Paper 2023/1407

Fully Homomorphic Encryption-Based Protocols for Enhanced Private Set Intersection Functionalities

JINGWEI HU, Nanyang Technological University
Junyan Chen, Zhejiang Lab
Wangchen Dai, Zhejiang Lab
Huaxiong Wang, Nanyang Technological University

This study delves into secure computations for set intersections using fully homomorphic encryption (FHE) within the semi-honest setting. Our protocols facilitate joint computations between two parties, each holding a set of inputs denoted as $N_s$ and $N_r$ in size, respectively. The primary objective is to determine various functionalities, such as intersection size and sum, while maintaining data confidentiality. These functionalities extend the classic private set intersection (PSI) and have practical applications in contact tracing, ad conversion analysis, and online dating, each abstracted into specialized PSI protocols. Our work demonstrates that these extended PSI functionalities are interconnected, with the PSI-cardinality protocol serving as the foundation. By adapting this protocol, we naturally arrive at PSI-sum-cardinality. Additionally, PSI-token-threshold is achieved by augmenting PSI-cardinality with FHE-based oblivious polynomial evaluation (OPE). The tPSI protocol combines PSI-token-threshold and standard PSI, allowing information sharing when the intersection size exceeds a threshold. Our protocols excel in simplicity, enhancing ease of understanding, implementation, optimization, and long-term maintenance. They also exhibit sublinear communication complexity concerning the larger sender's set, rendering them well-suited for scenarios involving substantial data. Various optimization techniques further bolster their practical efficiency.

Available format(s)
Cryptographic protocols
Publication info
Private Set IntersectionThreshold FunctionalityFully Homomorphic Encryption
Contact author(s)
davidhoo471494221 @ gmail com
chjuny @ zhejianglab com
w dai @ my cityu edu hk
hxwang @ ntu edu sg
2024-01-23: last of 4 revisions
2023-09-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {JINGWEI HU and Junyan Chen and Wangchen Dai and Huaxiong Wang},
      title = {Fully Homomorphic Encryption-Based Protocols for Enhanced Private Set Intersection Functionalities},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1407},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.