Malicious-Secure Threshold Multi-Party Private Set Intersection for Anonymous Electronic Voting

Threshold Multi-Party Private Set Intersection (TMP-PSI) is a cryptographic protocol that enables an element from the receiver’s set to be included in the intersection result if it appears in the sets of at least t−1 other participants, where t represents the threshold. This protocol is crucial for a variety of applications, such as anonymous electronic voting, online ride-sharing, and close-contact tracing programs. However, most existing TMP-PSI schemes are designed based on threshold homomorphic encryption, which faces significant challenges, including low computational efficiency and a high number of communication rounds. To overcome these limitations, this study introduces the Threshold Oblivious Pseudo-Random Function (tOPRF) to fulfill the requirements of threshold encryption and decryption. Additionally, we extend the concept of the Oblivious Programmable Pseudo-Random Function (OPPRF) to develop a novel cryptographic primitive termed the Partially OPPRF (P-OPPRF). This new primitive retains the critical properties of obliviousness and randomness, along with the security assurances inherited from the OPPRF, while also offering strong resistance against malicious adversaries. Leveraging this primitive, we propose the first malicious-secure TMP-PSI protocol, named QMP-PSI, specifically designed for applications like anonymous electronic voting systems. The protocol effectively counters collusion attacks among multiple parties, ensuring robust security in multi-party environments. To further enhance voting efficiency, this work presents a cloud-assisted QMP-PSI to outsource the computationally intensive phases. This ensures that the computational overhead for participants is solely dependent on the set size and statistical security parameters, thereby maintaining security while significantly reducing the computational burden on voting participants. Finally, this work validates the protocol’s performance through extensive experiments under various set sizes, participant numbers, and threshold values. The results demonstrate that the protocol surpasses existing schemes, achieving state-of-the-art (SOTA) performance in communication overhead. Notably, in small-scale voting scenarios, it exhibits exceptional performance, particularly when the threshold is small or close to the number of participants.