Oblivious Key-Value Stores and Amplification for Private Set Intersection
Oblivious Key-Value Stores and Amplification for Private Set Intersection
复制标题
DOI：
10.1007/978-3-030-84245-1_14
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Gayathri Garimella;Benny Pinkas;Mike Rosulek;Ni Trieu;Avishay Yanai
中科院分区：
文献类型：
--
作者：
Gayathri Garimella;Benny Pinkas;Mike Rosulek;Ni Trieu;Avishay Yanai
许多最近的私有集交集（PSI）协议编码的多项式输入集。我们考虑更一般的概念，即不经意的键值存储（OKVS），这是一种数据结构，可压缩地表示所需的映射。当值是随机的时，OKVS数据结构会隐藏用于生成它的值。（和大小最优）OKVS是一个多项式，使用插值选择，使得。我们开始了对不经意的键值存储的正式研究，并展示了迄今为止最快的OKVS的新构造。类似于布谷鸟哈希，目前的分析技术不足以找到具体的参数，以保证我们的OKVS结构的小故障概率。此外，运行实验来验证故障概率的小上限将花费太多。因此，我们展示了新的技术来放大一个OKVS建设，它有一个故障probabilityp，一个OKVS具有类似的开销和故障概率。将p设置为适当的小值，可以通过运行相对较少的O（1/p）实验来验证它。这验证了扩增的OKVS的失败概率。最后，我们描述了OKVS如何显著改善基本上所有PSI变体的最新技术水平。这导致了迄今为止最快的两方PSI协议，无论是半诚实还是恶意设置。具体地，在具有中等带宽的网络中（例如，30-300 Mbps），我们的恶意两方PSI协议的通信量减少了40%，比以前的最先进的协议快20-40%，即使后者只有启发式的信心。
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. When thevalues are random, the OKVS data structure hides thevalues that were used to generate it. The simplest (and size-optimal) OKVS is a polynomialpthat is chosen using interpolation such that.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 findingconcreteparameters 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 probabilityp, to an OKVS with a similar overhead and failure probability. Settingpto be moderately small enables to validate it by running a relatively small number ofO(1/p) experiments. This validates afailure 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.