Paper 2013/335

Parallel and Dynamic Searchable Symmetric Encryption

Seny Kamara and Charalampos Papamanthou

Abstract

Searchable symmetric encryption (SSE) enables a client to outsource a collection of encrypted documents in the cloud and retain the ability to perform keyword searches without revealing information about the contents of the documents and queries. Although efficient SSE constructions are known, previous solutions are highly sequential. This is mainly due to the fact that, currently, the only method for achieving sub-linear time search is the inverted index approach (Curtmola, Garay, Kamara and Ostrovsky, CCS ’06) which requires the search algorithm to access a sequence of memory locations, each of which is unpredictable and stored at the previous location in the sequence. Motivated by advances in multi-core architectures, we present a new method for constructing sub-linear SSE schemes. Our approach is highly parallelizable and dynamic. With roughly a logarithmic number of cores in place, searches for a keyword w in our scheme execute in o(r) parallel time, where r is the number of documents containing keyword w (with more cores, this bound can go down to O(log n), i.e., independent of the result size r). Such time complexity outperforms the optimal \theta(r) sequential search time - a similar bound holds for the updates. Our scheme also achieves the following important properties: (a) it enjoys a strong notion of security, namely security against adaptive chosen-keyword attacks; (b) compared to existing sub-linear dynamic SSE schemes (e.g., Kamara, Papamanthou, Roeder, CCS ’12), updates in our scheme do not leak any information, apart from information that can be inferred from previous search tokens; (c) it can be implemented efficiently in external memory (with logarithmic I/O overhead). Our technique is simple and uses a red-black tree data structure; its security is proven in the random oracle model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
searchable encryptioncloud computingcloud storage
Contact author(s)
senyk @ microsoft com
History
2013-06-03: received
Short URL
https://ia.cr/2013/335
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/335,
      author = {Seny Kamara and Charalampos Papamanthou},
      title = {Parallel and Dynamic Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2013/335},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/335}},
      url = {https://eprint.iacr.org/2013/335}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.