Paper 2010/469

Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model

Emiliano De Cristofaro, Jihye Kim, and Gene Tsudik


Private Set Intersection (PSI) protocols allow one party (“client”) to compute an intersection of its input set with that of another party (“server”), such that the client learns nothing other than the set intersection and the server learns nothing beyond client input size. Prior work yielded a range of PSI protocols secure under different cryptographic assumptions. Protocols operating in the semi-honest model offer better (linear) complexity while those in the malicious model are often significantly more costly. In this paper, we construct PSI and Authorized PSI (APSI) protocols secure in the malicious model under standard cryptographic assumptions, with both linear communication and computational complexities. To the best of our knowledge, our APSI is the first solution to do so. Finally, we show that our linear PSI is appreciably more efficient than the state-of-the-art.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. To appear in Asiacrypt 2010
Contact author(s)
edecrist @ uci edu
2010-09-15: last of 3 revisions
2010-09-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Emiliano De Cristofaro and Jihye Kim and Gene Tsudik},
      title = {Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model},
      howpublished = {Cryptology ePrint Archive, Paper 2010/469},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.