Paper 2017/677

Faster Unbalanced Private Set Intersection

Amanda Cristina Davi Resende and Diego de Freitas 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. Unfortunately, PSI implementations in the literature do not usually employ 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 participants 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 outperforms the communication complexity and the run time of previous proposals by around one thousand times.

Note: Minor fixes found a long time after publication.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Financial Cryptography and Data Security (FC 2018)
Keywords
Cuckoo filterPrivate Set Intersectionunbalanced PSIsoftware implementation
Contact author(s)
amanda resende @ ic unicamp br
dfaranha @ ic unicamp br
History
2022-05-09: last of 4 revisions
2017-07-12: received
See all versions
Short URL
https://ia.cr/2017/677
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/677,
      author = {Amanda Cristina Davi Resende and Diego de Freitas Aranha},
      title = {Faster Unbalanced Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2017/677},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/677}},
      url = {https://eprint.iacr.org/2017/677}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.