分布式多重集众数及重数的保密计算_家珠亮.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):102117密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618分布式多重集众数及重数的保密计算*家珠亮,赵雪玲,李顺东陕西师范大学 计算机科学学院,西安 710119通信作者:李顺东,E-mail:摘要:安全多方计算作为联合计算中隐私保护的核心技术,为许多不同的隐私保护问题提供了解决方案,目前关于多重集的众数及重数保密计算问题的研究很少.本文设计了一种新的编码方案,利用这种新的编码方案和 ElGamal 门限密码系统解决分布式多重集众数与重数的保密计算问题.针对多重集是由多个参与者的单个隐私数据构成的情况,设计了一个众数及重数的保密计算协议,阈值众数保密计算协议和元素重数大于阈值的保密计算协议.通过对编码方案的调整,进一步针对多重集是由多个参与者的多重集构成的情况,设计了多重集的并集的众数与重数的保密计算协议.用广泛接受的模拟范例证明了协议在半诚实模型下是安全的.理论分析和实验结果证明本文协议简单高效.关键词:安全多方计算;密码学;分布式多重集;众数;重数;同态加密;编码方法中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000582中文引用格式:家珠亮,赵雪玲,李顺东.分布式多重集众数及重数的保密计算J.密码学报,2023,10(1):102117.DOI:10.13868/ki.jcr.000582英文引用格式:JIA Z L,ZHAO X L,LI S D.Secure distributed multisets mode and multiplicity computa-tionJ.Journal of Cryptologic Research,2023,10(1):102117.DOI:10.13868/ki.jcr.000582Secure Distributed Multisets Mode and Multiplicity ComputationJIA Zhu-Liang,ZHAO Xue-Ling,LI Shun-DongSchool of Computer Science,Shaanxi Normal University,Xian 710119,ChinaCorresponding author:LI Shun-Dong,E-mail:Abstract:In recent years,SMC provides solutions to many different privacy preserving problems.However,there are still many problems need to be solved.There are very few results on SMC ofmode and multiplicity of private multisets.As a consequence,it is of great significance to study thesecure mode and multiplicity computation of distributed multiset.This paper designs a new codingscheme and uses this new coding scheme and ElGamal cryptosystem to solve the problem of privacypreserving mode and multiplicity computation.First of all,for the case where the multiset is a data setof multiple participants single private data,a secure mode and a multiplicity computation protocol,aswell as a secure threshold mode computation protocol and a secure element with multiplicity greaterthan a threshold value computation protocol are designed.Adjusting these protocols,for the casewhere the multiset is a set of multiple participants private multiset,a secure mode and multiplicitycomputation protocol for the union of the multisets is designed.The widely accepted simulation*基金项目:国家自然科学基金(61272435)Foundation:National Natural Science Foundation of China(61272435)收稿日期:2021-12-30定稿日期:2022-03-09家珠亮 等:分布式多重集众数及重数的保密计算103paradigm is used to prove the security of these protocols under the semi-honest model.Theoreticalanalysis and experimental results show that these protocols are simple and efficient.Key words:secure multiparty computation;cryptography;distributed multiset;mode;multiplicity;homomorphic encryption;encoding scheme1引言随着时代的发展与科技的不断进步,信息交互更加便捷与智能,随之而来的信息隐私泄露越来越严重,隐私保护问题受到越来越多的关注.隐私保护的迫切需求推动安全多方计算(secure multiparty compu-tation,SMC)发展成为国际密码学界研究的重点问题,成为解决隐私保护问题的强有力工具14.安全多方计算是指一组互不信任的参与者通过协同计算解决某一问题,计算完成后,各方参与者除了得到预先规定的输出结果外,不能获得其余参与者的任何其他隐私信息.两方安全计算问题在 1982 年首次被 Yao 提出5,不久后 Goldwasser 等人提出了多方安全计算问题6.目前安全多方计算已被应用于解决许多实际应用中的隐私保护问题,如保密的科学计算79、保密的统计分析10,11、保密的数据库查询1214以及其他安全多方计算问题1519等.多重集是指允许元素重复出现的集合,在实际生活中有着广泛的应用.为了避免混淆,本文中将不允许出现重复元素的集合称为标准集.分布式多重集是指该多重集的数据由不同参与者的数据共同组成,多重集中的元素分散在不同参与者处,他们可以通过合作利用整个多重集的数据.一个元素在多重集里出现的次数称为这个元素在多重集里面的重数.多重集的每一个元素都有一个重数,所有元素的重数的最大值定义为多重集的重数,重数最大的元素称为众数.统计学中,众数和重数往往结合使用,在人们生产生活中更是如此.如在森林野生生物环境适应性研究中,统计出适应性最好的生物种类的同时需要标注出其对应生物量,以便后续相关研究工作的开展.再如商场产品销量调研中,不仅要知道哪些产品的销量最好,还需要知道销量最好的产品的销售量,才能更科学合理地储备产品,实现利益最大化.因此,无论是在统计学研究还是实际应用中,对多重集众数及重数的研究都有很大意义.随着信息时代的来临,隐私数据泄露给人们带来的威胁和伤害越来越大,许多时候对众数及重数的计算需要保密进行.多重集众数及重数的保密计算在保密确定企业优势产品、保密选举、保密投票等实际生活方面有着重要应用.以投票选举为例,投票选举中常用的众数及重数的保密计算场景有:(1)每人投一票,票数最高者获胜就是保密确定多重集的众数与重数;(2)每人投一票,票数最高且过半(或某一阈值th)者胜选,否则选举无效、重新选举,这就是保密确定多重集的阈值众数;(3)每人有 a(a 1)票,最多可以投给 a 个心仪的选手,也可以把所有票都投给同一人,最终选票大于某阈值 th 数的选手可以成功进入下一轮比赛,否则淘汰,这就是保密确定多重集的并集中重数大于阈值 th 的成员.保密投票无论是在社区代表选举、投票决定晋级选手中,还是在投票决定新律法是否通过、国际事务投票抉择等各类事件中,都可以减少恶意竞争,减少多轮晋级投票制中选手故意伤害有力对手等事件的发生,使得竞争环境更加公平和谐.常见的阈值众数保密计算场景还有很多,如保密确定某些网站受到的最多的攻击,或者多于某个阈值 th 的攻击等.因此,对多重集众数及重数的保密计算具有重要意义.目前国内外关于标准集的保密计算研究很多2024,关于多重集的保密计算研究还很少25,26.据我们所知,目前还没有见到多重集众数保密计算的研究.针对目前的研究现状以及实际应用的需要,本文研究设计了多重集众数及重数的保密计算协议,主要贡献如下:(1)提出并研究了分布式多重集的保密计算的新问题,即多重集众数及重数的保密计算问题.拓展了保密计算集合问题的研究内容;(2)提出了多重集众数及重数的新编码方法.首先依据参与者的数据编码一个矩阵,然后各参与者通过对矩阵某行向量进行移位操作来记录自己的数据情况,使得问题得到解决.这种编码很容易用密码学方法保密实现,为其他保密计算问题提供了新的解决思路;(3)结合 ElGamal 门限密码系统,针对多个参与者的单个隐私数据组成的分布式多重集,设计了保密计算多重集众数及重数协议,众数大于某个阈值的保密计算协议,以及元素重数大于某个阈值的104Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023保密计算协议,对协议的正确性及安全性进行了严格证明;(4)对新编码方法进行稍微修改,可以解决求多个多重集的众数的问题,设计了分布式多重集保密求众数及重数协议;并说明了有阈值设定情况下保密求分布式多重集众数协议,元素重数大于阈值协议的设计方法.2预备知识2.1半诚实模型及其安全性定义半诚实参与者27在协议过程中严格按照要求执行协议,但在协议结束后有可能利用已获得的信息推导其他参与者的私密数据的额外信息.若协议的参与者都是半诚实的,则称该模型为半诚实模型.假设 n 个参与者 Pi(i 1,n)分别拥有私密数据 xi,记 X=(x1,x2,xn).设 f(X)=(f1(X),f2(X),fn(X)是概率多项式函数,表示计算函数 f 的多方协议.在 n 个参与者共同执行协议 的过程中,Pi得到信息序列记为 viewi(X)=(xi,ri,m1i,m2i,mai,fi(X).其中 ri表示 Pi产生的随机数,mhi(h 1,a)表示 Pi收到的信息,fi(X)是 Pi得到的计算结果.若对于任意参与者 I=P,P()P1,P2,Pn,都存在概率多项式时间算法 S(即模拟器)使得下式成立:S(I,(x,x),fI(X)Xc viewI(X)X.(1)则称协议 保密计算函数 f.其中,viewI(X)=(I,view(X),view(X),fI(X),符号c 表示计算不可区分.通过构造满足式(1)的模拟器证明半诚实模型下协议的安全性的方法称为模拟范例方法.本文所有协议的安全性采用该方法证明.2.2ElGamal 门限密码系统在有 n 个参与者的门限密码系统中,参与者各自选取自己