两方交集保密计算协议的设计和实现
Design and Implementation of Two-Party Set-Intersection Private Computing Protocol
【中文摘要】 两个数据集的交集运算是一种经常被运用到实际的应用程序和控制程序中的数学运算的计算机算法之一。处于对信息的安全考虑,参加计算的双方只希望得到与对方进行共有的数据集,同时又要尽可能少的暴露自己的全部数据集,因此能够保密的两方数据集的交集的运算的出现就显得十分必要。目前交集的保密计算的方案已有些人提出,但大多受到计算复杂度过大,计算效率低下,安全程度无法衡量,适用范围狭窄等因素的制约,少有可实际应用的方案及其实现。本文选取最近提出的较为实用的两方交集的保密计算协议的理论,并依此设计并实现出此协议。在效率上,由于使用了在椭圆曲线的上的指数计算,相比整数的指数运算,在同等的安全要求下,具有计算数据量小,运算速度快等优点。在安全上,采用了灵活的设计方案,对于密钥长度等安全参数可以自由调节,不仅能够满足对于计算能力有限的手持设备要求,还能够应用在对于安全性要求较高的工业仪器设备上。除此之外,此保密的交集计算算法是通过了数学证明,其安全程度是可以衡量的。本文在已提出的基于Boyen-Waters的匿名基于身份的加密方案IBE(Identity-BasedEncryption)的两方数据集交集保密计算协议的理论基础上,补充了原文中未完全提及的零知识证明和承诺方案的相关理论,使之成为一个完整的拥有两方保密交集计算能力的具体协议,又在此基础上提出了可行的协议实现方法。最后将针对此协议的实现程序设计出的一套全方位的自动测试方案,和所用到的测试数据及最终得出的测试数据。测试的结果反映出协议的在实际情况下的工作效率及性能上的瓶颈。
【英文摘要】 The intersection operation between two data sets is one of computer algorithms used in actual applications and control programs.Most times,each party jointed the intersect operation only wishes could get a result of sharing data set,and on the another hand also wishes could reduce exposure of whole data set to the least.Therefore 2-party set-intersection private computing is very useful and necessary.Present,a few of private computing schemes were proposed by some researchers,but oversized complexity,low production,unweighable securirty level,narrow applicable scope and so on factors restrict their applications,and their implementations are very less.This paper presents the more practical theories of 2-party set-intersection private computation protocol which proposed recently,and designs and realizes this protocol according to this.In efficiency,used of index operation on the elliptic curve,which has an advance in computational complexity and is speeded in comparing to index computation on integer under the same level security requirements.In the security,this proposal used the flexible design, freely adjustable security parameters and key length.Not only can satisfy requirement on the limited computation ability devices,but also can be applied on high-level secure required industrial equipments.Furthermore,the security of this algorithm is proved in mathematics way,for this reason its safety rate can be weighed.According to previous proposed based-on Boyen-Waters anonymous IBE(Identity-Based Encryption) 2-party set-intersection private computing theory,this paper supplemented relative theory without mentioned in original paper about Zero Knowledge Proof and Commitment,and consisted them into a completed protocol with the ability of 2-party set-intersection private computing.In addition to the theory feasible implementation of protocol has been proposed.Finally,an automatic all around test plan made for the application implemented the protocol,and the test result reflected the efficiency of protocol in the actual working situation and the bottleneck of its performance.
【中文关键词】 多方保密计算; 交集的保密计算; 椭圆曲线; IBE; 承诺方案; 零知识证明
【英文关键词】 Multiparty Private Computing; Set-Intersection Private Computing; Elliptic Curve; IBE; Commitment; Zero-knowledge Proof
【毕业论文目录】
摘要 4-5
Abstract 5
引言 8-10
1 理论背景 10-20
1.1 椭圆曲线理论 10-15
1.1.1 椭圆曲线简介 10-11
1.1.2 实数域上的椭圆曲线 11-12
1.1.3 素数域GF(p)上的椭圆曲线 12-13
1.1.4 特征为2的有限域GF(2~m)上的椭圆曲线 13-15
1.2 基于身份的加密系统 15-16
1.3 零知识证明系统 16-17
1.3.1 交互式的零知识证明 16-17
1.3.2 非交互式零知识证明 17
1.4 承诺方案 17-20
2 协议的理论构造 20-35
2.1 协议总体结构 20-24
2.2 匿名IBE方案 24-25
2.3 盲钥生成子协议 25
2.4 完美零知识证明子协议 25-32
2.4.1 ZKoP_Ⅰ 27-29
2.4.2 ZKoP_Ⅱ 29-30
2.4.3 ZKoP_Ⅲ 30-32
2.5 抗翻供承诺方案 32-35
3 软件实现 35-48
3.1 协议结构描述 35-38
3.1.1 运行机制 35-37
3.1.2 模块组成 37-38
3.2 数据结构定义 38-41
3.3 IBE加密系统 41-43
3.3.1 初始与清理 41
3.3.2 盲钥生成 41-42
3.3.3 数据加解密 42-43
3.4 承诺方案 43-44
3.5 零知识证明系统 44-45
3.6 数据流 45-48
4 性能分析与测试 48-57
4.1 环境配置 48-49
4.2 测试方法 49-51
4.2.1 生成测试应用程序 49-50
4.2.2 启动测试脚本 50-51
4.3 用例描述 51-53
4.4 结果分析 53-57
结论 57-58
参考文献 58-60
致谢 61-62
