Efficient Unbalanced Private Set Intersection Cardinality and User-friendly Privacy-preserving Contact Tracing


Mingli Wu and Tsz Hon Yuen, The University of Hong Kong


An unbalanced private set intersection cardinality (PSI-CA) protocol is a protocol to securely get the intersection cardinality of two sets X and Y without disclosing anything else, in which |Y| < |X|. In this paper, we propose efficient unbalanced PSI-CA protocols based on fully homomorphic encryption (FHE). To handle the long item issue in PSI-CA protocols, we invent two techniques: virtual Bloom filter and polynomial links. The former can encode a long item into several independent shorter ones. The latter fragments each long item into shorter slices and builds links between them.

Our FHE-based unbalanced PSI-CA protocols have the lowest communication complexity O(|Y|log(|X|), which is much cheaper than the existing balanced PSI-CA protocols with O(|Y|+|X|). When |X|=228 and |Y|=2048, our protocols are 172× ∼ 412× cheaper than the best balanced PSI-CA protocol. Our protocols can be easily modified into unbalanced PSI protocols. Compared with Cong et al. (CCS'21), one of our unbalanced PSI protocols can save 42.04% ∼ 58.85% communication costs and accelerate the receiver querying time.

We apply our lightweight unbalanced PSI-CA protocols to design a privacy-preserving contact tracing system. We demonstrate that our system outperforms existing schemes in terms of security and performance.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {291128,
author = {Mingli Wu and Tsz Hon Yuen},
title = {Efficient Unbalanced Private Set Intersection Cardinality and User-friendly Privacy-preserving Contact Tracing},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {283--300},
url = {https://www.usenix.org/conference/usenixsecurity23/presentation/wu-mingli},
publisher = {USENIX Association},
month = aug

Presentation Video