TY - GEN
T1 - Oblivious Key-Value Stores and Amplification for Private Set Intersection
AU - Garimella, Gayathri
AU - Pinkas, Benny
AU - Rosulek, Mike
AU - Trieu, Ni
AU - Yanai, Avishay
N1 - Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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 ki↦ vi. When the vi values are random, the OKVS data structure hides the ki 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(ki) = vi. 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 pc. Setting p to be moderately small enables to validate it by running a relatively small number of O(1/p) experiments. This validates a pc 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.
AB - 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 ki↦ vi. When the vi values are random, the OKVS data structure hides the ki 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(ki) = vi. 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 pc. Setting p to be moderately small enables to validate it by running a relatively small number of O(1/p) experiments. This validates a pc 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.
UR - http://www.scopus.com/inward/record.url?scp=85115287436&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115287436&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-84245-1_14
DO - 10.1007/978-3-030-84245-1_14
M3 - Conference contribution
AN - SCOPUS:85115287436
SN - 9783030842444
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 395
EP - 425
BT - Advances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
A2 - Malkin, Tal
A2 - Peikert, Chris
PB - Springer Science and Business Media Deutschland GmbH
T2 - 41st Annual International Cryptology Conference, CRYPTO 2021
Y2 - 16 August 2021 through 20 August 2021
ER -