Department of Computer Science
The Locality of Searchable Symmetric Encryption
- Publication Date: 2014-05-01
- Journal Volume: EUROCRYPT 2014
- Conference Location: Copenhagen, Denmark
- Link to Content 1: [full version]
- 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 ω(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.
We are committed to fostering a safe environment while upholding the principles of academic freedom and free expression of our community.
We're Hiring
Undergraduate
Graduate
Research
Upcoming Events
| 08 Sep 2026; - 10:15AM - 11:00AM Understanding and Shaping Strategic Behavior in Multiagent AI Systems |
| 10 Sep 2026; - 12:00PM - 03:00PM 2026 Annual CS Fall Fair |
| 15 Sep 2026; - 10:00AM - 12:00PM Mechanistic Interpretability for Vision: Beyond Feature-Level Interpretability to Model Control and Cross-Layer Computation |
