Practical Multi-Party Private Set Intersection Protocols

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Practical Multi-Party Private Set Intersection Protocols

By: 
Aslı Bay; Zekeriya Erkin; Jaap-Henk Hoepman; Simona Samardjiska; Jelle Vos

Privacy-preserving techniques for processing sets of information have attracted the research community’s attention in recent years due to society’s increasing dependency on the availability of data at any time. One of the fundamental problems in set operations is known as Private Set Intersection (PSI). The problem requires two parties to compute the intersection between their sets while preserving correctness and privacy. Although several efficient two-party PSI protocols already exist, protocols for PSI in the multi-party setting (MPSI) currently scale poorly with a growing number of parties, even though this applies to many real-life scenarios. This paper fills this gap by proposing two multi-party protocols based on Bloom filters and threshold homomorphic PKEs, which are secure in the semi-honest model. The first protocol is a multi-party PSI, whereas the second provides a more subtle functionality - threshold multi-party PSI (T-MPSI) - which outputs items of the server that appear in at least some number of other private sets. The protocols are inspired by the Davidson-Cid protocol based on Bloom filters. We compare our MPSI protocol against Kolesnikov et al. , which is among the fastest known MPSI protocols. Our MPSI protocol performs better than Kolesnikov et al. in terms of run time, given that the sets are small and there is a large number of parties. Our T-MPSI protocol performs better than other existing works: the computational and communication complexities are linear in the number of elements in the largest set given a fixed number of colluding parties. We conclude that our MPSI and T-MPSI protocols are practical solutions suitable for emerging use-case scenarios with many parties, where previous solutions did not scale well.

SPS on Twitter

  • Celebrate International Women's Day with SPS! This Tuesday, 8 March, join Dr. Neeli Prasad for "Unlocking the Poten… https://t.co/GDQIgjSpLs
  • Check out the SPS Education Short Courses, new at ! Earn PDH and CEU certificates by attending either in… https://t.co/1uYFNvltg7
  • We're partnering with the IEEE Humanitarian Activities on Wednesday, 2 March to bring you a new webinar, "Increasin… https://t.co/JzhaBl17UY
  • The DEGAS Webinar Series continues this Thursday, 3 March when Dr. Steven Smith present "Causal Inference on Networ… https://t.co/10kppomXdl
  • In the February issue of the Inside Signal Processing Newsletter, we talk to Dr. Oriol Vinyals, who discusses his j… https://t.co/XLQ7tpEq0A

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar