Peter Rindal & Mike Rosulek ~ eprint/2016/746 ~ Eurocrypt’17
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 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.