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. 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 Nx for the sender, and Ny for the receiver, we achieve a communication overhead of O(NylogNx). Our benchmarks show that it takes 36 seconds of online-computation, 71 seconds of non-interactive (receiver-independent) pre-processing, and only 12.5MB 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 times reduction in communication, with minimal increase in computation.Category / Keywords: cryptographic protocols / Private set intersection, fully homomorphic encryption Date: received 31 Mar 2017, last revised 3 Apr 2017 Contact author: haoche at microsoft com Available format(s): PDF | BibTeX Citation Note: Fixing one more reference. Version: 20170407:024218 (All versions of this report) Short URL: ia.cr/2017/299 Discussion forum: Show discussion | Start new discussion