基于弹性秘密共享的多方洗牌协议.pdf

学术论文DOl:10.12379/j.issn.2096-1057.2024.04.09ResearchPapers基于弹性秘密共享的多方洗牌协议满子琪张艳硕严梓洋罗乐琦（北京电子科技学院北京10 0 0 7 0)()Multi-party Shuffling Protocol Based on Elastic Secret SharingMan Ziqi,Zhang Yanshuo,Yan Ziyang,Luo Leqi,and Chen Ying(Beijing Electronic Science and Technology Institute,Beijing 100070)Abstract In order to promote data privacy protection,this paper proposes a multi-party shufflingprotocol based on elastic secret sharing,which mainly adopts the intersection computingtechnology of elastic secret sharing,shuffling protocol and privacy set.In this paper,we firstlygive a brief introduction to the multi-party shuffling protocol based on elastic secret sharing and itsrelated technologies,then construct the model and framework.and propose the design scheme ofmulti-party shuffling protocol based on elastic secret sharing.Meanwhile,this paper analyses thecorrectness,security,performance and prospect of the protocol in details.Through the proofs ofrelevant theorems and comparative analysis with some schemes,this protocol has higher efficiencyand better security.Key words elastic secret sharing;shuffling protocol;privacy set intersection computing;privacyprotection;cryptography摘要为了促进对数据隐私的保护，提出了一种基于弹性秘密共享的多方洗牌协议，主要采用了弹性秘密共享、洗牌协议与隐私集合交集计算技术.首先对基于弹性秘密共享的多方洗牌协议及其相关技术进行了简要的介绍，紧接着对模型、框架进行了构建，并提出了基于弹性秘密共享的多方洗牌协议的设计方案.同时，对该协议的正确性、安全性、性能、应用前景进行了详细分析.通过有关定理的证明以及与一些方案的对比分析，该协议具有较高的效率以及较好的安全性。关键词弹性秘密共享；洗牌协议；隐私集合交集计算；隐私保护；密码学中图法分类号TP309数据隐私保护 1问题已成为学术界关注的热点.洗牌协议 2 是旨在实现安全随机排列的协议，其将输入的数据打乱以保证数据隐私.秘密共享技术3是一种秘密保护技术，其将秘密份额分发并设置恢复秘密的门限值.收稿日期：2 0 2 3-0 8-2 0基金项目：国家自然科学基金项目（6 2 0 0 2 0 0 3）；2 0 2 2 年基本科研业务费优硕培养项目（32 8 2 0 2 2 2 8)通信作者：陈颖（ychenbesti.edu）引用格式：满子琪，张艳硕，严梓洋，等.基于弹性秘密共享的多方洗牌协议 J.信息安全研究，2 0 2 4，10（4）：347-352奇陈颖基于弹性秘密共享的多方洗牌协议的主要思想为：弹性秘密共享技术将数据集拆分成多个份额，洗牌协议对份额混淆处理.只有同时拥有一定份额的参与者才能够还原出原始数据.最后通过隐私交集计算，在参与者拥有数据集的交集达到了网址http:/ 1 347信息安全研究第10 卷第4期2 0 2 4年4月Journalotinformatien Security ResearchVol.10No.4Apr.2024门限值后才能完成秘密的恢复.在此过程中，任何参与者都无法得知其他参与者所持有的数据，保证了数据的隐私性。本文的主要创新点如下：1)引入了弹性秘密共享，增加了洗牌协议的容错性以及抗合谋攻击性；2)设计出一种多方下简单且效率较高的洗牌协议，具有较好的应用性；3)将洗牌协议和隐私集合交集计算技术相结合完成秘密的恢复，提高了恢复过程的隐私性。1相关工作1.1弹性秘密共享秘密共享最早由Shamir4于197 9年提出，并于198 6 年 5 提出了（t，n）门限方案.Desmedt等人 6 于1991年提出了弹性秘密共享的概念.弹性秘密共享保证了存在一定数量恶意参与者的情况下方案的可靠性.Roy等人 7 于2 0 14年提出了一种防止作弊行为的秘密共享方案.肖健等人 8 于2023年提出了一种基于多答案保护的弹性秘密共享协议.与秘密共享相比，弹性秘密共享具有可恢复性强、安全性好、可扩展性强等优点.因此，本文创新地在洗牌协议中引入了弹性秘密共享，较之传统的基于秘密共享的洗牌协议，本文协议具有更高的安全性与可扩展性。1.2洗牌协议洗牌协议主要用于对数据进行随机排序，最初由Chaum9于198 1年提出.Chen等人 10 于2020年提出了一种基于秘密共享和洗牌的数据发布协议.Melissa等人 11于2 0 2 0 年提出将加密的元素和位向量进行洗牌.粟勇等人 12 1于2 0 2 2 年提出了一种基于安全洗牌和差分隐私的联邦学习模型安全防护方法.洗牌的特点在于其随机性.数据集中的每组数据在洗牌后都等概率地出现在空间的各个位置，有效地降低了攻击者找到某一特定元素进而展开攻击的风险。1.3基于秘密共享的洗牌协议2000年，Cramer等人 13 提出将洗牌协议和秘密共享相结合，但并未给出详细的过程.2 0 0 1年,Damgard 等人 14提出一种基于秘密共享的洗3481牌协议，主要特点是能够实现公开验证和保密性.但是，其对参与者的诚实性有较高要求.Pinkas等人 15 于2 0 12 年提出一种基于洗牌协议的安全多方计算协议，并提高了计算的效率和可扩展性。Kong等人16 1于2 0 2 1年提出一种随机化洗牌技术，用于保护参与者在协作学习过程中的隐私.1.4隐私集合交集计算隐私集合交集计算17 能够在计算参与者私有数据集交集的同时，不泄露除交集以外的其他信息.Meadows18于198 6 年提出首个隐私集合交集计算协议.随后，Huberman等人 19 于1999年对Meadows18的方案作出了细致的描述.Freed-man等人 2 0 1于2 0 0 4年基于不经意多项式求值构造了隐私集合交集计算协议.申立艳等人 2 1 于2017年对两方隐私集合交集计算协议进行了简要总结.高莹等人 2 2 于2 0 2 3年对基于多个参与者的隐私集合交集进行了综述。1.5布隆过滤器布隆过滤器是一种集合元素查询工具 2 3，用来确定一个元素是否为集合的成员.Bloom24于1970年首次提出布隆过滤器，其主要功能是查询元素是否属于某集合.布隆过滤器可以看作将元素编码在一个长度为的数组中.通过使用哈希函数和位向量，对元素的哈希映射位置来间接存储元素。2基基于弹性秘密共享的多方洗牌协议的设计2.1整体思路弹性秘密共享算法可以保证数据的机密性，确保数据不被恶意泄露.洗牌协议可以对数据进行重新排列，从而保护数据的隐私.数据拥有者可以使用弹性秘密共享算法对数据进行共享，然后使用洗牌协议对数据进行重新排列，即使参与者窃取了部分密文也无法推断出原始数据的内容.因此，将弹性秘密共享和洗牌协议相结合可以在保护数据隐私的同时保证数据的机密性和完整性。2.2详细步骤本文提出了一种基于弹性秘密共享的多方洗学术论文.ResearchPapers牌协议.假设本文采用的弹性秘密共享技术基于(t,n)门限,协议参与方的个数为n，参与方拥有的集合为X，每个集合的比特长度为.本文所用的相关符号如表1所示：表1相关符号说明名称符号表示参与方P1,P2,Pn参与方拥有的集合X,=(ai,a2.,ah)共享份额的自变量a1.a2,an共享份额的因变量f(ai),f(a2),f(an)该协议的具体流程如下：1）秘密份额的生成算法.分发者选定一个秘密s，随机性地选择n个不同的索引作为相应的自变量(a1,a2，,a n)根据这些索引选择一个最高次幂为t一1的秘密多项式f（），满足条件f（O）=s.秘密份额的集合为（s1，S2，Sn），且满足条件s;=f(ai).2）数据集的洗牌.生成秘密份额后将这些秘密份额打乱顺序，将秘密份额看作元素，并将这些元素组成长度为NXn的数组.从末端元素开始向前遍历数组。直到第2 个元素，对于每个位置i，随机生成一个范围在 0,订之间的整数j.接着将第i个位置的元素与第；个位置的元素交换。然后继续向前遍历数组，重复前2 段步骤，直到遍历到第1个元素为止。最后，打乱后的数组即为随机打乱后的顺序.按照上述洗牌的方法得到随机的元素顺序.这里随机选择 N个元素为1组,由于一共有 NXn个元素,故元素一共被分成n组.每个参与方获得1组元素，这里参与方P1的元素所构成的秘密份额的集合表示为X,=i,2,c).每个参与者只能看到自已所持有的数据部分，而无法看到其他参与者的数据.每个参与者可按照上述对其所持有的秘密共享数据部分进行洗牌。3）布隆过滤器生成算法.假设一共有k个哈希函数.任意选择1个参与方，如P1.P1用自已的份额构造长度为m的布隆过滤器.具体算法如下：首先P1用哈希函数将自己的每个元素都进行仿射变换，得到n个因变量.然后将这n个因变量作为布隆过滤器数组的自变量,并为每个因变量赋相应的随机种子，这样就实现了将弹性秘密共享生成的秘密份额分别放在自已集合元素映射到布隆过滤器位置的过程。当插人1个元素到布隆过滤器中时，k个不同的哈希函数分别对该元素进行映射，所得到的k个结果的异或仍然为该元素。同时,P1将该混淆布隆过滤器分解为n一1个子混淆布隆过滤器，满足分解后的n一1个子混淆布隆过滤器的异或为原混淆布隆管理器。随后P1将n一1个子混淆布隆过滤器发给其余的参与方P2.4）份额收发.在份额收发阶段，参与者之间需要相互交换它们的份额，以便进行后续的计算操作。通过异或秘密共享方案隐藏各个参与方的混淆布隆过滤器.具体为：P2，P3，,P，运行1个异或秘密共享方案，并公开各自的秘密份额异或后的结果.每个参与方根据自己的秘密份额生成自己的布隆过滤器，并由此构造混淆布隆过滤器.5）交集计算.利用弹性秘密共享能否重构出秘密判断交集基数是否达到门限值.如果能达到重构值，即：交集数量达到门限值，则能够输出共享的秘密；否则，可以推断出交集数量没有达到门限值，协议终止.具体算法流程如下：输人构造好的秘密份额集合s=(si,s2，s,)，通过里德所罗门解码算法计算出1个多项式g（）满足g（i n d.）=s i,如果s中正确的份额大于t,那么g(0)=f(0)=s.3基于弹性秘密共享的多方洗牌协议的分析3.1正确性分析如果交集数量达到门限值则能够输出共享的秘密；否则，可以推断出交集数量没有达到门限网址http:/1349信息安全研究第10 卷第4期2 0 2 4年4月Journalotinformatien Security ResearchVol.10No.4Apr.2024值，协议终止。定理1.本文协议采用的弹性秘密共享满足正确性。当参与方P1，P2，,P，交集数量达到门限值t时，可以获得足够多的正确份额重构秘密s.弹性秘密共享能够重构秘密需要满足如下条件：参与方元素的交集t十（n十d一t)/2.这里的d为余码的数量，n为参与方的集合元素的大小.引人穴余码后，需要满足t十+d=t+(n十d一t)/2,因此dn十t.因此协议的离线阶段通过相同的随机种子生成n一t个相同的伪元素.当1个元素是交集中的元素时P1通过元素查询混淆布隆过滤器可以得到.因此，当交集数量达到门限值t时，可以获得足够多的秘密份额重构秘密s.本文提出的协议可以保证正确性。定理2.本文协议采用的洗牌算法满足正确性。证明。洗牌算法的方法是通过数学归纳法，考虑洗牌算法在每次迭代中是否能够产生1个等概率的排列.假设在第i步之前已经产生了1个等概率的排列.在第i步中，从剩余的元素中随机选择1个元素，并将其与第i个元素交换.这将生成另一个等概率的排列，因为每个元素都有相同的概率成为第i个元素.当算法完成时将得到一个由原序列中的元素组成的等概率排列，因为每次都是从剩余的元素中随机选择1个元素来交换，而不是从已经交换过的元素中选择。因此，该洗牌算法的正确性可以得到证明：如果使用一个公平的随机数生成器，那么该算法将产生一个等概率的排列.证毕。定理3.本文协议采用的布隆过滤器假阳性可能性很低，其潜在的误差可以忽略不计假设需要处理的集合为(1,2，,n），存在k个m位的哈希函数.哈希函数将每个元素独立且均匀地映射为随机数.这是一个乐观的假设，适合于实际实现.在这个假设下，在s的所有元素被散列到布隆过滤器后，某个特定位仍然为0 的概率：3501p=(1-1/m)ne-k/m,所以为了方便性，可以用p=e-kl来代替p,则在力的前提条件下，假阳性的概率为f=(1-p)*(1-p)*=(1-e-klm)*,这个概率是很小的，故本文协议采用的布隆过滤器假阳性可能性很低，其潜在的误差可忽略不计.3.2安全性分析定理4.本文协议在半诚实模型中是安全的，可以抵抗合谋攻击。假设参与方p是攻击者，那么其进行如下攻击操作：首先选择一个随机值rand1和2 n一t个自变量ai,a2,a2m-,结合相应的因变量计算布隆过滤器Bk，并将其拆分为n一1份.然后攻击者P根据布隆过滤器Bk和交集I随机且独立地对布隆过滤器SB：进行采样.最终，攻击者P可以得到的信息为攻击者P享有的秘密份额k、交集I以及布隆过滤器SBk.然而攻击者P无法计算其余参与方的布隆过滤器，因为没有其余参与方的秘密份额，同时也无法区别真实执行的和随机生成的布隆过滤器。在合谋攻击中，攻击者企图获取秘密s.诚实的参与者发送布隆过滤器给攻击方后.布隆过滤器SB，是参与者P，通过对布隆过滤器B，和随机数异或得到的.由于秘密共享保证了随机数和布隆过滤器的安全性.攻击者无法区别真实执行的和随机生成的布隆过滤器.所以攻击者无法得到其余参与者的隐私信息，也无法确定协议真实的算法.故本文协议可以抵御合谋攻击。3.3对比分析本文协议还与其他基于秘密共享的洗牌协议进行了对比，具体如表2 所示。本文协议所采用的洗牌算法的基本思想是从数组中随机选择1个元素，然后将它与数组的最后1个元素交换位置，依此类推，直到数组的第1个元素.因此洗牌算法的计算复杂度是线性的,即O(n).本文协议在生成布隆过滤器时的计算复杂度为O(nk），各方计算其布隆过滤器的计算复杂度与布隆过滤器的长度相关，为O（m）.在秘密共享的重构阶段，计算复杂度为O（n lo g n）.总体来说，本文协议的计算复杂度为O(n十nk十m十nlogn).学术论文.ResearchPapersCristofaroL26提出了一种基于秘密共享的洗牌协议.该协议确保在洗牌过程中每个服务器和客户端都只了解到洗牌结果的一部分.该方案具有较高的效率，但不能较好地抵御合谋攻击.其构建哈希链的时间复杂度O(n）,其中n是原始数据的大小.而哈希函数近似于O(1)的计算复杂度.故哈希链洗牌的计算复杂度为O(n十1).协议安全性抗合谋攻击Huang 等人 2 5高Cristofaro 等人 2 6 中本文高应用前景分析4.1具体应用本文提出的基于弹性秘密共享的洗牌协议在数据隐私保护方面具有一定的实用性，包括但不限于如下方面：1）弹性秘密共享和洗牌双重保护数据共享。秘密共享协议将秘密分配给不同的参与方，洗牌协议随机重组数据，以保护数据的隐私.解密需要各方协同重组消息.这种方案在医疗、金融等领域得到广泛应用.2）协议支持多方下的安全计算.将参与方的数据进行随机混淆和重组，并使用秘密共享协议将其分配给不同的参与方.最后，各方协同解密并重组数据.这种协议广泛应用于机器学习等领域.3）协议应用于检索和排序.将检索和排序任务分配给多个参与方，各方将其拥有的数据进行洗牌处理，并使用秘密共享协议将其分配给其他参与方。4.2存在的问题本文协议目前存在的一些问题主要有：1）秘密共享的计算复杂度略高.协议需要对数据进行多次处理，因此会增加数据处理的时间成本。2）隐私交集计算的通信开销可进一步降低。洗牌协议和秘密共享需要对数据进行多次传输，因此会增加数据通信开销。Huang等人 2 5 提出了一种基于安全多方计算的洗牌协议.该协议允许参与方将其私有数据进行洗牌，可以抗合谋攻击，但是在参与方数量增加时，计算复杂度会大幅度增加.该协议采用的洗牌算法的计算复杂度为O（n）,因为每次选择和移除元素都需要线性时间.此外，该方法通常需要额外的空间存储新的随机排列数组.表2 本文协议与其他方案对比效率是中较高（随机抽样、哈希链）是高（隐私交集计算）3）协议应用受到参与方个数的限制.洗牌协议和秘密共享需要多个参与方进行协同处理，因此会限制其在大规模数据处理中的应用.5 结 语本文提出一种基于弹性秘密共享的多方洗牌协议，充分利用了弹性秘密共享、洗牌协议等相关的密码学技术.通过与相关协议对比，本文协议兼具实用性和安全性等特点，能够很好地保护用户数据隐私，有较好的应用前景。参考文献1董晓蕾.物联网隐私保护研究进展.计算机研究与发展，2 0 15，52（10)：2 341-2 3522文刘涵阅，张春生。基于洗牌算法的大数据抽样有效性分析J.计算机应用研究，2 0 2 1，38（10）：30 49-30 543崔晨雨，张丽娜。一种具有身份锁的门限多秘密共享方案J.计算机工程与科学，2 0 2 2，44（8）：138 2-13974Shamir A.How to share a secret J.Communications ofthe ACM,1979,22(11):612-6135Sahai A,Shamir A.How to share a secret J.Communications of the ACM,1986,29(11):1129-11346Desmedt Y,Beimel A.Robust threshold secret sharingJJ.Journal of Cryptology,1991,4(1):1-247RRoy P,Adhikari A,Xu R An efficient robust secretsharing scheme with optimal cheater resiliency J.Security,Privacy,and Applied Cryptography Engineering,2014,88(4):47-58网址http:/1351洗牌计算复杂度0(n2)0(n+1)洗牌计算复杂度为O(n）信息安全研究第10 卷第4期2 0 2 4年4月Journalot information Security ResearchVol.10No.4Apr.20248肖健，杨敏，孟庆树.多答案保护秘密共享协议J。武汉大学学报：理学版，2 0 2 3，6 9（1）：51-599Chaum D.Untraceable electronic mail,return addresses,and digital pseudonyms JJ.Communications of the ACM,1981,24(2):84-9010Chen J,Liu G,Liu Y.Lightweight privacy-preserving rawdata publishing scheme J.IEEE Trans on EmergingTopics inComputing,2020,9(4):2170-217411Melissa C,Esha G,Oxana P.Secret shared shuffle J.Cryptology ePrint Archive,2020,11(1):342-37212粟勇，刘文龙，刘圣龙，等.基于安全洗牌和差分隐私的联邦学习模型安全防护方法J.信息安全研究，2 0 2 2，8(3):270-27613Cramer R,Damgard I,Nielsen J.Multiparty computationwith low communication,computation and interaction viathreshold FSS G/LNCS 1807:Advances in CryptologyEUROCRYPT 2000.Berlin:Springer,2000:311-32614Damgard M,Pedersen T P,Pfitzmann B.Efficient andsecure multiparty computation C/Advances in CryptologyEUROCRYPT 2001.Berlin:Springer,2001:52-7815Pinkas B,Schneider T,Zohner M.Secure multipartycomputation goes live CJ/Proc of the 2012 ACM Conf onComputer and Communications Security(CCS12).NewYork:ACM,2012:605-61616 Kong Y,Wang C,Li L.Privacy-preserving collaborativelearning via randomized shuffle JJ.IEEE Trans onInformation Forensics and Security,2021,16(8),2113-212617魏立斐，刘纪海，张蕾，等。面向隐私保护的集合交集计算综述 J.计算机研究与发展，2 0 2 2，59（8）：17 8 2-17 9918Meadows C.A more efficient cryptographic matchmakingprotocol for use in the absence of a continuously availablethird party CJ/Proc of the 7th IEEE Symp on Securityand Privacy.Los Alamitos,CA:IEEE Computer Society,1986:134-13419Huberman B,Franklin M,Hogg T.Enhancing privacy andtrust in electronic communities C/Proc of the 1st ACMConf on Electronic Commerce.New York:ACM,1999:78-862oFreedman M,Nissim k,Pinkas B.Efficient privatematching and set intersection C/Proc of the 23rd intConf on the Theory and Applications of CryptographicTechniques.Berlin:Springer,2004:1-1921申立艳，陈小军，时金桥，等.隐私保护集合交集计算技术研究综述 J.计算机研究与发展，2 0 17，54（10）：2 153-216922高莹，王玮.多方隐私集合交集计算技术综述.电子与信息学报，2 0 2 3，45（5）：18 59-18 7 223华文镝，高原，吕萌，等。布隆过滤器研究综述.计算机应用，2 0 2 2，42(6)：17 2 9-17 4724Bloom B.Space/time tradeoffs in hash coding withallowable errors J.Communications of the ACM,1970,13(7):422-42625Huang Y,Katz J,Evans D.Privacy-preserving shuffling ofprivate data:A secure multi-party computation approachCJ/Proc of the 30th IEEE Symp on Security and Privacy(S&.P).Piscataway,NJ:IEEE,201l:535-54626Cristofaro D,Emiliano M.Practical secure shuffling ofoutsourced data C/Proc of the Int Conf on AppliedCryptography and Network Security.Berlin:Springer,2012:1-12满子琪硕士研究生，主要研究方向为网络空间安全，张艳硕博士，副教授，硕士生导师，CCF高级会员，主要研究方向为密码理论及其应用。zhang_严梓洋硕士研究生.主要研究方向为网络空间安全罗乐琦硕士研究生.主要研究方向为漏洞挖掘、网络攻防。陈颖博士，副教授，硕士生导师.主要研究方向为数据挖掘、信息安全.ychenbesti.edu352