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.Category / Keywords: pattern matching, delegatable computation, simulation-based security Original Publication (with major differences): ICALP 2011 Date: received 25 Aug 2014, last revised 30 Apr 2015 Contact author: venturi at di uniroma1 it Available format(s): PDF | BibTeX Citation Note: Simplified protocol for malicious setting. Version: 20150430:083614 (All versions of this report) Discussion forum: Show discussion | Start new discussion