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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Efficient PSI Protocol with Linear Communication Complexity

  • Shuai Yang,
  • Bowei Chen,
  • Yiliang Han

摘要

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.