【作者】 李强；

【导师】 陈克非；

【作者基本信息】 上海交通大学 ， 计算机系统结构， 2003， 硕士

【摘要】 本文总结了目前安全多方计算协议的研究现状,介绍并分析了已有的四类安全多方计算协议:“基于OT 的安全多方计算协议”、“基于VSS 的安全多方计算协议”、“基于同态门限加密的安全多方计算协议”以及“基于Mix-Match 的安全多方计算协议”。在分析已有协议的优缺点的基础上,本文对四类安全多方计算协议均有较大的改进。这些改进主要有: (1)“基于OT 的安全多方计算协议”:引入访问结构,使该类型的协议能够实现任意的访问结构,从而避免了原来协议所固有的缺点:只能实现( n, n )门限这一特殊的访问结构只要有一个恶意参与者主动攻击,整个协议将无法进行下去。改进后的协议可以实现任意的访问结构。(2)“基于VSS 的安全多方计算协议”:1)引入访问结构,使该类型的协议能够实现任意的访问结构,从而避免了原来协议所固有的缺点:只能实现(t , n )门限这一特殊的访问结构,其中n ≥2t ? 1。2)提出一种新的“二元乘法运算”协议AtomMul ,使用该协议可以从根本上克服原来的乘法协议对n ≥2t ? 1的依赖,进而为实现任意的访问结构提供基础。3)给出一种计算域上的“一元求逆运算”,使得“基于VSS 的安全多方计算协议”可以计算协议域上的任意函数。(3)“基于同态门限加密的安全多方计算协议”:1)引入访问结构,使该类型的协议能够实现任意的访问结构,从而避免了原来协议所固有的缺点:只能实现(t , n )门限这一特殊的访问结构,其中n ≥2t ? 1。2)给出一种计算域上的“一元求逆运算”,使得“基于VSS的安全多方计算协议”可以计算协议域上的任意函数。(4)“基于Mix-Match 的安全多方计算协议”:1)引入访问结构,使该类型的协议能够实现任意的访问结构,从而避免了原来协议所固有的缺点:只能实现(t , n )门限这一特殊的访问结构。2)给出“建立盲表正确性”的验证方法,从而保证这种类型安全多方计算协议的核心部分——盲表的正确性。最后,在分析已有协议的特征的基础上,本文提出了一种全新的安全多方计算协议。该协议的最大特点是计算域上的乘法运算、求逆运算简单,加法运算复杂。其次,新协议对运算的输入自变量个数的限制取消了,可以实现“d 元乘法运算”、“d 元加法运算”。更多还原

【Abstract】 This paper summarized the current research status of multiparty computation protocols, introduced the four types of multiparty computation protocols and analyzed them. The four types of multiparty computation protocols are: multiparty computation protocol based on OT (Oblivious Transfer), multiparty computation protocol based on VSS (Verifiable Secret Sharing), multiparty computation protocol based on threshold homomorphic encryption and multiparty computation protocol based on Mix-Match. On basis of the analysis of the strengths and shortcomings of the protocols, the paper improved on the four types of multiparty computation protocols. The improvements are as follows: (1) Multiparty computation protocol based on OT: Introduced access structure to this type of multiparty computation protocol, thus avoid the previous protocol’s connatural disadvantages: The protocol can only realize the special ( n, n )-threshold access structure. With this access structure, even one malicious participant can stop the protocol. The improved protocol can realize any access structure. (2) Multiparty computation protocol based on VSS: 1) Introduced access structure to this type of multiparty computation protocol, which makes the improved protocol realize any access structure and avoid the previous protocol’s connatural disadvantages: can only realize the special (t , n )-threshold access structure where n ≥2t ? 1. 2) Provided a new protocol of binary multiplication operation AtomMul . With the help of AtomMul , this type of protocol can overcome the tie of the original protocol’s: n ≥2t ? 1. AtomMul provides the possibility of realizing any access structure. 3) Provided a protocol of unitary reversion operation, and thus the multiparty computation protocol can calculate any function defined on the fields of the protocol. (3) Multiparty computation protocol based on threshold homomorphic encryption: 1) Introduced access structure to this type of multiparty computation protocol, which makes the improved protocol realize any access structure and avoid the previous protocol’s connatural disadvantages: can only realize the special (t , n )-threshold access structure where n ≥2t ? 1. 2) Provided a protocol of unitary reversion operation, and thus the multiparty computation protocol can calculate any function defined on the fields of the protocol. (4) Multiparty computation protocol based on Mix-Match: 1) Introduced access structure to this type of multiparty computation protocol, which makes the improved protocol realize any access structure and avoid the previous protocol’s connatural disadvantages: can only realize the special (t , n )-threshold access structure. 2) Provided a protocol to validate the correctness of building a blind table, and so ensure the correctness of blind tables that are cores of this type of multiparty computation protocol. In the end, based on the analysis of the character of the existed protocols, this paper provided a new multiparty computation protocol. This outstanding character of this protocol is: It’s easy to compute the multiplication and reversion operation while it’s complex to calculate addition operation. Another strength of this protocol is that it has no limit on the number of inputs to an operation, it can realize d entities multiplication operation and addition operation.更多还原