通用可重组安全的多方求解Top-k协议设计_栾明学.pdf
《通用可重组安全的多方求解Top-k协议设计_栾明学.pdf》由会员分享,可在线阅读,更多相关《通用可重组安全的多方求解Top-k协议设计_栾明学.pdf(14页珍藏版)》请在咨信网上搜索。
1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):195208密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618通用可重组安全的多方求解 Top-k 协议设计*栾明学1,张秉晟1,杨国正2,臧 铖3,陈嘉俊2,李泽昊1,吴泽成1,任 奎11.浙江大学 网络空间安全研究中心,杭州 3100272.浙商银行金融科技部,杭州 3112153.浙商银行区块链技术应用研究院,杭州 311215通信作者:张秉晟,E-mail:摘要:对于一个定点数多重集合 S,第
2、 k 小元素(又称 Top-k 元素)x S 是指当集合中元素按照递增顺序排列时,刚好位于第 k 位置的元素.两方或多方安全求解它们输入的公共集合 X 的 Top-k 元素,是安全多方计算应用领域的经典案例.它能够使互不信任的多个数据持有方在不泄露自身数据的前提下,获取更大样本集合上的统计信息,从而实现隐私保护决策.本文提出了一种两方或多方分布式持有定点数数据的场景下,不依赖可信第三方,安全求解它们数据集合 X 中 Top-k 元素的协议,证明了其通用可重组(UC)安全性.协议使用了基于秘密分享的比较及加法安全多方计算协议作为构造模块,巧妙地从高到低按位依次确定并公布 Top-k 元素的 p
3、进制定点数表示.协议实现了 O(logpM)的通信轮次复杂度,其中 M 为 p 进制数的最大取值,p 为约定的定点数基数.实验证明,对于常见网络环境(包括局域网和广域网),当 p=2i(i=2,8)时,协议的通信时间和总运行时间均显著优于其他现有的 Top-k 求解协议.关键词:安全多方计算;中位数;Top-k 元素;通用可重组(UC)安全中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000589中文引用格式:栾明学,张秉晟,杨国正,臧铖,陈嘉俊,李泽昊,吴泽成,任奎.通用可重组安全的多方求解 Top-k协议设计J.密码学报,2023,10(1):195208
4、.DOI:10.13868/ki.jcr.000589英文引用格式:LUAN M X,ZHANG B S,YANG G Z,ZANG C,CHEN J J,LI Z H,WU Z C,RENK.Universally composable secure multi-party computation of the top-k elementJ.Journal of CryptologicResearch,2023,10(1):195208.DOI:10.13868/ki.jcr.000589Universally Composable Secure Multi-party Computatio
5、n of theTop-k ElementLUAN Ming-Xue1,ZHANG Bing-Sheng1,YANG Guo-Zheng2,ZANG Cheng3,CHEN Jia-Jun2,LI Ze-Hao1,WU Ze-Cheng1,REN Kui11.Institute of Cyber Security Research,Zhejiang University,Hangzhou 310027,China*基金项目:国家重点研发计划(2021YFB3101601);国家自然科学基金(62032021,61772236);浙江省重点研发计划(2019C03133);阿里巴巴-浙江大学前沿
6、技术联合研究所;浙江大学网络空间治理研究所;创新创业团队浙江省引进计划(2018R01005);移动互联网系统与应用安全国家工程实验室 2020 开放课题Foundation:National Key Research and Development Program of China(2021YFB3101601);National Natu-ral Science Foundation of China(62032021,61772236);Key Research and Development Plan of Zhejiang Province(2019C03133);Alibaba-Z
7、hejiang University Joint Institute of Frontier Technologies(AZFT);Institute of CyberspaceGovernance of Zhejiang University;Innovation and Entrepreneurship Team Introduction Plan of Zhejiang Province(2018R01005);Open Project Program of National Engineering Laboratory of Mobile Internet System and App
8、licationSecurity(2020)收稿日期:2022-02-18定稿日期:2022-05-06196Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.20232.Financial Technology Department,China Zheshang Bank Co.Ltd.,Hangzhou 311215,China3.Blockchain Technology Application Research Institute,China Zheshang Bank Co.Ltd.,Hangzhou 311215,ChinaC
9、orresponding author:ZHANG Bing-Sheng,E-mail:Abstract:The kth-minimum element(i.e.Top-k element)in a multiset S of fixed-point numbers isthe kth element when the elements in S are sorted in increasing order.One of the classic cases of securemulti-party computation(MPC)application is safely evaluating
10、 the Top-k element of the union set Xof two or multi parties secret set,which enables multiple data owners who do not trust each other toobtain statistical information on a larger set without disclosing their own data,realizing the privacyprotecting decision.This paper proposes a protocol to evaluat
11、e the Top-k element of their union setX secretly without a trusted third party when each party holds a multiset of fixed-point numbers,andits universally composable(UC)security has been proved.The protocol is based on secret sharing,constructing with the comparison and addition secure computing bloc
12、ks,and skillfully evaluates thebase-p representation of the Top-k element from high position to low position while disclosing themone by one.Its communication round complexity is O(logpM),where M is the maximum value ofany number of base p,and p is such the base.Experiments show that,for a common ne
13、twork setting(LAN or WAN),when p=2i(i=2,8),the communicating and total running time of the proposedprotocol are significantly better than other existing Top-k protocols.Key words:secure multi-party computation(MPC);median number;Top-k element;universallycomposable(UC)security1引言对于定点数多重集合 S,Top-k 元素
14、x S 是指当集合中元素按照递增顺序排列时,刚好位于第 k 位置的元素,即集合中第 k 小的元素.考虑 n 个互不信任的数据持有方 P1,P2,Pn,其各自持有私密数据集合 X1,X2,Xn,则其公共 Top-k 元素 x X 是指公共集合 X=X1 X2 X3 Xn中第 k 小的元素.隐私保护安全地求解 n 个数据持有方的公共 Top-k 元素要求协议运行过程中,任一数据持有方 Pi不能直接或推理得出其他任意数据持有方 Pj对应集合 Xj中元素的值,而只在协议运行最后获知 Top-k 元素的值.作为一个特殊情况,当 k=|X|/2 时,协议安全地求解公共集合中位数元素.多方安全求解 Top-
15、k 元素在现实世界中具备大量应用场景.例如,多家银行希望在不泄露各自客户信息和经营状况的前提下,衡量银行储户的信用评分分布状况;或者同一地区的多家医院希望在不泄露患者私密信息的前提下,获取该地区患者身体指标的中位数.多方数据聚合使得样本量大大增加,从而能更真实地反映行业状况,有助于提高企业或机构的决策准确度.除此之外,Top-k 元素求解往往是其他安全多方计算功能的基础协议构件,例如 Vaidya 等1提出了一种寻找与目标样本相似度前 k 项样本的算法,其主要思想就是获取测试集合中与目标样本曼哈顿距离或欧几里得距离最小的前 k 项测试样本.事实上,只要统计样本特征能够数值化表示,Top-k 求
16、解算法就有其用武之地.因此,Top-k 元素安全求解一直是安全多方计算应用领域的重要研究问题,各国学者纷纷尝试构造高效的 Top-k 求解协议.Vaidya 等1提出了一种基于预估数值和安全比较的多方 Top-k 求解协议,协议每轮预生成一个猜测值,各方将自己数据依次与该猜测值进行安全比较,然后各方将各自集合中小于该猜测值的元素数量安全相加,相加结果与 k 安全比较,并依据比较结果调整下一轮猜测值的大小,从而逐步逼近最终第 k 小的值.Aggarwal 等2,3分别提出了两方和多方 Top-k 求解协议,两方协议中双方各取前k 小元素参与运算,从而将 Top-k 问题转变为中位数求解,然后逐轮
17、比较各自集合的中位数,并丢弃中位数较小一方较小的一半元素和中位数较大一方较大的一半元素,直至两方集合各剩一个元素,较小的元素就是原公共集合的 Top-k 元素的值;其多方协议采用了与文献 1 类似的构造,区别在于允许每一轮的猜测值广播给参与计算的每一方,从而集合元素与猜测值的比较可以在本地计算,进而在不泄露更多信息的栾明学 等:通用可重组安全的多方求解 Top-k 协议设计197前提下,显著降低了协议的通信复杂度.Huang 等人4提出了一种更高效的多方 Top-k 求解协议,它对数据采用了一种类似独热编码(one-hot)的表示方式,可以仅使用一轮加法安全运算得到所有集合元素的分布信息,从而
18、求出第 k 小的元素.但是在安全性方面,该协议虽然隐匿了数据持有方与数据的映射关系,但还是泄露了所有样本数据的分布信息.除此之外,Zhang 等人5借助非可信的第三方聚合器实现了多方数据 Top-k 求解;而 Jnsson 等人6使用安全比较协议和归并排序算法实现了多方数据的排序,同样也可以用于 Top-k 元素的求解,但是其通信量是 O(mlog2m),m 是集合中元素的数量.1.1文章贡献本文提出了一种半诚实敌手模型下可证明安全的多方 Top-k 求解协议,该协议约定了一种以 p 为基数(p=2i,i=1,2,)的位分解表示形式,并且应用基于秘密分享的比较及加法安全多方计算协议,从高到低按
19、位确定 Top-k 元素的定点数表示.该协议通信轮次复杂度为 O(logpM),其中 M 为定点数最大取值,并且在实现了较低通信复杂度的同时,保证了除最终披露 Top-k 元素外不泄露集合元素的分布信息.文章具体贡献如下:提出了一种多方 Top-k 安全求解协议,引入了可调节的基数 p,使其通信轮次复杂度为 O(logpM),相比基于二分法的协议2大大降低了通信轮次.在半诚实敌手模型下分析并证明了所提出协议的通用可重组安全性.进行了协议的实现与性能评估,实验结果表明当 p=2i(i=2,8)时,相比基于二分法的协议2显著降低了通信时间和总运行时间.1.2文章结构接下来,文章第2节将介绍安全多方
20、计算与通用可重组安全领域的相关知识,第3节将进行协议细节描述,第4节将进行协议的通用可重组安全性证明,第5节将对协议的通信复杂度和运行数据进行分析,第6节将对本文工作进行总结和展望.2相关知识2.1符号与约定本文中出现的所有符号及标记与本节下列约定一致.记 Z 为协议的安全参数.当 X 为一个多重集合时,x X 表示从 X 中均匀随机采样 x,并且|X|代表多重集合中元素的数量.当 F 为一个本地算法时,y F(x)表示输入为 x 时算法 F 输出 y.对于下文将出现的向量和标量,记 a 为向量,设其长度为,则 av0,)表示其内部的一个标量成员.若向量已存在下标,则表示其内部标量时,在原有下
21、标后添加一个新的下标,二者以逗号分隔,例如,长度为 的向量 ai内的标量成员表示为 ai,v0,).2.1.1整数域 Z2考虑到多重集合中允许存在多个相同值的元素,协议的参与者 P:=P1,P2,Pn 需要统计公共集合元素的数量以约定模域 Z2,log2(|X|),|X|=ni=1|Xi|可以通过基于秘密分享的加法安全计算协议求出7,从而避免泄露各方私有集合中元素的数量.之后将 x 21,21)映射到 Z2,当 x为负时,x=x+2,即,当 x 为负数时最高位置为 1.2.1.2规范化定点数表示该协议从高到低逐位确定 Top-k 元素的值,为此,各方还需要事先约定好数据的定点数表示格式.考虑到
22、元素可能为小数或负数的情况,还需要在协议运行前将元素的取值范围映射到非负整数集,接下来分4 种情况讨论:非负整数 对于集合中全部元素均为非负整数的情况,所有各方约定定点数基数 p 和定点数长度,从而集合中任意元素 x 可表示为 x1x2x0,x=1i=0 xi pi;非负小数 若集合中存在非负小数,各方需要额外约定小数部分位数 f,并放大集合中所有元素至 pf倍,从而 x pf=1i=0 xi pi,此时协议的输入均映射为非负整数,协议运行结束后将输出结果缩小至 pf倍即原集合 Top-k 元素的值.198Journal of Cryptologic Research 密码学报 Vol.10,
23、No.1,Feb.2023负整数 若集合中存在负整数,各方需要先约定元素最小值 xmin 0,并使集合中所有元素减去 xmin,再约定定点数基数 p 和长度,从而 x xmin=1i=0 xi pi.此时协议的输入均映射为非负整数,协议运行结束后将输出结果加上 xmin即原集合 Top-k 元素的值.负数与小数并存 若集合中同时存在负数和小数,各方约定小数部分位数 f、元素最小值 xmin0、定点数基数 p 和长度,从而(x xmin)pf=1i=0 xi pi.此时协议的输入均映射为非负整数,协议运行结束后将输出结果放缩至 pf倍后加上 xmin即原集合 Top-k 元素的值.简明起见,本文
24、第3节中协议描述仅考虑集合中全部元素均为非负整数这一种情况.另外不难看出,上述约定不但规范了数据表示形式,还隐式地确定了数据的取值范围.2.2安全多方计算1982 年,Yao 提出了著名的“百万富翁问题”:两个百万富翁如何在不泄露自身资产的前提下得知谁更富有8.该问题引申出了安全多方计算的基本概念:两个或多个互不信任的数据持有方在不泄露己方数据且不依赖可信第三方的前提下,安全地计算一个约定函数.目前常见的安全多方计算实现方案主要包括姚氏混淆电路协议和基于秘密分享的协议.2.2.1秘密分享本文使用了基于加法秘密分享的安全多方计算基础协议作为安全求解公共集合 Top-k 元素协议的原语.记 x 为
25、秘密分享状态下的 x,此时安全计算参与方各持有一份 x 的加法秘密分片,只有通过与其他参与方通信获取其余所有加法秘密分片,才能还原出 x 的值,此还原过程称为“披露”.设计协议时,允许将 x 的值披露给所有参与方,也可以单独披露给指定的部分参与者.由于加法秘密分享的线性特性,线性的加法操作可以在加法秘密分片上本地进行7;而对于乘法操作,则需要执行安全计算协议,例如预处理乘法三元组协议9,直接生成乘法输出的秘密分片,记为 x y=x y.这样一来,其他更为复杂的运算就可以使用加法协议和乘法协议组合完成.特别地,当 x,y Z2时,乘法协议和加法协议分别对应布尔电路的与(AND)门和异或(XOR)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 通用 重组 安全 多方 求解 Top 协议 设计 栾明学
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。