Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations
| Autor: | Ido Shahaf, Moni Naor, Gilad Asharov, Gil Segev |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Scheme (programming language)
Theoretical computer science General Computer Science Computer science General Mathematics Cryptography 02 engineering and technology 0102 computer and information sciences Upper and lower bounds 01 natural sciences 010104 statistics & probability ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0202 electrical engineering electronic engineering information engineering Overhead (computing) 0101 mathematics computer.programming_language business.industry Keyword search Linear space Locality Construct (python library) ComputerSystemsOrganization_PROCESSORARCHITECTURES Symmetric-key algorithm 010201 computation theory & mathematics 020201 artificial intelligence & image processing business computer |
| Zdroj: | STOC |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/19m1303186 |
| Popis: | Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of non-contiguous memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer). We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly-optimal read efficiency. Specifically, for a database of size N, under the modest assumption that no keyword appears in more than N1 − 1/loglogN documents, we construct a scheme with read efficiency O(loglogN). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT ’14) showing that any SSE scheme must be sub-optimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency O(logN). Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations (“balls and bins”) problem that we put forward. We construct nearly-optimal two-dimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|