Paper 2014/308

The Locality of Searchable Symmetric Encryption

David Cash and Stefano Tessaro

Abstract

This paper proves a lower bound on the trade-off between server storage size and the locality of memory accesses in searchable symmetric encryption (SSE). Namely, when encrypting an index of $N$ identifier/keyword pairs, the encrypted index must have size $\omega(N)$ \emph{or} the scheme must perform searching with $\omega(1)$ non-contiguous reads to memory \emph{or} the scheme must read many more bits than is necessary to compute the results. Recent implementations have shown that non-locality of server memory accesses create a throughput-bottleneck on very large databases. Our lower bound shows that this is due to the security notion and not a defect of the constructions. An upper bound is also given in the form of a new SSE construction with an $O(N\log N)$ size encrypted index that performs $O(\log N)$ reads during a search.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2014
Contact author(s)
david cash @ cs rutgers edu
History
2014-04-30: received
Short URL
https://ia.cr/2014/308
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/308,
      author = {David Cash and Stefano Tessaro},
      title = {The Locality of Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2014/308},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/308}},
      url = {https://eprint.iacr.org/2014/308}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.