Cryptology ePrint Archive: Report 2022/379

Fully Secure PSI via MPC-in-the-Head

S. Dov Gordon and Carmit Hazay and Phi Hung Le

Abstract: We design several new protocols for private set intersection (PSI) with active security: one for the two party setting, and two protocols for the multi-party setting. In recent years, the state-of-the-art protocols for two party PSI have all been built from OT-extension. This has led to extremely efficient protocols that provide correct output to one party;~seemingly inherent to the approach, however, is that there is no efficient way to relay the result to the other party with a provable correctness guarantee. Furthermore, there is no natural way to extend this line of works to more parties. We consider a new instantiation of an older approach. Using the MPC-in-the-head paradigm of Ishai et al [IPS08], we construct a polynomial with roots that encode the intersection, without revealing the inputs. Our reliance on this paradigm allows us to base our protocol on passively secure Oblivious Linear Evaluation (OLE) (requiring 4 such amortized calls per input element). Unlike state-of-the-art prior work, our protocols provide correct output to all parties. We have implemented our protocols, providing the first benchmarks for PSI that provides correct output to all parties. Additionally, we present a variant of our multi-party protocol that provides output only to a central server.

Category / Keywords: cryptographic protocols / Private set intersection, MPC-in-the-Head

Original Publication (in the same form): Proceedings on Privacy Enhancing Technologies (PETS)

Date: received 23 Mar 2022, last revised 28 Mar 2022

Contact author: ple13 at gmu edu

Available format(s): PDF | BibTeX Citation

Version: 20220328:220329 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]