Welcome to the resource topic for 2016/746
Title:
Improved Private Set Intersection against Malicious Adversaries
Authors: Peter Rindal, Mike Rosulek
Abstract: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\times on a single thread. When compared to the previous fastest protocol of De Cristofaro et al., we improve the running time by 8-24\times. 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.
ePrint: https://eprint.iacr.org/2016/746
Talk: https://www.youtube.com/watch?v=Dz_mJmTZNQc
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .