Paper 2022/379

Fully Secure PSI via MPC-in-the-Head

S. Dov Gordon, Carmit Hazay, and Phi Hung Le


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Proceedings on Privacy Enhancing Technologies (PETS)
Private set intersectionMPC-in-the-Head
Contact author(s)
ple13 @ gmu edu
2022-03-28: revised
2022-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {S.  Dov Gordon and Carmit Hazay and Phi Hung Le},
      title = {Fully Secure PSI via MPC-in-the-Head},
      howpublished = {Cryptology ePrint Archive, Paper 2022/379},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.