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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. PETS 2015
DOI
10.1515/popets-2015-0014
Contact author(s)
melissac @ microsoft com
History
2015-06-18: revised
2014-08-21: received
See all versions
Short URL
https://ia.cr/2014/638
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/638,
      author = {Melissa Chase and Emily Shen},
      title = {Substring-Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2014/638},
      year = {2014},
      doi = {10.1515/popets-2015-0014},
      note = {\url{https://eprint.iacr.org/2014/638}},
      url = {https://eprint.iacr.org/2014/638}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.