Paper 2020/1280

DORY: An Encrypted Search System with Distributed Trust

Emma Dauterman, Eric Feng, Ellen Luo, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.OSDI 2020
Keywords
Searchable Encryption
Contact author(s)
edauterman @ berkeley edu
History
2021-04-25: last of 3 revisions
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1280
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1280,
      author = {Emma Dauterman and Eric Feng and Ellen Luo and Raluca Ada Popa and Ion Stoica},
      title = {DORY: An Encrypted Search System with Distributed Trust},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1280},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1280}},
      url = {https://eprint.iacr.org/2020/1280}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.