Welcome to the resource topic for 2014/308
Title:
The Locality of Searchable Symmetric Encryption
Authors: David Cash, 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.
ePrint: https://eprint.iacr.org/2014/308
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .