若干集合问题的安全多方计算研究

1、分类号TP309密 级公开学 号161584快币峰花大?SHAANXI NORMAL UNIVERSITY硕士学位论文（学术型）题目若干集合问题的安全多方计算研究作者刘旭红指导教师窦家维副教授-级学科名称帷二级学科名称应用数学提交日期二。一九年五月学位论文原创性声明本人声明所呈交的学位论文是我在导师的指导下进行研究工作所取得的 研究成果。尽我所知，除本文中已经注明引用的内容和致谢的地方外，本论 文不包含其他个人或集体己经发表或撰写过的研究成果，也不包含本人或他 人已申请学位或其他用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均已在文中做了明确说明并表示谢意。本学位论文若有不实或者侵

2、犯他人权利的，本人愿意承担一切相关的法 律责任。作者签名：加窟日期：加|年尸月7日学位论文知识产权及使用授权说明书本人在导师指导下所完成的学位论文及相关成果，知识产权归属陕西师 范大学。本人完全了解陕西师范大学有关保存、使用学位论文的规定，允许 本论文被查阅和借阅，学校有权保留学位论文并向国家有关部门或机构送交 论文的纸质版或电子版，有权将本论文的全部或部分内容编入有关数据库进 行检索，可以采用任何复制手段保存和汇编本论文。本人保证毕业离校后， 发表本论文或使用本论文成果时署名单位仍为陕西师范大学。保密论文解密后使用本声明。作者签名：切独Z日期：圮7年3月q日随着网络技术的迅速发展，多方联合计

3、算己经成为计算机网络中越来越 普遍的计算模式.由于网络环境的虚拟性，在联合计算过程中稍有不慎就可能 导致数据的机密性丧失与隐私泄露，所以在联合计算中保护参与者数据的隐 私性是一个关键性问题.运用安全多方计算技术，既能充分发挥机密数据的作 用，又能保护数据的机密性与隐私,这使得安全多方计算成为隐私保护计算的 主要方法，并得到广泛研究.集合问题的安全多方计算是隐私保护问题的一个重要研究内容，在实际 生活中的很多领域具有广泛应用.现有的关于集合问题的保密计算主要研究 整数集上的两方集合保密计算，相关研究成果较多，但集合问题在其他方面还 有很多重要问题未得到解决.一方面，现有集合问题的研究成果主要是针

4、对两 方集合，关于多方集合的研究方案还较少，且已有方案的计算效率不高，不具 有实际应用性.另一方面，有理数域上集合问题的保密计算还未见到相关研 究，限制了集合保密计算的适用范围.所以，需要设计效率更高，适用性更广的 有关集合问题的保密计算方案.本文以上述两方面集合问题为研究重点，即深入研究整数集上多方集合 问题和有理数域上两方集合问题，对这两类问题设计高效、安全的保密计算 协议.本文的主要研究内容如下：关于整数集合和有理数集合，设计了两种不同的编码方案，使每个参 与者的保密集合隐藏在一个特殊数组中，并结合具有一定同态性的加密算法, 将集合保密计算问题转化为数组的保密计算问题.本文对于几种基本的

5、集合运算设计了安全高效的计算协议，这些协议 适用于两方和多方集合保密计算.并利用模拟范例方法严格证明了这些方案 在半诚实模型下是安全的，能够抵抗任意的合谋攻击.进一步，以半诚实模型 下的保密计算协议为基础，设计了恶意模型下安全的相关协议.提出并研究了有理数域上两方集合保密计算这类新问题.首先，利用 计算几何知识将集合问题转化为数组问题，结合同态加密算法，对于有理数域 上几类基本的集合问题设计了保密计算协议，这些协议能同时保证集合元素 以及集合势的隐私性.效率分析表明本文协议在计算效率方面优势明显最 后，给出了协议在有理点集合问题中的应用举例.关键词:安全多方计算；同态加密方案；集合问题；编码方

6、案;安全性.AbstractWith the rapid development of network technology, multiparty collaborative computation has become an increasingly common computation mode in computer networks. Due to the virtuality of the network environment, the slightest carelessness in the collaborative computation process may lead

7、 to privacy disclosure of data, so protecting the privacy of the participants7 data in the collaborative computation is a key issue. The application of secure multiparty computation technology can not only give full play to the role of private data, but also protect the confidentiality and privacy o

8、f data, which makes secure multiparty computation become a main method of privacy-preserving computation, and has been widely studied.Secure multiparty computation of set problems is an important research content in cryptography, and it has been widely used in many fields. The existing secure comput

9、ation of set problems mainly studies two-party set computation on integer set, and there are many related research results. In other research directions, there are still many important set problems have not been solved. On the one hand, the existing research results of the set problem are mainly aim

10、ed to the computation of two-party set. There are few research schemes about the computation of multiparty set, and the computational efficiency of the existing schemes are not ideal, which has no practical application. On the other hand： the secure computation of set problems on the rational number

11、 field have not been studied, which limits the applicable scope of the secure set computation. Therefore, it is necessary to design schemes with higher efficiency and wider applicability.In this paper, we focus on the above two aspects of set problems, deeply explore the multiparty set problem on th

12、e integer set, and the two-party set problem on the rational number field, and design efficient and secure protocols for above two problems. The main research contents of this paper are as follows:We design two different encoding schemes for integer set and rational set. so that each participants pr

13、ivate set is hidden in a special array. Combining with the homomorphic encryption algorithm, the secure set computation problem is transformed into that of secure array computation.We design secure and efficient computation protocols for several basic set operations. These protocols are suitable for

14、 the secure computation of two-party sets and multiparty sets. Then, we strictly prove that these schemes are secure in the semi-honest model and can resist any collusion attacks by using simulation paradigm. Finally, we modify the protocol under the semi-honest model and design the related protocol

15、 in the malicious model.We propose and solve a new problem of privacy preserving two-party set computation on the rational number fields. Firstly, we use computational geometry to transform the set problem into an array problem. Combining with homomorphic encryption algorithm, we design secure compu

16、tation protocols for several basic set problems on the rational number field. These protocols can guarantee the privacy of set elements and set cardinality. The efficiency analysis show that the proposed protocols have obvious advantages in computational eflficiency. Then, we give an application exa

17、mple of the above protocols in rational point set problem.Key words: secure multiparty computation; homomorphic encryption scheme; set problem; encoding scheme; security. TOC o 1-5 h z 摘要IAbstractIll第1章绪论11.1研究背景和意义11.2国内外研究现状21.3本文的主要贡献41.4本文的组织结构4第2章预备知识72.1安全多方计算模型及安全性定义7 HYPERLINK l bookmark23 o

18、 Current Document 2.1.1理想模型7 HYPERLINK l bookmark26 o Current Document 2.1,2半诚实模型7 HYPERLINK l bookmark29 o Current Document 2.1.3恶意模型82.2同态加密方案9 HYPERLINK l bookmark32 o Current Document 2.2.1 ElGamal加密方案9 HYPERLINK l bookmark35 o Current Document 2.2.2变体ElGamal加密方案10 HYPERLINK l bookmark38 o Curre

19、nt Document 2.2.3 Paillier加密方案10224门限密码体制112.3三角形面积计算公式122.4本章小结12第3章多方集合的高效计算协议及应用133.1保密计算多方集合交集/并集13 HYPERLINK l bookmark41 o Current Document 3.1.1问题描述13 HYPERLINK l bookmark44 o Current Document 3.1.2协议设计143.1.3协议的正确性143.1.4协议的安全性143.1.5并集问题描述及协议设计153.2保密计算多方集合交集势/并集势16 HYPERLINK l bookmark72 o

20、 Current Document 3.2.1问题描述16 HYPERLINK l bookmark75 o Current Document 3.2.2协议设计173.2.3协议的正确性183.2.4协议的安全性183.2.5并集势问题描述及协议设计183.3保密计算阈值并集19 HYPERLINK l bookmark105 o Current Document 3.3.1问题描述19 HYPERLINK l bookmark109 o Current Document 3.3.2协议设计 203.3.3协议的正确性213.3.4协议的安全性213.3.5阈值多重并集问题描述及协议设计23

21、3.4性能分析243.5推广应用263.5.1恶意模型下的协议设计263.5.2协议的推广及实际应用273.6本章小结29第4章 有理数域上两方集合的高效计算协议314.1编码方法和转化原理314.2保密判定元素与集合关系32 HYPERLINK l bookmark166 o Current Document 421问题描述32 HYPERLINK l bookmark169 o Current Document 4.2.2协议设计344.2.3协议的正确性354.2.4协议的安全性354.3保密计算有理数集合交集37 HYPERLINK l bookmark184 o Current Do

22、cument 4.3.1问题描述37 HYPERLINK l bookmark187 o Current Document 4.3.2协议设计384.3.3协议的正确性394.3.4协议的安全性394.3.5交集势问题描述及协议设计424.4保密计算有理数集合并集43 HYPERLINK l bookmark202 o Current Document 4.4.1问题描述43 HYPERLINK l bookmark205 o Current Document 4.4.2协议设计434.4.3协议的正确性444.4.4协议的安全性454.5保密计算有理数集合包含关系46 HYPERLINK l

23、 bookmark220 o Current Document 4.5.1问题描述464.5.2协议设计474.5.3协议的正确性48454协议的安全性484.6保密计算有理点与有理点集合关系494.7性能分析504.8本章小结52第5章总结与展望53参考文献55致谢61 HYPERLINK l bookmark286 o Current Document 攻读硕士学位期间的科研成果63 HYPERLINK l bookmark293 o Current Document 攻读硕士学位期间参与项目63第1章绪论1.1研究背景和意义在科技和信息技术飞速发展的时代背景下，计算机网络的应用越来越广,

24、 通信、社交网络、电子商务等网络平台和各种移动APP不断推陈出新，成为人 们生活中必不可少的组成部分.人们可以在网络环境中进行信息交互与传输, 例如：通过移动设备进行电话通讯、视频聊天、文件传输；在各种App进行网 络购物、电子投资、在线支付等.近年来，人们通过网络环境进行信息传递和 信息共享的生活方式越来越普遍，网络信息交互和传输达到空前规模.由于网 络环境的不可控性和虚拟性，在信息交互和传输的过程中无法确保信息的完 整性以及正确性，导致信息安全问题日趋严重.尤其是网络泄密事件频频发 生，已威胁到国家和个人的财产安全，如“黑客”入侵快递公司后台盗取近亿 客户信息、上海市医保系统故障瘫痪近四小

25、时、阿里云因bug禁用内部IP导致 大规模故障等，所以网络信息安全事件无处不在，人们希望能够实现享受便捷 的生活方式与保护个人的私密信息两者共存.根据实际生活中的信息安全问题，安全多方计算(Secure Multiparty Computation, SMC)这一概念应运而生，为解决联合计算中的信息安全问题提供了 基本理论和技术支持.1982年图灵奖得主姚期智教授在文献1中以著名的百 万富翁问题引入安全多方计算，并通过该问题形象地指出了安全多方计算面 临的挑战和可行的解决思路，引起众多学者的关注.之后，Goldreich等人的研 究为安全多方计算的发展提供了理论基础，使其逐渐成为密码学的一个重

26、要 分支.在目前个人数据存在安全隐患的环境下，对数据进行保密并实现数据 价值显得尤为重要，SMC就是实现此目的的关键技术.安全多方计算是关于 一组互不信任的参与者在保护各自私密数据的前提下进行联合计算的问题, SMC要确保各参与者输入数据的私密性以及计算结果的正确性.一方面，设计相应的安全多方计算协议是解决隐私保护问题的基本思路; 另一方面，安全多方计算的研究与发展均来源于生活中实际的应用场景.因 此，安全多方计算在密码学中具有重要的理论意义和实际意义.而安全多方计 算从理论研究到实际应用还有很长的路要走，目前主要广泛应用于电子拍卖、 门限签名、联合数据查询、私有信息安全查询、电子选举等领域.

27、随着安全多方计算在各个领域的迅速发展和广泛应用，许多安全多方计 算问题已经得到了深入研究，但由于其研究范围与生活息息相关，其中还有许 多问题有待解决.集合是数学中基本的研究对象,集合问题在各个学科中具有 基础作用，关于集合问题的保密计算一直是安全多方计算中的研究热点，包括 元素与集合关系、集合交集/并集、集合交集势/并集势、集合包含关系等问 题目前，集合问题的研究工作主要是两方整数集合问题的保密计算，关于多 方整数集合问题和有理数集合问题的保密计算的研究成果较少，且解决方案 的计算复杂性高.因此，需要设计更加高效安全的保密协议.集合问题的安全多方计算与生活息息相关，其来源于生活又改变着生活.

28、目前，关于集合问题的研究成果和实际应用还不多，且该领域的研究方法是多 样的，研究方向是长远的，所以集合问题还需要持续进行更深入的研究，在今 后的密码学领域依然是热点问题.1.2国内外研究现状安全两方计算问题是安全多方计算问题中的基本情形，安全两方计算问 题在1982年由姚期智教授首次提出叫 在1988年Goldreich和Goldwasser等人基于 两方计算问题提出了多方的安全计算问题，并深入研究了该问题，为研究更 多问题提供了理论依据2T,对安全多方计算的发展有重大意义.目前，安全 多方计算领域研究的主要问题有：(1)保密科学计算【1,5 - 8； (2)保密统计分 析【9-凹；(3)保密

29、数据挖掘W-14；保密计算几何115 18；其他安全多方计算 应用【1922等.集合问题是科学计算中的基础问题，集合问题的保密计算在保密的科学 计算中具有重要价值，在保密数据挖掘、保密选举、保密查询和模式匹配等方 面有重要的应用.近年来，关于集合问题的保密计算己经有很多研究成果，主 要的研究类型为：两方集合保密计算和多方集合保密计算，研究工作如下：两方集合保密计算在两方集合保密计算问题的研究中，主要工作包括保 密判定元素与集合关系23-24、保密计算集合交集及其势2431、保密计算集 合并集及其势【32- 33和保密判定集合包含关系3437等问题，文献23,24分别基 于对称加密算法和公钥加密

30、算法设计了元素与集合关系的保密判定协议，在 协议中需要公布集合的势.文献24基于不经意多项式解决了集合交集及其 势问题，若两参与者集合的势分别为幻和0协议的计算复杂性和通信复杂性 O(wloglogv)和0(幻+以 文献25研究了恶意模型下的两方交集问题，设计的 协议与文献24具有类似的计算复杂性.文献26降低了24的复杂性，所设计协 议的复杂性是集合势的准线性(almost linear)函数 文献27基于第三方硬件的 安全设置设计了集合交集保密计算协议，如果两个参与者的集合元素均属于 域。=O,iy,协议具有0（枫）的计算复杂性.文献2&31利用不同的密码学工 具设计了更多两方交集保密计算

31、协议.文献32-33分别设计了集合并集的保密计算协议，其中文献32将参与者 的集合表示成多项式的形式，并利用翻转罗朗级数和秘密共享的方法给出了 集合并集的保密计算方案；文献33借助全同态加密算法和多项式求值的方法 给出计算集合并集的协议.这些并集协议的计算复杂性都较高，并且无法保证 各参与者集合势的私密性.文献34-36分别基于不同的密码学知识设计了集 合包含关系的保密判定协议，由于多次应用加解密算法，导致协议计算复杂性 较高.文献37通过设定全集并利用编码方法设计了集合包含关系的保密判定 协议，协议的计算复杂性与全集的势同阶，当全集元素不太多时，有较高的计 算效率.多方集合保密计算在多方集合

32、保密计算问题的研究中，主要研究多方集 合交集/并集及其势和多方阈值并集等问题.文献38利用多项式不经意计算 的思想，首次研究 2）个参与者的多重集交集/并集及其势问题，并设计了 保密计算协议，若每个集合的势为从则所设计的交集/并集及其势协议都是二 次计算复杂性，交集/并集协议的通信复杂性是线性的，交集/并集势协议的通 信复杂性为0（n2fc）;文献38还设计了阈值集合问题的保密计算协议，与交集协 议的复杂性类似.基于文献38的工作，文献39,40设计了与参与者人数是线性 关系的集合保密计算协议，降低了计算复杂性.文献41将集合元素表示为多 项式函数曲线上的点，设计了集合交集计算协议，其计算复杂

33、性与集合规模成 拟线性关系.基于单向散列函数和Pohlig-Hellman加密方案，文献42设计了术打 2）方交 集势保密计算协议，协议具有。（漩）和O（n2v）的计算复杂性和通信复杂性.在 文献43中作者利用不经意排序和数据比较的思想，研究设计了集合和多重集 的各种保密计算协议，假设所有参与者共有m个元素，则所设计的协议的计算 复杂性和通信复杂性为。伽logm）,且协议要求有安全认证信道.在文献44中, 作者利用Bloom过滤器设计了集合交集/并集势的计算协议,计算效率较高，但 是其计算结果为近似结果，且参与者之间需要有安全信道.根据上述集合问题的研究现状，一方面，己有的集合保密计算协议大多

34、是 针对整数集上两方集合问题进行设计，很难将其直接推广到多方集合问题.关 于多方集合问题的保密计算协议还很少，己有的多方集合保密计算协议的计 算复杂性都是与集合规模成二次或拟线性关系，计算效率低，很难将其应用于 解决实际问题，所以研究更加安全高效的多方集合保密计算协议具有重要的 研究价值.另一方面，己有的集合保密计算协议都将集合元素限制在整数范围 内，关于有理数域上集合问题的研究还较少，限制了集合保密计算的适用范围, 所以研究有理数域上的集合保密计算问题具有重要的理论意义和实际意义.集合问题的安全多方计算不仅在信息科学领域具有重要的研究意义，在 其他交叉领域也发挥着重要作用，如保密计算文本相似

35、度问题、保护隐私的 医疗诊断问题、建筑规划的隐私保护问题等等.1.3本文的主要贡献本文主要研究集合问题的保密计算，深入探究整数集上多方集合问题的 保密计算和有理数域上两方集合问题的保密计算，构造更加安全高效且适用 范围广的安全协议.研究的主要内容如下：为整数集合和有理数集合分别设计了巧妙的编码方案，每个参与者将 自己的保密集合编码为一个特殊数组，并结合具有一定同态性的加密算法，将 集合保密计算问题转化为数组的保密计算问题.对于几种基本的整数集合运算设计了安全高效的计算协议，这些协议 对于两方集合问题和多方集合问题均适用，而且有较高的计算效率,应用严格 的模拟范例方法证明了这些协议在半诚实模型下

36、的安全性，并指出将本文协 议作为基础模块可以解决更多的集合计算问题提出了关于有理数以及有理点的编码方法和转化技巧.为解决有理数 域上的保密计算问题提供了新的途径.解决了有理数域上两方集合保密计算这类新问题.对于有理数域上几 类基本的集合运算设计了保密计算协议，所设计的协议能同时保证集合元素 以及集合势的隐私性，且具有线性或常数计算复杂性,通过严格的安全性分析 和效率分析表明这些协议在安全性和计算效率方面优势明显.并给出了协议 在有理点集合问题中的推广应用.1.4本文的组织结构根据本文具体的研究内容,将本文分为以下五个章节：第1章，绪论，主要叙述了安全多方计算的研究背景和研究意义，以及本文 所研

37、究的集合问题的研究现状和研究方向.第2章，预备知识，主要介绍了本文研究过程中需要的基础知识，包括：安 全多方计算模型及安全性定义，同态加密方案和几何中三角形面积计算公式.第3章，研究多方集合的高效保密计算协议，将集合保密计算问题转化为 数组的保密计算问题，设计构造了各种集合运算的保密计算协议.第4章，设计了有理数域上两方集合保密计算协议，并对其进行推广应用 于有理点集合的保密计算.第5章,对本文研究工作进行总结，并展望未来的研究方向和工作.第2章预备知识本章主要介绍集合问题的保密计算研究中需要的一些基本概念和基础工 具.基本概念：（1）安全多方计算模型：理想模型、半诚实模型、恶意模型；（2）

38、安全多方计算的安全性定义：双方计算、模拟范例，基本工具：（1）同态加密方 案：ElGamal加密方案、Paillier加密方案、门限密码体制； 三角形面积计算 公式.2.1安全多方计算模型及安全性定义本节主要介绍本文所需要的安全多方计算的基本概念【45】.2.1.1理想模型设想存在一个值得信赖的第三者（Trusted Third Party-TTP），在任何情况 下，他都不会泄露不该泄露的信息.理想的安全多方计算是指多个参与者利 用TTP进行联合计算.假设有n（7i 2）个参与者他们分别拥有私密数 据他们将自己的私密数据发送给TTP, TTP单独计算函数/:, Xn ） = （/1 （工1,n

39、）,然后将 2)个参与者P1,R分别拥有私密数据记X = Si,，孙).设/ = (/“.)是一个概率多项式时间函数，参与者利用协议刀保 密地计算函数/(X)= CA(x)./(x).在执行协议7T的过程中月所得到的信 息序列记为：view(X) = (% 己崩，就,(X),其中表示R产生的随机数，表示R收到的第j个消息，(X)表示己获得的输 出结果.对于部分参与者构成的子集= 乌，.，4, C饵，,R,记vieWp(X) = (r, view (X),views(X).定义2.仆5关于上述函数/和协议几对任意的= %. C 如果存在概率多项式时间算法S使得：S(R,林)/(X)x&o,i*广

40、 (况e呢(X)xe(o,i*广(2-1)成立，则称协议R可以保密地计算函数其中刍表示计算上不可区分.在定义2.1中，如果取任意7Z- 1个参与者构成的集合，都存在满足(2-1)式 的S,则协议兀可以抵抗任意的合谋攻击.2.1.3恶意模型恶意模型下的安全多方计算协议主要通过迫使各参与者按照协议要求执 行协议，类似于半诚实参与者执行协议的过程.在任何协议中，以下三种恶意 行为：(1)参与方拒绝执行协议；参与方篡改自己的输入数据；(3)参与方执 行协议过程中临时中止协议，是无法避免的.因此，在考虑恶意模型下的安全 协议时，对上述三种恶意行为不予考虑.在协议执行中，具有恶意行为的参与 者会进行主动攻

41、击，所以该参与者也称为主动攻击者.目前许多研究成果己经对半诚实模型下的安全多方计算协议进行了深入 研究，关于恶意模型下的安全多方计算协议的研究还较少.在文献45中，作者 设计了一个编译器，可以将半诚实模型下的安全协议进行编译，得到恶意模型 下的安全协议.该编译器的基本原理是设法防止协议中参与者的恶意行为，使 得参与者按协议要求执行协议.因此半诚实模型下安全计算协议的设计是基 本而重要的.本文主要研究半诚实模型下的安全多方计算问题.2.2同态加密方案目前，安全多方计算中最常用的工具是同态加密方案(homomorphic encryption), 同态加密方案由Rivest在文献46中首次提出.一

42、般地，一个公钥加密方案 由密钥生成算法&()、加密算法E，)、解密算法。()三个算法组成.其中：密钥生成算法G(少密钥生成算法G(.)根据一个安全参数兀生成公私钥初c和 sk,以及明文空间M和密文空间G即(冰，sk, M. C) G().加密算法利用G()生成的公钥风对于明文me M进行加密，得到对 应密文c = E(m),即：c E(m).解密算法():利用G()生成的私钥对于密文进行解密，得到对应 明文m = D(c),即：m D(c).本文主要利用ElGamal加密方案网、变体EiGamal加密方案街刨、painier加 密方案网和门限密码体制凤，521,上述的加密方案均为概率加密方案且

43、具有一 定的同态性，下面详细介绍这几种加密方案.2.2.1 ElGamal加密方案ElGamal加密方案闽具体过程如下：密钥生成：密钥生成算法G()根据安全参数八生成素数p并选择随机数A: 6 和生成元g Z；,计算h = gk mod p.其中公钥pk =(9 ,九)，私钥= k.加密，选择随机数，利用公钥泌=(gji)对消息G Z；)进行加密，得到c = E(m)=(勺。2) (gr mod p. mhr mod p).解密：利用私钥s/c = A;对密文c = E(m)=(勺 2个参与者R0 1,71), R分别拥有私密集合&他们希望合作计 算交集1X1说，且保密各自的&假设集合S4 Z

44、 =伯,6,其中ei e2 * - 2参与者R0 Gl,n)利用公钥加密数组X,中的元素L得到加密数组G = (佐1, , jPl将四=0发送给每一个R顶=2,n,从At处接收到= 0G_i；将G与Wi_i的对应分量相乘，得到数组店=G .G_i a；将数组形发送给F(i+l)modn.参与者R将附=G .S =(皿,叫Q公开.参加者R0 G l?n)利用各自的私钥份额对W的每个分量凹联合解密得 到 A: 故% e Jti Si ni舞为大于1的随机数，协议2保密计算集合并集输入：参与者月0 1/）分别输入私密集合&所有参与者应用ElGamal门 限密码体制，联合生成加密方案的公私钥pA和麻.

45、输出：集合并集u% &按照32）式，参与者1,用）对集合&进行编码得到*参与者R0 l,n）利用公钥泌:加密数组*中的元素1,得到加密数组G = （91）, 7 Gm），Fi将Wi = G发送给R.每一个R0 = 2,（a）从R_i处接收到印i_i =CiG_i；（b）将G与风_i的对应分量相乘，得到数组论=G . . Q_i %（C）将数组说发送给F（中）m。顼参与者P1公开W = C1 Cn =（W1,Bm）.参与者月（2 e 1,河）利用各自的私钥份额对w的每个分量啊t联合解密得 至虹（1 k 2个参与者R0 GR分别拥有私密集合&他们想保密计算集合交集的势且不泄露各自集合&其中团C Z

46、.计算原理类似于多方集合交集保密计算协议1,关于多方集合交集势的保 密计算协议只需对协议1进行简单修改即可得到.而交集势的保密计算协议与 交集保密计算协议1的主要区别在于需要保密交集中的具体元素，仅可得到交 集中元素的个数.3.2.2协议设计协议3保密计算集合交集势输入：参与者Pi(i e 1冲分别输入私密集合爵所有参与者应用ElGamal门 限密码体制，联合生成公私钥泌和输出：集合交集势ink S.按照(3-1)式，参与者R(2lm)对集合$进行编码得到X.参与者e l,n)利用公钥p/c加密数组X中的元素1,得到加密数组G = (G15 , , Gm).0把Wi =G发送给每个R0 = 2

47、, .,n - 1,收到由R_i发送的IS = GG_i；将G与W-i的对应分量相乘，得到数组W, = G弓一G；将数组1私发送给R+i.R计算= C G =(皿，*小)，并选取随机置换7T乍用于阿，将置 换后的数组记为* = 7Cn(Wn) =(5 . Jnm).每一个 Pi,i = n - 1, .y 2,接收到R+i发送的峪+i = (%+i)i,. .,%)；利用公钥林加密m个1得到不同的密文，并用1的不同密文乘V+i中的元素，再对其随机置换得到E =缶(叩+i)】E(l),.,*+】)mE(l),其中缶为随机置换.(C)将数组*发送给R利用公钥泌加密m个1得到不同的密文，并用1的不同

48、密文乘以屿中的 元素，再随机置换得到，=(h.g)=心(如1E,，四危)，其中“I为随 机置换.R公开史 参与者RQeLM)利用各自的私钥份额对，的每个元素联合 解密得到m个数afc(l k 2个参与者H G l,n),每个H分别拥有私密集合金，他们想保密 计算集合并集的势且不泄露各自集合琮其中另Q Z.并集势计算协议的设计思想类似于交集势的设计思想，下面仅叙述协议 过程：协议4保密计算集合并集势输入：参与者Pii l,n)分别输入私密集合品，所有参与者应用ElGamal门 限密码体制中，联合生成公私钥泌和输出：集合并集势|U?=iS1-按照(3-2)式、参与者L)对集合&进行编码得到匕：.参

49、与者AW e 1,涮利用公钥泌加密数组匕:中的元素1,得到加密数组记)寸Cj (G1, ?R将Wi = G发送给R.每一个43 = 2,.,72 1,从At处接收到= G - Gi；将G与华_i的对应分量相乘，得到数组审=G Gt G；将形发送给月+iR计算咧=6凡加),并选取随机置换办作用于功切将置 换后的数组记为K = 7rn(Wn) = (vnl，,vnm),每个E0 = 72-1, .,2,收到只+ 1发送的峪+1 =利用公钥泌加密m个1得到不同的密文，并用1的不同密文乘以峪+1中的 元素，再进行随机置换房得到峙=缶：(0(并1)1归(1)，+lgE(l)(C)发送站给九一1).R利用

50、公钥泌加密m个1得到不同的密文，并用1的不同密文乘以数组14中 的每个元素，再进行随机置换7T得到，=(0, . . . , Vm) = 7T1(巧1E,凡2小与(1).R公开V.参与者月01顷)利用各自的私钥份额对V的每个元素联合 解密得到771个数%(1 k 2个参与者R(z 1顷),月分别具有私密集合&其中集合$ C Z.他们商定一个阈值Z,希望合作计算所有集合中总次数达到Z的元素构成的集合，并保密其中各元素的具体个数.我们称该问题为阈值并集问题，记举例说明，在6个集合& = 1,3,6,8, & = 1,2,4,6,7, S3 = 5,7,9,$4 = 2,3,6,7,务=1,9,跣=

51、3,6,8.若设定阈值t取值为3,那么上述集合构成的阈值并集为1,3,6,7.计算原理阈值并集问题与交/并集问题有所不同，构造新的1-0编码方 案，每个R将私密集合品编码为m维数组U =(如，皿帛.编码过程如下：对 于S L,n,k e令(3-3)公 S*；0, e* 若公属于阈值并集Zr(Si.,S”)，则至少有z个力，.3 e l,n,使得弘e Sjs(s e 按照(33)编码方式，有可M = 1,即 t成立,反之，若xuik i, 则元素弘至少属于n个集合S.,Sn中的扮集合，因此弘方(昌,Sn).故，e、k ，Si) ；_根据上述分析，对每个A; e 参与者R0 1,福)利用变体ElG

52、amal门 限密码体制联合计算%加即可根据和式的值判定元素是否为所求集 合&(&.岛)的元素.在文献38,53中提出了一个IsEq协议，该协议可以保密判 定两个不同的密文对应的明文是否相同，即对于两个密文当。1,。2对应 明文相同时，输出IsEq(C1?C2) = 1;当对应明文不同时，输出IsEq(G,%)= 0(具体协议可参看文献38,53).本节利用IsEq协议的思想解决阈值并集计算问题，通过逐个比较弘出现总 次数的密文狄与密文B = E(Z)(Zl,t-1)是否相等，可以得到ek e &(Si,，Sn) = VZ e l,t - l,IsEq(wfc, Ei) = 0.3.3.2协议设

53、计协议5保密计算阈值并集输入：参与者pie 1,河)分别输入自己的私密集合&所有参与者应用变 体ElGamal门限密码体制，联合生成公私钥执和就，并计算屈=瓦Z)(Z 6 1-1).输出：阈值并集为(易,按照(3-3)式，参与者e 1,)对集合s进行编码得到*参与者RQ 1,圳)加密数组无中的各个元素，记为G =(弓1,.，4血)-R将i = G发送给3.每一个Pi,i = 2,. n,收到已一 i发送的叫t = G，-Gt；将G与1441的对应分量相乘，得到数组Wi = G G1 G;(C)将昭发送给P(Hl)modn-R公开TV = Ci Cn = (wi,wm).对于每一个i e l,n

54、, k e l,m,月选择随机数以 N+ = 1,2,.;计算快=(Eili 则钦 /(Si,当:=b(Vk)手0时,说明存在Z e哗- 1,有IsEq(欧,瓦)=I,即)=Ek以 2个参与者R(z e l,n)? R分别具有私密集合&其中集合昌Q Z.他们商定一个阈值匕，希望合作计算所有集合中总次数达到的元素构成 的集合，并得到其中各元素的具体个数.我们称该问题为阈值多重并集问 题记为/MS/.*).如果是集合jTM(Sl.,Sn)中的元素，记弘的总个数 为(钦).举例说明，在6个集合& = 1,3,6,8, $2 = 1,2,4,6,7, S3 = 5,7,9,$4 = 2,3,6, 7,

55、 $5 = 1,3,6,9, $6 = 3,6,8.若设定阈值匕取值为3,那么上述集合构成的阈值多重并集为,5*6)= 1,1,1,3,3, 3,3,6,6,6,6,6, 7,7,7),其中TM=3, TM(3) = 4, TM(6) = 5, :=3.计算原理类似于阈值并集保密计算问题，在阈值多重并集的保密计算 中，每个R按照(33)中的1-0编码方式，将自己的私密集合，编码为m维数组弟= (%：1, .Uim)-易知，若膈e,$门)且=诳，则有且仅有K品e l,n, 使得弘 Sjs(s e 1&).由编码方式(3-3)可知，若s = 1, % 相应地有的m = 1, 否则灼M = 0,即满

56、足E-=1 Uik = nk.反之，若X1以=腿则，.，$中恰 有秩个集合含有元素以，因此ek e frM(Su .,.,Sn)且故，ek Sn) A TAlc = r坎：ik n*具体协议如下：协议6保密计算阈值多重并集输入：参与者R(M Is)分别输入私密集合&所有参与者联合运行变 体ElGamal门限密码体制，生成公私钥泌和航，并计算回=E(Z)(/ e l,i- 1).输出：阈值多重并集按照(3-3)式,参与者R(i el,n)对集合S,进行编码得到骞参与者Pi(i l,n)加密数组L中各个元素，记为G： =(G：i,.R将1伯=G发送给R.每一个R,?； = 2,.,n,接收到R_i

57、发送的倒一1 = G G-i；将G与匡1的对应分量相乘，得到数组邕=G , . CU . G;(C)将明:发送给化+l)m。顼R公开沙=。1。“二(叫.，也m).对于每一个2 l,n, k 6 1,m,E选择随机数孙，使得初 n;计算狄=wk 方(Xi q沃)(IsEq(迪加 &) + . + IsEqg Ei).所有参与者利用自己的私钥份额联合解密每个得到以(1 k m).如果Z AnB = AAuB = B,因此直接求集合交集或并集即 可(利用协议1或协议2).简述如下：按照(3-1)式,Alice对集合4进行编码得到数组X,并对数组X中的元素1进 行加密，得到数组C =(勺，将其发送给B

58、ob.Bob根据3 = 61：.,儒中每个元素在全集中的位置，得到饥=zki eZi E 1, G l,m)5 Bob计算帝=cfcl -,将其送给Alice.Alice解密1得到D(W由4 C 8当且仅当O(W) = 1,则得到结果.电子选举问题随着计算机网络的发展，电子商务变得越来越广泛,其中电 子投票成为匿名投票选举的一种重要方式.下面结合本章协议的设计思想，简 述电子投票问题的保密协议.情形(i):在大学的学生会社团中包含着许多不同的部门(学习部、生活部、 体育部等)，每当学生会换届选举开始，每个部门大多会采用电子匿名投票方 式进行.关于某个部门的某个职务，在所有候选的人员中只有票数达

59、到一个数 量才能当选.该选举活动属于多人同职选举，最后只需公布当选人的名单.情 形(ii):如果对多个部门同时进行选举部长，需要根据候选人得票数高低进行 选举，最后需要公布当选者名单及票数.根据上述两种情形，可以利用本章阈值并集协议和阈值多重并集的协议 进行解决.首先对候选人进行编号，得到全集Z =住】,投票成员记 为每个投票成员可以对多人进行投票，则B根据投票结果得到集 合X，C Z,设定当选者票数要大于等于阈值Z.协议组合应用在一项走访宣传活动中，Alice和Bob分别在不同地区进行了 宣传，他们想知道共同走访宣传的地区而不想泄露各自的走访区域记Alice和 Bob的走访区域集合分别为&瓦

60、则该问题可以抽象为保密计算ACB.如果两 人的交集势接近各自的集合势时，他们可能会担心自己的区域泄露.所以可以 约定，当|/in可满足某个条件：T时，才允许两个参与者得到输出结果.上述问题 可以用交集势协议和交集协议相结合进行解决，基本思路如下：Alice生成公私钥和s/c;按照编码方式(3-1), Alice对集合4进行编码得到数组X,并加密其中的 元素1,将加密数组发送给Bob;按照编码方式(3-1), Bob对集合8也进行编码得到数组*根据自己编 码为1的位置，将Alice发送来的数组中对应元素挑选出来，再分别乘以1的密文 得到新的加密数组(Bob为隐藏集合3的势，可添加一些随机数元素)