Verifiable Pattern Matching on Outsourced Texts

In this paper we consider a scenario where a user wants to outsource her documents to the cloud, so that she can later reliably delegate to the cloud pattern matching operations on these documents. We propose an efficient solution to this problem that relies on the homomorphic MAC for polynomials proposed by Catalano and Fiore ini¾?[14]. Our main contribution are new methods to express pattern matching operations both in their exact and approximate variants as low degree polynomials, i.e.i¾?polynomials whose degree solely depends on the size of the pattern. To better assess the practicality of our schemes, we propose a concrete implementation that further optimizes the efficiency of the homomorphic MAC fromi¾?[14]. Our implementation shows that the proposed protocols are extremely efficient for the client, while remaining feasible at server side.