高效的隐私保护多方多数据排序  

Towards Efficient Privacy-Preserving Multi-Party Multi-Data Sorting

作　　者：商帅 李雄 张文琪[1] 汪小芬[1] 李哲涛 张小松 SHANG Shuai;LI Xiong;ZHANG Wen-Qi;WANG Xiao-Fen;LI Zhe-Tao;ZHANG Xiao-Song(College of Computer Science and Engineering(College of Cyber Security),University of Electronic Science and Technology of China,Chengdu 611731;Key Laboratory of Data Protection and Intelligent Management,Ministry of Education,Sichuan University,Chengdu 610065;Shenzhen Institute for Advanced Study,University of Electronic Science and Technology of China,Shenzhen,Guangdong 518110;National&Local Joint Engineering Research Center of Network Security Detection and Protection Technology,Jinan University,Guangzhou 510632;Guangdong Provincial Key Laboratory of Data Security and Privacy Protection,Jinan University,Guangzhou 510632;College of Information Science and Technology,Jinan University,Guangzhou 510632)

机构地区：[1]电子科技大学计算机科学与工程学院(网络空间安全学院),成都611731 [2]四川大学数据安全防护与智能治理教育部重点实验室,成都610065 [3]电子科技大学(深圳)高等研究院,广东深圳518110 [4]暨南大学网络安全检测与防护国家地方联合工程研究中心,广州510632 [5]暨南大学数据安全与隐私保护广东省重点实验室,广州510632 [6]暨南大学信息科学技术学院,广州510632

出　　处：《计算机学报》2024年第8期1832-1852,共21页Chinese Journal of Computers

基　　金：国家自然基金项目(重点项目62332018,面上项目62072078和62271128);四川省自然科学基金面上项目(2022NSFSC0550);四川大学数据安全防护与智能治理教育部重点实验室开放课题(SCUSAKFKT202303Z)的资助。

摘　　要：安全多方计算允许具有私密输入的多个参与方联合计算一个多输入函数而不泄露各参与方私有输入的任何信息,因此近年来受到广泛关注.作为安全多方计算中的一个基础问题,隐私保护排序允许多个参与方在不泄露数据集隐私的前提下计算多个数据集的排序结果,广泛应用于产品定价、拍卖等场景.现有的隐私保护排序协议大多只支持两个参与方.而已有的多方多数据排序协议通信开销大、计算复杂度高,整体效率较低.现有隐私保护排序协议均未考虑恶意参与者的穷举攻击,因此安全保护不足.对此,本文提出一个高效的隐私保护多方多数据排序协议.多个参与方仅需O(1)轮交互即可以隐私保护的方式获得其持有的多个数据的排序结果.具体来讲,本文设计一种基于多项式的编码方法,将参与方的数据集编码为一个多项式,其每项的指数和系数分别代表数据和该数据的个数.通过多项式加法可实现多个参与方数据集的排序.同时,本文设计了多项式加密、聚合多项式生成和解密多项式生成算法,在保证计算正确性的同时实现多项式的隐私保护.最后,各参与方通过不经意传输技术获得排序结果.本文定义了不合谋参与方穷举攻击下的恶意安全.安全性分析表明本文协议不仅实现了半诚实安全性,而且达到了不合谋恶意用户穷举攻击的恶意安全性.此外,大量实验表明本文提出的协议在通信和计算方面都十分高效.如当参与方数量为15、每个参与方持有20000个数据、数据上界为500000时,本文协议的通信和计算开销分别为898.44 MB和69.76 s,仅为LDYW协议的12.08%和76.85%;而相对于AHM+方案,本文协议在通信开销仅增加约4倍的情况下使计算效率提升了约20倍.In recent years,secure multi-party computation has received extensive attention in academia and industry.Secure multi-party computation allows multiple participants with private inputs to jointly compute a multi-input function without revealing any information about the private inputs of each participant,which makes the data available but invisible.As a fundamental problem in secure multi-party computation,privacy-preserving sorting allows multiple participants to compute the joint sorting result of multiple datasets without disclosing the privacy of the datasets and the sorting result,which has a wide range of application needs and values,such as product pricing,auctions,interest recommendations.Most of the existing privacy-preserving sorting protocols only support two participants,and cannot meet the joint sorting requirements of multiple participants in practical scenarios.The existing multi-party multi-data sorting protocols have the problems of high communication overhead,high computational complexity.As a result,they all suffer low overall efficiency.At the same time,the existing privacy-preserving sorting protocols do not consider the malicious security model of exhaustive attacks by malicious participants,and only realize security under the semi-honest adversary model,thus providing insufficient security protection against the more realistic malicious adversary model.In this paper,we propose an efficient privacy-preserving multi-party multi-data sorting protocol to overcome the above problems.Through this protocol,multiple participants can collectively compute the sorting results of their data in a privacy-preserving way with only O(1)rounds of interaction.Specifically,this paper designs a polynomial-based encoding method that encodes a participant´s dataset as a polynomial.In such a polynomial,the exponent and coefficient represent the data and the number of the data,respectively.Therefore,the sorting of multiple participant datasets can be realized by polynomial addition.For the above polynomial-based

关 键 词：隐私计算 安全多方排序 安全数据分析 隐私保护 排序 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]