Paper 2022/379

Fully Secure PSI via MPC-in-the-Head

S. Dov Gordon, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Proceedings on Privacy Enhancing Technologies (PETS)
Keywords
Private set intersectionMPC-in-the-Head
Contact author(s)
ple13 @ gmu edu
History
2022-03-28: revised
2022-03-28: received
See all versions
Short URL
https://ia.cr/2022/379
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/379,
      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{https://eprint.iacr.org/2022/379}},
      url = {https://eprint.iacr.org/2022/379}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.