Cryptology ePrint Archive: Report 2017/677

Faster Unbalanced Private Set Intersection

Amanda C. Davi Resende and Diego F. Aranha

Abstract: Protocols for Private Set Intersection (PSI) are important cryptographic primitives that perform joint operations on datasets in a privacy-preserving way. They allow two parties to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. PSI implementations in the literature usually do not use the best possible cryptographic implementation techniques. This results in protocols presenting computational and communication complexities that are prohibitive, particularly in the case when one of the protocolís participant is a low-powered device and there are bandwidth restrictions. This paper builds on modern cryptographic engineering techniques and proposes optimizations for a promising one-way PSI protocol based on public-key cryptography. For the case when one of the parties holds a set much smaller than the other (a realistic assumption in many scenarios) we show that our improvements and optimizations yield a protocol that over performs the communication complexity and the run time of previous proposals by up to one thousand times.

Category / Keywords: Cuckoo filter, Private Set Intersection, unbalanced PSI, software implementation

Date: received 6 Jul 2017, last revised 26 Sep 2017

Contact author: amanda resende at ic unicamp br

Available format(s): PDF | BibTeX Citation

Version: 20170926:211220 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]