Abstract. In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an untrusted server in the cloud. While most earlier work considers the general question of how to securely outsource any computation to the cloud server, we focus on concrete and important functionalities and give the first protocol for the pattern matching problem in the cloud. Loosely speaking, this problem considers a text T that is outsourced to the cloud S by a client CT. In a query phase, clients C1,...,Cl runanefficientprotocol with the server S and the client CT in order to learn the positions at which a pattern of length m matches the text (and nothing beyond that). This is called the outsourced pattern matching problem and is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases that contain confidential data (e.g., health related data about patient history). Our constructions offer simulation-based security in the presence of semi-honest and malicious adversaries (in the random oracle model) and limit the communication in the query phase to O(m) bits plus the number of occurrences — which is optimal. In contrast to generic solutions for delegatable computation, our schemes do not rely on fully homomorphic encryption but instead uses novel ideas for solving pattern matching, based on efficiently solvable instances of the subset sum problem. 1
Oblivious transfer (OT) is a significant primitive with wide use in secure two-party computation, private set intersection private and other cryptographic schemes. In the past ten years, different variants of OT primitive like cut-and-choose OT (CCOT) and outsourced OT (OOT), have been proposed so as to satisfy various emerging models. In this paper, we firstly propose and formalize a new primitive called permutable cut-and-choose OT (PCCOT) which generalizes the original CCOT functionality. Furthermore, we construct an efficient PCCOT protocol in the presence of malicious adversaries using the Decisional Diffie-Hellman (DDH) hard assumption. It is worth mentioning that we apply the PCCOT primitive to the efficient construction of secure wildcard pattern matching (WPM) protocol. The WPM functionality allows a party to determine the locations of its pattern with wildcard characters occurs in a long text of another party while revealing nothing to either party in addition to the length of their own inputs. Our proposed secure WPM protocol via PCCOT is secure against semi-honest adversary with 2 rounds and has identical communication cost as the the state-of-the-art scheme.
Let S1,S2∈Σ∗ strings, we say that S1 {\em jumble match} S2 if they are permutations of each other. Given a text T of size N and a string S∈Σ∗, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in T jumbled matching S. In classical computing, a widespread conjecture is that JPM requires Ω(N2−ε) preprocessing time and space for O(1) query time, or Ω(N1−δ) query time in the online version, with ε,δ>0. In this paper, we present a quantum algorithm for the online JPM in O(N) time.