Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
The Locality of Searchable Symmetric Encryption
verfasst von : David Cash, Stefano Tessaro
Erschienen in: Advances in Cryptology – EUROCRYPT 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 nonlocality 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.