PSI with computation or Circuit-PSI for Unbalanced Sets from Homomorphic Encryption

Abstract

Circuit-based Private Set Intersection (circuit-PSI) refers to cryptographic protocols that let two parties with input set X and Y compute a function f over the intersection set X ∩ Y, without revealing any other information. The research efforts for circuit-PSI mainly focus on the case where input set sizes |X| and |Y| are similar so far, and they scale poorly for extremely unbalanced set sizes |X| ≫ |Y|. Recently, Lepoint et al. (ASIACRYPT’21) proposed the first dedicated solutions for this problem, which has online cost only linear in the small set size |Y|. However, it requires an expensive setup phase that requires huge storage of about O(|X|) on the small set holder side, which can be problematic in applications where the small set holder is assumed to have restricted equipment.
In this work, we suggest new efficient proposals for circuit-PSI tailored for unbalanced inputs, which feature zero small set holder side storage, and comparable online phase performance to the previous work. At the technical core, we use homomorphic encryption (HE) based plain PSI protocols of Cong et al. (CCS’21), with several technically non-trivial arguments on algorithm and security.
We demonstrate the superiority of our proposals in several input set sizes by an implementation. As a representative example, for input sets of size 224 and 212, our proposals require zero storage on the small set holder whereas Lepoint et al. requires over 7GB. The online phase remains similar; over LAN network setting, ours takes 7.5 (or 20.9s) seconds with 45MB (or 11.7MB) communication, while Lepoint et al. requires 4.2 seconds with 117MB communication.