Name
Abstract | ||
|---|---|---|
Many recent private set intersection (PSI) protocols encode input sets as polynomials. We consider the more general notion of an oblivious key-value store (OKVS), which is a data structure that compactly represents a desired mapping k(i) -> v(i). When the v(i) values are random, the OKVS data structure hides the k(i) values that were used to generate it. The simplest (and size-optimal) OKVS is a polynomial p that is chosen using interpolation such that p(k(i)) = v(i).We initiate the formal study of oblivious key-value stores, and show new constructions resulting in the fastest OKVS to date.Similarly to cuckoo hashing, current analysis techniques are insufficient for finding concrete parameters to guarantee a small failure probability for our OKVS constructions. Moreover, it would cost too much to run experiments to validate a small upperbound on the failure probability. We therefore show novel techniques to amplify an OKVS construction which has a failure probability p, to an OKVS with a similar overhead and failure probability p(c). Setting p to be moderately small enables to validate it by running a relatively small number of O(1/p) experiments. This validates a p(c) failure probability for the amplified OKVS.Finally, we describe how OKVS can significantly improve the state of the art of essentially all variants of PSI. This leads to the fastest two-party PSI protocols to date, for both the semi-honest and the malicious settings. Specifically, in networks with moderate bandwidth (e.g., 30-300 Mbps) our malicious two-party PSI protocol has 40% less communication and is 20-40% faster than the previous state of the art protocol, even though the latter only has heuristic confidence. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-84245-1_14 | ADVANCES IN CRYPTOLOGY - CRYPTO 2021, PT II |
DocType | Volume | ISSN |
Conference | 12826 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gayathri Garimella | 1 | 0 | 1.01 |
| Benny Pinkas | 2 | 6470 | 444.33 |
| Mike Rosulek | 3 | 334 | 25.32 |
| Ni Trieu | 4 | 0 | 1.01 |
| Avishay Yanai | 5 | 0 | 0.34 |