Cryptology ePrint Archive: Report 2022/334

Private Set Intersection from Pseudorandom Correlation Generators

Dung Bui and Geoffroy Couteau

Abstract: Pseudorandom correlation generators (PCG) allow two parties to generate long correlated pseudorandom strings with minimal communication. Since secure computation applications typically benefit from such protocols, we explore the use of PCG to improve private set intersection (PSI) protocols. We obtain two main results.

In our first result, we construct a new highly optimized semi-honest PSI. Our protocol builds upon the protocol of (Kolesnikov et al., CCS 2016), and significantly improves it using multiple optimizations, including a new oblivious pseudorandom function (built from a PCG for the subfield-VOLE correlation), and a new technique to handle a generalized variant of Cuckoo hashing tailored to our setting. For sets with elements of size $\ell$ bits with $\ell \leq 70$, our protocol outperforms all known PSI protocols, by as much as $42\%$ when $\ell = 32$ and with $n = 2^{20}$ items (compared to the best known protocol of (Rindal and Schoppmann, Eurocrypt 2021), enhanced with recent improvements). For these parameters, the communication of our protocol is extremely small: only $129n$ bits of total communication.

In our second result, we use a PCG for a new correlation, called the subfield ring-OLE correlation. We construct a new protocol with attracting features: competitive communication with the state of the art, fully malicious security in the standard model (no random oracle or tailored assumptions on hash functions). To our knowledge, our protocol outperforms by a large margin all previous protocols in the standard model, and is competitive even with ROM-based protocols. Furthermore, our protocol leads to a batch non-interactive PSI, where (after a one-time short interaction) a client can broadcast a single compact encoding of its dataset, and compute its intersection with the datasets of multiple servers after receiving a single message from each server.

Category / Keywords: cryptographic protocols / private set intersection, pseudorandom correlation generators, subfield vector OLE

Date: received 9 Mar 2022

Contact author: bui at irif fr, couteau at irif fr

Available format(s): PDF | BibTeX Citation

Version: 20220314:115019 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]