Welcome to the resource topic for 2021/883
Title:
Oblivious Key-Value Stores and Amplification for Private Set Intersection
Authors: Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, 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.
ePrint: https://eprint.iacr.org/2021/883
Talk: https://www.youtube.com/watch?v=Q-5W5MzpPhw
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .