Paper 2014/638

Substring-Searchable Symmetric Encryption

Melissa Chase and Emily Shen

Abstract

In this paper, we consider a setting where a client wants to outsource storage of a large amount of private data and then perform substring search queries on the data -- given a data string s and a search string p, find all occurrences of p as a substring of s. First, we formalize an encryption paradigm that we call queryable encryption, which generalizes searchable symmetric encryption (SSE) and structured encryption. Then, we construct a queryable encryption scheme for substring queries. Our construction uses suffix trees and achieves asymptotic efficiency comparable to that of unencrypted suffix trees. Encryption of a string of length n takes O(kn) time and produces a ciphertext of size O(kn), and querying for a substring of length m that occurs z times takes O(km+z) time and three rounds of communication, where k is the security parameter. Our security definition guarantees correctness of query results and privacy of data and queries against a malicious, adaptive adversary. Following the line of work started by Curtmola et al. (ACM CCS 2006), in order to construct more efficient schemes we allow the query protocol to leak some limited information that is captured precisely in the definition. We prove security of our substring-searchable encryption scheme against malicious adversaries, where the query protocol leaks limited information about memory access patterns through the suffix tree of the encrypted string.