Privacy Preserving Substring Search Protocol with Polylogarithmic Communication Cost

The problem of efficiently searching into outsourced encrypted data, while providing strong privacy guarantees, is a challenging problem arising from the separation of data ownership and data management typical of cloud-based applications. Several cryptographic solutions allowing a client to look-up occurrences of a substring of choice in an outsourced document collection have been publicly presented. Nonetheless, practical application requirements in terms of privacy, security and efficiency actively push for new and improved solutions. We present a privacy-preserving substring search protocol exhibiting a sub-linear communication cost, with a limited computational effort on the server side. The proposed protocol provides search pattern and access pattern privacy, while its extension to a multi-user setting shows significant savings in terms of outsourced storage w.r.t. a baseline solution where the whole dataset is replicated. The performance figures of an optimized implementation of our protocol, searching into a remotely stored genomic dataset, validate the practicality of the approach exhibiting a data transfer of less than 200 kiB to execute a query over a document of 40 MiB, with execution times on client and server in the range of a few seconds and a few minutes, respectively.