Practical Private Intersection-Sum Protocols with Good Scalability

Private intersection-sum (PI-Sum) enables participants to compute the sum of data associated with the intersection without revealing any personal information. It has been a research focus of secure multi-party computation, particularly valuable for a business application: attributing aggregate ad conversions. Most PI-Sum research based on Decisional Diffie-Hellman (DDH) assumptions and techniques such as garbled circuits. They rely on modular exponentiation operations and frequent interactions between participants, resulting in high computational overhead and lack of scalability within practical applications. In this paper, we design two practical PI-Sum protocols with different set domains. Specifically, we convert private sets into the bit-set representation and bloom filters. Then, we encrypt them with elliptic curves (ECC) Threshold ElGamal and Paillier algorithms. Through simulation paradigms and theoretical analysis, it is proved that the efficiency of our protocols are higher than those of the available protocols. Finally, we demonstrate the scalability of our PI-Sum protocols to multi-party private intersection-sum (MPI-Sum).