An Efficient PSI Protocol with Linear Communication Complexity
摘要
Privacy Set Intersection (PSI), a core cryptographic primitive for secure multi-party computation, allows participants to compute dataset intersections without revealing non-intersecting elements, which is valuable in privacy-preserving scenarios, such as healthcare data sharing and federated learning parameter alignment. However, existing schemes have significant tradeoffs between security, efficiency, and scalability. In this paper, we propose a hybrid cryptography PSI protocol for semi-honest models, which fuses Paillier homomorphic encryption, Elliptic Curve Diffie-Hellman (ECDH) key exchange, and hash matrix compression coding techniques, to enhance the security of plain hashing and make it difficult for adversaries to obtain information beyond the intersection through a simple collision attack, linear communication complexity is realized, and the experiments show that the communication volume is stable at 255.5 KB at the scale of \(2^{10}\) and linearly related to the size of the dataset. Furthermore, we provide a formal security proof demonstrating that the protocol satisfies privacy guarantees under the semi-honest model.