Paper 2014/662

Outsourced Pattern Matching

Sebastian Faust, Carmit Hazay, and Daniele Venturi


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 $\bfS$ by a sender $\sen$. In a query phase, receivers $\rec_1, \ldots , \rec_l$ run an efficient protocol with the server $\bfS$ and the sender $\sen$ 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 which 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 are simulation-based secure 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 use novel ideas for solving pattern matching, based on a reduction to the subset sum problem. Interestingly, we do not rely on the hardness of the problem, but rather we exploit instances that are solvable in polynomial-time. A follow-up result demonstrates that the random oracle is essential in order to meet our communication bound.

Note: Simplified protocol for malicious setting.

Available format(s)
Publication info
Published elsewhere. Major revision. ICALP 2011
pattern matchingdelegatable computationsimulation-based security
Contact author(s)
venturi @ di uniroma1 it
2015-04-30: revised
2014-08-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Faust and Carmit Hazay and Daniele Venturi},
      title = {Outsourced Pattern Matching},
      howpublished = {Cryptology ePrint Archive, Paper 2014/662},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.