Oblivious Key-Value Stores and Amplification for Private Set Intersection

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
EditorsTal Malkin, Chris Peikert
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages31
ISBN (Print)9783030842444
StatePublished - 2021
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: Aug 16 2021Aug 20 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12826 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Oblivious Key-Value Stores and Amplification for Private Set Intersection'. Together they form a unique fingerprint.

Cite this