Cryptology ePrint Archive: Report 2020/1280

DORY: An Encrypted Search System with Distributed Trust

Emma Dauterman and Eric Feng and Ellen Luo and Raluca Ada Popa and Ion Stoica

Abstract: Efficient, leakage-free search on encrypted data has remained an unsolved problem for the last two decades; efficient schemes are vulnerable to leakage-abuse attacks, and schemes that eliminate leakage are impractical to deploy. To overcome this tradeoff, we reexamine the system model. We surveyed five companies providing end-to-end encrypted filesharing to better understand what they require from an encrypted search system. Based on our findings, we design and build DORY, an encrypted search system that addresses real-world requirements and protects search access patterns; namely, when a user searches for a keyword over the files within a folder, the server learns only that a search happens in that folder, but does not learn which documents match the search, the number of documents that match, or other information about the keyword. DORY splits trust between multiple servers to protect against a malicious attacker who controls all but one of the servers. We develop new cryptographic and systems techniques to meet the efficiency and trust model requirements outlined by the companies we surveyed. We implement DORY and show that it performs orders of magnitude better than a baseline built on ORAM. Parallelized across 8 servers, each with 16 CPUs, DORY takes 116ms to search roughly 50K documents and 862ms to search over 1M documents.

Category / Keywords: cryptographic protocols / Searchable Encryption

Original Publication (with major differences): OSDI 2020

Date: received 13 Oct 2020, last revised 19 Nov 2020

Contact author: edauterman at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20201119:172421 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]