### Oblivious Key-Value Stores and Amplification for Private Set Intersection

Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai

##### 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 \mapsto 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 {\em 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 upper bound 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.

Note: A better description of recent work eprint 2021/122

Available format(s)
Category
Cryptographic protocols
Publication info
Keywords
oblivious key value storeprivate set intersection
Contact author(s)
ay yanay @ gmail com
History
2021-11-30: revised
See all versions
Short URL
https://ia.cr/2021/883

CC BY

BibTeX

@misc{cryptoeprint:2021/883,
author = {Gayathri Garimella and Benny Pinkas and Mike Rosulek and Ni Trieu and Avishay Yanai},
title = {Oblivious Key-Value Stores and Amplification for Private Set Intersection},
howpublished = {Cryptology ePrint Archive, Paper 2021/883},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/883}},
url = {https://eprint.iacr.org/2021/883}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.