Anti-collusion multi-party private set union protocol in low-bandwidth scenarios

ZHANG En; WANG Mengtao; ZHENG Dong; YU Yong; HUANG Yuchen

doi:10.11959/j.issn.1000-436x.2025020

您当前的位置：

首页 >

文章列表页 >

Anti-collusion multi-party private set union protocol in low-bandwidth scenarios

Correspondences | 更新时间：2025-02-13

- Anti-collusion multi-party private set union protocol in low-bandwidth scenarios
- Journal on Communications Vol. 46, Issue 1, Pages: 210-221(2025)
- 作者机构：
  
  1.河南师范大学计算机与信息工程学院，河南新乡 453007
  2.河南省教育人工智能与个性化学习重点实验室，河南新乡 453007
  3.西安邮电大学无线网络安全技术国家工程实验室，陕西西安 710061
  4.陕西师范大学计算机科学学院，陕西西安 710062
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-436x.2025020
  CLC： TP309
- Received：03 September 2024，
  
  Revised：2025-01-06，
  
  Published：25 January 2025
- 稿件说明：
移动端阅览
张恩,王梦涛,郑东等.低带宽场景下防合谋多方隐私集合并集协议[J].通信学报,2025,46(01):210-221.

ZHANG En,WANG Mengtao,ZHENG Dong,et al.Anti-collusion multi-party private set union protocol in low-bandwidth scenarios[J].Journal on Communications,2025,46(01):210-221.
张恩,王梦涛,郑东等.低带宽场景下防合谋多方隐私集合并集协议[J].通信学报,2025,46(01):210-221. DOI： 10.11959/j.issn.1000-436x.2025020.

ZHANG En,WANG Mengtao,ZHENG Dong,et al.Anti-collusion multi-party private set union protocol in low-bandwidth scenarios[J].Journal on Communications,2025,46(01):210-221. DOI： 10.11959/j.issn.1000-436x.2025020.

摘要

针对现存的多方隐私集合并集（MPSU）协议存在交互轮数多以及通信开销大等问题，使其无法在低带宽场景中得以有效应用，设计了一种基于不经意键值存储和门限同态加密技术的不经意匹配置换方法，并运用该方法提出了一种半诚实模型下的多方隐私集合并集协议。该协议允许

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391468&type=

2.28600001

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391456&type=

2.53999996

个参与方共同计算所有集合的并集，且不会泄露任何其他的信息，具有通信轮数少、能抵御

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391457&type=

2.28600001

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391473&type=

7.70466709

个参与方的合谋、通信开销低等优势，比现有最先进的多方隐私集合并集的通信开销降低了65%左右。

Abstract

Aiming at the problems of the existing multi-party private set union (MPSU) protocols

such as a large number of interaction rounds and excessive communication overhead

which prevented them from being effectively applied in low-bandwidth scenarios

an oblivious matching permutation method based on oblivious key-value store and threshold homomorphic encryption technologies was designed

and a multi-party private set union protocol under a semi-honest model was proposed through this method. This protocol allowed

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391474&type=

2.28600001

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391472&type=

2.53999996

participants to jointly calculate the union of all sets and would not leak any other information. It mainly has the advantages of a small number of communication rounds

the ability to resist the collusion of

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391488&type=

2.28600001

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=73391489&type=

7.70466709

participants

and low communication overhead. Its communication overhead is reduced by about 65% compared to the existing most advanced multi-party private set union.

关键词

Keywords

references

HOGAN K , LUTHER N , SCHEAR N , et al . Secure multiparty computation for cooperative cyber risk assessment [C ] // Proceedings of the 2016 IEEE Cybersecurity Development (SecDev) . Piscataway : IEEE Press , 2016 : 75 - 76 .

RAMANATHAN S , MIRKOVIC J , YU M L . BLAG: improving the accuracy of blacklists [C ] // Proceedings of 2020 Network and Distributed System Security Symposium . Piscataway : IEEE Press , 2020 : 1 - 6 .

ZHANG C , CHEN Y , LIU W R , et al . Linear private set union from multi-query reverse private membership test [C ] // Proceedings of the 32nd USENIX Conference on Security Symposium . Berkeley : USENIX Association , 2023 : 337 - 354 .

KOLESNIKOV V , KUMARESAN R , ROSULEK M , et al . Efficient batched oblivious PRF with applications to private set intersection [C ] // Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2016 : 818 - 829 .

PINKAS B , SCHNEIDER T , ZOHNER M . Faster private set intersection based on OT extension [C ] // Proceedings of the 23rd USENIX Conference on Security Symposium . Berkeley : USENIX Association , 2014 : 797 - 812 .

PINKAS B , SCHNEIDER T , SEGEV G , et al . Phasing: private set intersection using permutation-based hashing [C ] // Proceedings of the 24th USENIX Conference on Security Symposium . Berkeley : USENIX Association , 2015 : 515 - 530 .

RINDAL P , ROSULEK M . Malicious-secure private set intersection via dual execution [C ] // Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2017 : 1229 - 1242 .

PINKAS B , ROSULEK M , TRIEU N , et al . SpOT-light: lightweight private set intersection from sparse OT extension [C ] // Advances in Cryptology- CRYPTO 2019 . Berlin : Springer , 2019 : 401 - 431 .

张恩 , 耿魁 , 金伟 , 等 . 抗隐蔽敌手的云外包秘密共享方案 [J ] . 通信学报 , 2017 , 38 ( 5 ): 57 - 65 .

ZHANG E , GENG K , JIN W , et al . Cloud outsourcing secret sharing scheme against covert adversaries [J ] . Journal on Communications , 2017 , 38 ( 5 ): 57 - 65 .

PINKAS B , ROSULEK M , TRIEU N , et al . PSI from PaXoS: fast, malicious private set intersection [C ] // Advances in Cryptology-EUROCRYPT 2020 . Berlin : Springer , 2020 : 739 - 767 .

CHASE M , MIAO P H . Private set intersection in the Internet setting from lightweight oblivious PRF [C ] // Advances in Cryptology-CRYPTO 2020 . Berlin : Springer , 2020 : 34 - 63 .

RINDAL P , SCHOPPMANN P . VOLE-PSI: fast OPRF and circuit-PSI from vector-OLE [C ] // Advances in Cryptology-EUROCRYPT 2021 . Berlin : Springer , 2021 : 901 - 930 .

GARIMELLA G , PINKAS B , ROSULEK M , et al . Oblivious key-value stores and amplification for private set intersection [C ] // Advances in Cryptology-CRYPTO 2021 . Berlin : Springer , 2021 : 395 - 425 .

RAGHURAMAN S , RINDAL P , RAGHURAMAN S , et al . Blazing fast PSI from improved OKVS and subfield VOLE [C ] // Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2022 : 2505 - 2517 .

魏立斐 , 王勤 , 张蕾 , 等 . 半可信云服务器辅助的高效隐私交集计算协议 [J ] . 软件学报 , 2023 , 34 ( 2 ): 932 - 944 .

WEI L F , WANG Q , ZHANG L , et al . Efficient private set intersection protocols with semi-trusted cloud server aided [J ] . Journal of Software , 2023 , 34 ( 2 ): 932 - 944 .

ISHAI Y , KILIAN J , NISSIM K , et al . Extending oblivious transfers efficiently [C ] // Advances in Cryptology-CRYPTO 2003 . Berlin : Springer , 2003 : 145 - 161 .

COUTEAU G , RINDAL P , RAGHURAMAN S . Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes [C ] // Advances in Cryptology-CRYPTO 2021 . Berlin : Springer , 2021 : 502 - 534 .

张蕾 , 贺崇德 , 魏立斐 . 高效且恶意安全的三方小集合隐私交集计算协议 [J ] . 计算机研究与发展 , 2022 , 59 ( 10 ): 2286 - 2298 .

ZHANG L , HE C D , WEI L F . Efficient and malicious secure three-party private set intersection computation protocols for small sets [J ] . Journal of Computer Research and Development , 2022 , 59 ( 10 ): 2286 - 2298 .

张恩 , 裴瑶瑶 , 杜蛟 . 基于RLWE的密文策略属性代理重加密 [J ] . 通信学报 , 2018 , 39 ( 11 ): 129 - 137 .

ZHANG E , PEI Y Y , DU J . RLWE-based ciphertext-policy attribute proxy re-encryption [J ] . Journal on Communications , 2018 , 39 ( 11 ): 129 - 137 .

宋祥福 , 盖敏 , 赵圣楠 , 等 . 面向集合计算的隐私保护统计协议 [J ] . 计算机研究与发展 , 2020 , 57 ( 10 ): 2221 - 2231 .

SONG X F , GAI M , ZHAO S N , et al . Privacy-preserving statistics protocol for set-based computation [J ] . Journal of Computer Research and Development , 2020 , 57 ( 10 ): 2221 - 2231 .

KOLESNIKOV V , MATANIA N , PINKAS B , et al . Practical multi-party private set intersection from symmetric-key techniques [C ] // Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2017 : 1257 - 1272 .

ZHANG E , LIU F H , LAI Q Q , et al . Efficient multi-party private set intersection against malicious adversaries [C ] // Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop . New York : ACM Press , 2019 : 93 - 104 .

NEVO O , TRIEU N , YANAI A . Simple, fast malicious multiparty private set intersection [C ] // Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2021 : 1151 - 1165 .

张恩 , 秦磊勇 , 杨刃林 , 等 . 基于弹性秘密共享的多方门限隐私集合交集协议 [J ] . 软件学报 , 2023 , 34 ( 11 ): 5424 - 5441 .

ZHANG E , QIN L Y , YANG R L , et al . Multi-party threshold private set intersection protocol based on robust secret sharing [J ] . Journal of Software , 2023 , 34 ( 11 ): 5424 - 5441 .

魏立斐 , 刘纪海 , 张蕾 , 等 . 双云辅助的超阈值多方隐私集合交集计算协议 [J ] . 软件学报 , 2023 , 34 ( 11 ): 5442 - 5456 .

WEI L F , LIU J H , ZHANG L , et al . Two cloud-assisted over-threshold multi-party private set intersection calculation protocol [J ] . Journal of Software , 2023 , 34 ( 11 ): 5442 - 5456 .

LIU F H , ZHANG E , QIN L Y . Efficient multiparty probabilistic threshold private set intersection [C ] // Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2023 : 2188 - 2201 .

FENSKE E , MANI A , JOHNSON A , et al . Distributed measurement with private set-union cardinality [C ] // Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2017 : 2295 - 2312 .

DONG C Y , LOUKIDES G . Approximating private set union/intersection cardinality with logarithmic complexity [J ] . IEEE Transactions on Information Forensics and Security , 2017 , 12 ( 11 ): 2792 - 2806 .

BLANTON M , AGUIAR E . Private and oblivious set and multiset operations [J ] . International Journal of Information Security , 2016 , 15 ( 5 ): 493 - 518 .

KOLESNIKOV V , ROSULEK M , TRIEU N , et al . Scalable private set union from symmetric-key techniques [C ] // Advances in Cryptology-ASIACRYPT 2019 . Berlin : Springer , 2019 : 636 - 666 .

GARIMELLA G , MOHASSEL P , ROSULEK M , et al . Private set operations from oblivious switching [C ] // Public-Key Cryptography-PKC 2021 . Berlin : Springer , 2021 : 591 - 617 .

JIA Y X , SUN S F , ZHOU H S , et al . Shuffle-based private set union: faster and more secure [C ] // 31st USENIX Security Symposium . Berkeley : USENIX Association , 2022 : 2947 - 2964 .

TU B B , CHEN Y , LIU Q , et al . Fast unbalanced private set union from fully homomorphic encryption [C ] // Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2023 : 2959 - 2973 .

HAZAY C , NISSIM K . Efficient set operations in the presence of malicious adversaries [J ] . Journal of Cryptology , 2012 , 25 ( 3 ): 383 - 433 .

MANY D , BURKHART M , DIMITROPOULOS X . Fast private set operations with SEPIA [R ] . 2012 .

DAVIDSON A , CID C . An efficient toolkit for computing private set operations [C ] // Information Security and Privacy . Berlin : Springer , 2017 : 261 - 278 .

CANETTI R , PANETH O , PAPADOPOULOS D , et al . Verifiable set operations over outsourced databases [C ] // Public-Key Cryptography-PKC 2014 . Berlin : Springer , 2014 : 113 - 130 .

SHISHIDO K , MIYAJI A . Efficient and quasi-accurate multiparty private set union [C ] // Proceedings of the 2018 IEEE International Conference on Smart Computing (SMARTCOMP) . Piscataway : IEEE Press , 2018 : 309 - 314 .

KISSNER L , SONG D . Privacy-preserving set operations [C ] // Advances in Cryptology-CRYPTO 2005 . Berlin : Springer , 2005 : 241 - 257 .

FRIKKEN K . Privacy-preserving set union [C ] // Applied Cryptography and Network Security . Berlin : Springer , 2007 : 237 - 252 .

HONG J , KIM J W , KIM J , et al . Constant-round privacy preserving multiset union [J ] . Bulletin of the Korean Mathematical Society , 2013 , 50 ( 6 ): 1799 - 1816 .

SEO J H , CHEON J H , KATZ J . Constant-round multi-party private set union using reversed Laurent series [C ] // Public Key Cryptography-PKC 2012 . Berlin : Springer , 2012 : 398 - 412 .

GONG X H , HUA Q S , JIN H . Nearly optimal protocols for computing multi-party private set union [C ] // Proceedings of the 2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS) . Piscataway : IEEE Press , 2022 : 1 - 10 .

LIU X , GAO Y . Scalable multi-party private set union from multi-query secret-shared private membership test [C ] // Advances in Cryptology- ASIACRYPT 2023 . Singapore : Springer , 2023 : 237 - 271 .

DONG M L , CHEN Y , ZHANG C , et al . Breaking free: efficient multi-party private set union without non-collusion assumptions [J ] . arXiv Preprint , arXiv: 2406.07011 , 2024 .

BADAWI A A , BATES J , BERGAMASCHI F , et al . OpenFHE: open-source fully homomorphic encryption library [C ] // Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography . New York : ACM Press , 2022 : 53 - 63 .

ASHAROV G , JAIN A , LÓPEZ-ALT A , et al . Multiparty computation with low communication, computation and interaction via threshold FHE [C ] // Advances in Cryptology-EUROCRYPT 2012 . Berlin : Springer , 2012 : 483 - 501 .

Views

942

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on efficient and scalable private set intersection cardinality schemes

Adaptive federated learning secure aggregation scheme based on threshold homomorphic encryption

Related Author

LI Gongli

LIU Weichen

ZHENG Dong

Zhuo MA

Jiayu JIN

Yilong YANG

Yang LIU

Zuobin YING

Related Institution

School of Computer and Information Engineering, Henan Normal University

School of Cyberspace Security, Xi’an University of Posts and Telecommunications

School of Cyber Engineering, Xidian University

Faculty of Data Science, City University of Macau, Macau

AI问答

⁰