Paper 2014/853

Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation

David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cătălin Roşu, and Michael Steiner

Abstract

We design and implement dynamic symmetric searchable encryption schemes that efficiently and privately search server-held encrypted databases with tens of billions of record-keyword pairs. Our basic theoretical construction supports single-keyword searches and offers asymptotically optimal server index size, fully parallel searching, and minimal leakage. Our implementation effort brought to the fore several factors ignored by earlier coarse-grained theoretical performance analyses, including low-level space utilization, I/O parallelism and goodput. We accordingly introduce several optimizations to our theoretically optimal construction that model the prototype's characteristics designed to overcome these factors. All of our schemes and optimizations are proven secure and the information leaked to the untrusted server is precisely quantified. We evaluate the performance of our prototype using two very large datasets: a synthesized census database with 100 million records and hundreds of keywords per record and a multi-million webpage collection that includes Wikipedia as a subset. Moreover, we report on an implementation that uses the dynamic SSE schemes developed here as the basis for supporting recent SSE advances, including complex search queries (e.g., Boolean queries) and richer operational settings (e.g., query delegation), in the above terabyte-scale databases.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. NDSS 2014
DOI
10.14722/ndss.2014.23264
Keywords
Searchable Encryption
Contact author(s)
david cash @ cs rutgers edu
History
2014-10-22: received
Short URL
https://ia.cr/2014/853
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/853,
      author = {David Cash and Joseph Jaeger and Stanislaw Jarecki and Charanjit Jutla and Hugo Krawczyk and Marcel-Cătălin Roşu and Michael Steiner},
      title = {Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/853},
      year = {2014},
      doi = {10.14722/ndss.2014.23264},
      note = {\url{https://eprint.iacr.org/2014/853}},
      url = {https://eprint.iacr.org/2014/853}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.