Paper 2021/1116

Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication

Kelong Cong, Radames Cruz Moreno, Mariana Botelho da Gama, Wei Dai, Ilia Iliashenko, Kim Laine, and Michael Rosenberg

Abstract

It is known that fully homomorphic encryption (FHE) can be used to build efficient (labeled) Private Set Intersection protocols in the unbalanced setting, where one of the sets is much larger than the other (Chen et al. (CCS'17, CCS'18)). In this paper we demonstrate multiple algorithmic improvements upon these works. In particular, our protocol has an asymptotically better computation cost, requiring only $O(\sqrt{|X|})$ homomorphic multiplications, and communication complexity sublinear in the larger set size $|X|$. We demonstrate that our protocol is significantly better than that of Chen et al. (CCS'18) for many practical parameters, especially in terms of online communication cost. For example, when intersecting $2^{28}$ and $2048$ item sets, our protocol reduces the online computation time by more than 83% and communication by more than 32%. When intersecting $2^{24}$ and $4096$ item sets, our protocol reduces the online computation time by 50% and communication by 52%. Our comparison to other state-of-the-art unbalanced PSI protocols shows that our protocol has the best total communication complexity when $|X| \geq 2^{24}$. For labeled PSI our protocol also outperforms Chen et al. (CCS'18). When intersecting $2^{20}$ and $256$ item sets, with the larger set having associated $288$-byte labels, our protocol reduces the online computation time by more than 85% and communication by 36%. Finally, we demonstrate a modification that results in nearly constant communication cost in the larger set size $|X|$, but impractically high computation complexity on today's CPUs. For example, to intersect a $210$-item set with sets of size $2^{22}$, $2^{24}$, or $2^{26}$, our proof-of-concept implementation requires only $0.76$ MB of online communication, which is more than a $24$-fold improvement over Chen et al. (CCS'18).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM CCS 2021
Keywords
private set intersectionhomomorphic encryption
Contact author(s)
kim laine @ gmail com
iliailiashenko @ gmail com
History
2021-11-15: last of 2 revisions
2021-09-03: received
See all versions
Short URL
https://ia.cr/2021/1116
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1116,
      author = {Kelong Cong and Radames Cruz Moreno and Mariana Botelho da Gama and Wei Dai and Ilia Iliashenko and Kim Laine and Michael Rosenberg},
      title = {Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1116},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1116}},
      url = {https://eprint.iacr.org/2021/1116}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.