Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography /

Original Publication (with minor differences): IACR-EUROCRYPT-2014

Date: received 30 Apr 2014

Contact author: david cash at cs rutgers edu

Available format(s): PDF | BibTeX Citation

Version: 20140430:211006 (All versions of this report)

Short URL: ia.cr/2014/308

Discussion forum: Show discussion | Start new discussion