Efficient and Low-communication Unbalanced Private Set Intersection Cardinality Protocol
Yuanyuan Li, X Yin, Shenhai Zheng, Peng Han · 2024
Private set intersection cardinality (PSI-CA) is a derivative of Private set intersection (PSI). It is designed to securely compute the intersection size of two sets, with one party obtaining the result without revealing anything. Optimizing the communication of encrypted sets and reducing privacy leaks at lower costs remains a challenge. This paper presents an efficient unbalanced PSI-CA protocol based on the Diffie-Hellman oblivious pseudorandom function (DH-OPRF). The protocol combines slicing for filtering with polynomial linking (PoL) to maintain connections between sliced data. This approach reduces computational and communication overhead without compromising privacy. The proposed protocol is 29.71 times more efficient in computation and 3.98 times more efficient in communication compared to existing unbalanced PSI-CA protocols, breaking the communication bottleneck and speeding up receiver query time. The protocol's viability for private common contact counting is demonstrated using sets with significant size differences.