Paper 2017/299

Fast Private Set Intersection from Homomorphic Encryption

Hao Chen, Kim Laine, and Peter Rindal

Abstract

Private Set Intersection (PSI) is a cryptographic technique that allows two parties to compute the intersection of their sets without revealing anything except the intersection. We use fully homomorphic encryption to construct a fast PSI protocol with a small communication overhead that works particularly well when one of the two sets is much smaller than the other, and is secure against semi-honest adversaries. The most computationally efficient PSI protocols have been constructed using tools such as hash functions and oblivious transfer, but a potential limitation with these approaches is the communication complexity, which scales linearly with the size of the larger set. This is of particular concern when performing PSI between a constrained device (cellphone) holding a small set, and a large service provider (e.g. \emph{WhatsApp}), such as in the Private Contact Discovery application. Our protocol has communication complexity linear in the size of the smaller set, and logarithmic in the larger set. More precisely, if the set sizes are $N_Y < N_X$, we achieve a communication overhead of $O(N_Y \log N_X)$. Our running-time-optimized benchmarks show that it takes $36$ seconds of online-computation, $71$ seconds of non-interactive (receiver-independent) pre-processing, and only $12.5$MB of round trip communication to intersect five thousand $32$-bit strings with $16$ million $32$-bit strings. Compared to prior works, this is roughly a $38$--$115 \times$ reduction in communication with minimal difference in computational overhead.

Note: Added a reference to [Kiss et al., 2017]

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
private set intersectionfully homomorphic encryption
Contact author(s)
kim laine @ microsoft com
History
2017-09-06: last of 4 revisions
2017-04-07: received
See all versions
Short URL
https://ia.cr/2017/299
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/299,
      author = {Hao Chen and Kim Laine and Peter Rindal},
      title = {Fast Private Set Intersection from Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/299},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/299}},
      url = {https://eprint.iacr.org/2017/299}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.