Third-party private set intersection (PSI) allows two parties to compute the intersection of their private input sets without revealing any more information than the result to an inputless third party. In this work, we leverage homomorphic encryption and oblivious pseudorandom function techniques for the first time to design third-party PSI protocols. We present two highly efficient third-party PSI protocols characterized by linear communication and computational complexity, along with a requirement of only 2 communication rounds. These protocols significantly lower the computational workload compared to prior work. Furthermore, we extend our investigation to third-party PSI cardinality protocols. Our constructions to achieve the cardinality functionality attain linear communication and computational complexity. Finally, we implement our protocols in C++ and perform a comprehensive evaluation, an aspect previously unexplored in third-party PSI research. The results demonstrate that our OPRF-based third-party PSI can obtain a 4.6–13.78 times faster improvement over the HE-based third-party PSI with a single thread in LAN setting. Moreover, the results indicate that our OPRF-based third-party PSI will yield even greater improvements as the set size increases, compared to HE-based third-party PSI.

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

An Efficient Toolkit for Computing Third-Party Private Set Intersection

  • Kai Chen,
  • Yongqiang Li,
  • Mingsheng Wang

摘要

Third-party private set intersection (PSI) allows two parties to compute the intersection of their private input sets without revealing any more information than the result to an inputless third party. In this work, we leverage homomorphic encryption and oblivious pseudorandom function techniques for the first time to design third-party PSI protocols. We present two highly efficient third-party PSI protocols characterized by linear communication and computational complexity, along with a requirement of only 2 communication rounds. These protocols significantly lower the computational workload compared to prior work. Furthermore, we extend our investigation to third-party PSI cardinality protocols. Our constructions to achieve the cardinality functionality attain linear communication and computational complexity. Finally, we implement our protocols in C++ and perform a comprehensive evaluation, an aspect previously unexplored in third-party PSI research. The results demonstrate that our OPRF-based third-party PSI can obtain a 4.6–13.78 times faster improvement over the HE-based third-party PSI with a single thread in LAN setting. Moreover, the results indicate that our OPRF-based third-party PSI will yield even greater improvements as the set size increases, compared to HE-based third-party PSI.