Cryptology ePrint Archive: Report 2014/853

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

David Cash and Joseph Jaeger and Stanislaw Jarecki and Charanjit Jutla and Hugo Krawczyk and 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.

Category / Keywords: Searchable Encryption

Original Publication (with major differences): NDSS 2014

Date: received 17 Oct 2014

Contact author: david cash at cs rutgers edu

Available format(s): PDF | BibTeX Citation

Version: 20141022:163708 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]