Efficient private set intersection-sum with cardinality based on differential private load overestimation mechanism
Cong Wang, Ou Ruan · 2024
Private set intersection (PSI) allows two parties to compute the common items of their input sets, without leaking other irrelevant information. In some practical applications, it is very useful, and many researches have been conducted. However, this does not meet the requirement that we not only need to compute the cardinality of the intersection but also calculate the sum of the correlation values. In this work, we propose a new intersection-sum with cardinality protocol based on a variant of the ElGamal cryptosystem and the load overestimation mechanism to solve this problem, with the load overestimation mechanism, if a certain degree of differential privacy leakage is allowed, the efficiency can be greatly improved, it is very useful when the set becomes larger. we first hash items into bins respectively and pad some dummy items to hide the information of bins, then the calculations are conducted in each bin. In the semi-honest scenario, we use the simulation paradigm to prove the security of our protocol. We conduct comprehensive experiments to compare the efficiency of our protocol with the related protocol, our protocol does not require both parties to have high computational capabilities, and for larger set sizes, our protocol has a lower runtime and holds a greater advantage.