Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations

DOI10.1137/19M1303186zbMath1475.94101OpenAlexW3200246893WikidataQ121141247 ScholiaQ121141247MaRDI QIDQ5157397

Ido Shahaf, Moni Naor, Gil Segev, Gilad Asharov

Publication date: 18 October 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1303186

zbMATH Keywords

localitysearchable symmetric encryptionbalanced allocations

Mathematics Subject Classification ID

Database theory (68P15) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A proof of security of Yao's protocol for two-party computation
• Negative association of random variables, with applications
• Deterministic Dictionaries
• Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries
• Structured Encryption and Controlled Disclosure
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• Privacy Preserving Keyword Searches on Remote Encrypted Data
• Uniform Hashing in Constant Time and Optimal Space
• Balanced Allocations
• Balls and bins: A study in negative dependence
• Cuckoo hashing
• The Locality of Searchable Symmetric Encryption
• Probability and Computing
• Concentration of Measure for the Analysis of Randomized Algorithms