1. Improved Private Set Intersection against Malicious Adversaries 2017 Eurocrypt PSI
    Peter Rindal and Mike Rosulek
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    author = {Peter Rindal and Mike Rosulek},
    title = {Improved Private Set Intersection against Malicious Adversaries},
    howpublished = {Cryptology ePrint Archive, Report 2016/746},
    year = {2016},
    note = {\url{https://eprint.iacr.org/2016/746}},

Private set intersection (PSI) refers to a special case of secure two-party computation in which the parties each have a set of items and compute the intersection of these sets without revealing any additional information. In this paper we present improvements to practical PSI providing security in the presence of {\em malicious} adversaries. Our starting point is the protocol of Dong, Chen & Wen (CCS 2013) that is based on Bloom filters. We identify a bug in their malicious-secure variant and show how to fix it using a cut-and-choose approach that has low overhead while simultaneously avoiding one the main computational bottleneck in their original protocol. We also point out some subtleties that arise when using Bloom filters in malicious-secure cryptographic protocols. We have implemented our PSI protocols and report on its performance. Our improvements reduce the cost of Dong et al.’s protocol by a factor of 14−110× on a single thread. When compared to the previous fastest protocol of De Cristofaro et al., we improve the running time by 8−24×. For instance, our protocol has an online time of 14 seconds and an overall time of 2.1 minutes to securely compute the intersection of two sets of 1 million items each.