Skip to content Skip to navigation

The Locality of Searchable Symmetric Encryption

The Locality of Searchable Symmetric Encryption

Author Name: 

David Cash, Stefano Tessaro

Publication Date: 
May, 2015

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 ω(N) or the scheme must perform
searching with ω(1) non-contiguous reads to memory 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.