PSI with computation or Circuit-PSI for Unbalanced Sets from Homomorphic Encryption
Yongha Son, Jinhyuck Jeong
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.