可调节安全等级的多方安全计算

摘 要：对于多方安全计算目前国内外已有许多研究成果，从安全方面去看很多解法是尽善尽美，但在实际的运行中却不尽人意。为此，本文提出了多方安全计算的一种新的安全范型,其中利用了允许部分信息泄露的可接受的安全模型. 该模型是通过降低安全方面的约束来实现更好的性能。在新范例中，安全是可调整的，用户可以根据他们可接受安全的定义调整安全等级. 此外，文中还定义了整篇论文中所使用的唯一的问题，即标量数乘问题。特别地证明了新范型在算法模式标准中是怎样导向实用解法的，并描述能服务目标的已有的算法模式。

关键词：多方安全计算；安全等级；安全范型

中图分类号：TP393.08 文献标识码：a DoI: 10.3969/j.issn.1003-6970.2012.02.038

Secure multi-party computation of adjustable the security level

CHeN Jie(College of the People Armed Forces of Gui zhou University, Guiyang of Guizhou Province, 550025)

【Abstract】at present, there are many research about secure multi-party computation In China and abroad.as for security aspect In China and abroad, many solutions are ideal,but not good at real life impelmentation. therefore, In this paper a new paradigm is proposed for the secure multi-party computation, in which an acceptable security model that allows partial information disclosure is used. It can achieve a much better performance by lowering the restriction on the security. Moreover,in new paradigm,the security is adjustable,such that users can adjust the level of security based on their definition of the acceptable security. Furthermore,a single problem is used throughout this paper, it is defined the scalar product problem. In particular, how the new paradigm can lead to practical solutions in the computation model level is demonstrated and the existing computation models that can achieve the goal is described.

【Key words】Secure multi-party computation; security level;

0 引 言

1982年，A.Yao首先在文献[1]中介绍了多方安全计算的概念，随后，这个问题得到了广泛的推广与研究[2,3]。对目前国内外已有的多方安全计算研究成果，从安全角度来看很多解法是尽善尽美，但在实践中的运行却不是人们所预期的那样有效。因而，完美的安全却并不一定实用，也就是说，满足了理想的安全而失去了性能和效率[4]。

对于多方安全计算，一切解法所面临的最大挑战是如何满足安全需求。就形式定义的安全性而言，以往的多方安全计算研究是提出理想模型和实践模型。在理想模型中，实际参与方联合了一个可信任第三方来执行算法；在实践模型中，实多方安全计算协议是生效的（存在不可信的第三方），若可能伴随有那样一个攻击者的实执行可在实践模式中被模拟，则实践模型中的协议被称为就安全角度而言的备忘录式的规定[5]。广泛地说，在实践模型中无论出现什么样的信息泄密也会在理想模型中出现. 基于以上安全定义的安全模型称为理想安全模型。为了避免理想安全模型与实践安全模型的混淆，我们强调，基于理想安全模型的算法并不仅仅用于一个可信任方。

许多多方安全计算问题的研究是基于理想安全模型的，注意到满足这种安全模型是不困难的，而满足其有效性是困难的. 根据理论的多方安全计算问题研究，一切的多方安全计算问题在理论上使用电路计算协议能被解决，但对于多方安全算法中的特殊实例用这种普通的解法是不切实际的。因而，为实现有效性，对这种特殊实例的特殊解法应该被开发[6]。

然而，基于理想模型的实用解法是否存在仍是未知的。

1 新安全范型的提出

去寻找替代传统方法的实用解法，我们提出这些问题：我们为什么必须满足这种理想安全？实践中理想安全真的很必要吗？现实世界中，满足理想安全固然是很好，但若理想安全是代价太高而不能达到的话，人们更愿意选择达到一个可接受安全级别的低成本解法。换言之，为了一个较好的性能而牺牲某种安全或者泄露秘密数据某些有限的信息在实践中是经常被采纳的。距离说，假设秘密信息是一组成员，只要真实的原 始数据不被泄露的话，泄露这组成员中的一些统计信息是可接受的。

因而，我们提出了一种新的安全模型：基于一种可接受安全模型的多方安全计算问题.这种新范型如图1(Fig.1)所示.我们称新问题为可实践的多方安全计算问题（PSMC），PSMC涉及到任意输入计算的任意函数，在一个分布式网络中，各个参与方拥有一个输入，并确保只有有限的信息被泄露给算法中的一个参与方。

图1 可接受安全

为便于定义可接受安全的第一步，我们使用如下通俗的定义，称一个协议达到了可接受的安全，若一个对手在具有下面特征的域内只能缩小所有可能的秘密数据的值的范围：

（1） 此域中大量的数值是无限大的，或者此域中的大量的数值是如此的大使得强大的攻击在计算上是不可行的。

（2）对于应用域的范围是可接受的，可接受范围的定义与具体的应用相关。

我们假设可接受范围的定义与应用相关联是由于对于一个应用的可接受的范围可能对于其它的应用是不可接受的。比如，在区间[0，9]中的一个数对于一个应用不会泄露重要信息，但对另一个应用可能泄露足够多的信息。因此，从泄露给对手的域的范围应该被调整的意义上来说，这个定义实质上包含一个满足这种安全定义的解法是可以调整的。因此，用户可以调整一个协议，满足具有最小成本的安全需求，为证明新范型如何导向实用解法，我们描述了基本算法的解法，这些算法服役于很多SMC问题的构件。特别地，我们将证明新范型在算法模型标准中是如何导向实用解法的，并且描述能服务我们目前已有的计算模型。

2 数乘问题

为证明新范型，我们将描述支撑新范型的各种各样的方法，也讨论这些方法是怎样操作的，为了容易比较这些方法，我们将使用单独的一个问题，然而，正像我们后面将叙述的，我们的方法能解决一类问题，而不只是这个具体的问题，这个问题称为标量数乘问题，定义为：

问题1（标量数乘问题）U1有一个向量A=(a1,…,an)和U2有一个向量B=(b1,…,bn).U1（但不是U2）即将得到结果r=A・B+v，v是一个随机的标量，仅U2知道，U2的随机量v的作用是：若A・B是一个U1没有猜测到的局部结果，那么给予他A・B+v避免了U1知道局部结果（即使实际上执行了标量数乘），之后，在多步协议的末尾，v的作用被U2有效的删除而没有泄密给U1。

3 计算模型

3.1 计算模型

在两方安全问题的研究中，经常使用一个两方模型，因为就安全方面而言它提供的是一个理想的模型。两方模型只有两个参与者组成（见图2（a））(Fig .2(a)),即U1和U2在没有得到第三方帮助下依靠他们自己执行计算. 如果两方模型可以提供一个实用解法，那么就不需要另外的模型. 然而，找到这种模型的解法是很困难的。

由于我们的研究目的是要达到实用的安全，因而将不只局限于两方模型，我们要考察其它计算模型，研究其是否能够实现这些模型的实用解法，与两方模型比较起来，一些计算模型可达到的安全级别较低。但是若性能的增加胜过安全方面的损失，且安全方面的损失在某种情形中是可接受的话，则基于这些模型的解法较可能在实践中被采用。

图2(b)中描述的商品服务器模型是一个有趣的模型。

图2 计算模型

模型中有一个额外的服务器（商品服务器），属于第三方，在商品服务器上列出的唯一的需求是它不能串通任一参与方，此服务器有如下吸引人的特点：其一，，它不参加参与者间的计算，但是它为参与者们提供数据来保密它们的秘密数据。其二，商品服务器所提供的数据不依赖参与者们的秘密数据，所以，商品服务器不必知道这些秘密数据。这样的特点避免了商品服务器今后无论什么时间易遭争议的形象，以防万一某一参与者的秘密数据以某种方式泄露出去。另外，由于一个商品服务器没有太多的信赖是需要的，因此这一特点使得容易找到如此一个服务器，具备以上这些特点，商品服务器可产生独立的脱机数据，并且作为商品卖给参与者（因而取名为“商品服务器”）。特别指出的是这样的商品服务器不能串通任何一方，否则，模型就成了两方模型。在现实中，找到这样一个商品服务器是很可能的.

下面，我们将描述基于此模型的标量数乘问题的解法，应该指出此协议的执行比起两方模型的其它协议的执行更有效。

协议1.（标量数乘协议―商品服务器方法）

输入：U1有一个向量A=(a1,…,an)，U2有一个向量B=(b1,…,bn)；

输出：U1(但不是U2)获得A・B+v,U2得到v。

商品服务器生成一对随机向量S1和S2，并使s1+s2=S1・S2，其中s1和s2是随机地产生的，然后服务器发送S1和s1给U1,发送S2和s2给U2。

U1发送A′=A+S1给U2,而U2发送B′=B+S2给U1

U2产生一个随机数v′，并计算A′・B+v′，之后把结果发送给U1. U2也使得v=v′-s2

U1计算

(A′・B+v′)-(S1・B′)+s1=A・B+(v′-S1・S2-s1)

=A・B+(v′-s2)=A・B+v

定理 如果所有随机数是从实数域中产生的，那么协议1是安全的并使得U2不知道A[i]对任意i，和U1不知道B[i]对任意的i，这里A[i]和B[i]分别表示向量的第i个元素。

证明：

要求1：协议1不允许U2知道A的信息

因为A′=A+S1是U2所获得的全部信息，并由于随机性和S1的保密性, U2不能查找出A的信息

要求2：如果协议1允许U1知道B的信息，即U1可找到向量A′，使得通过发送A′给伴随协议的U2，对某一个i，U1能查找出B[i]。从形式上说，协议是不安全的，那么就存在一个决定性的算法，考虑A′，对任意B，若算法的输入是A′，B′=B+S0和Z=A′・B+v′，则对某一个i，算法输出B[i]。

接下来，我们构造一个任意的具有B-[i]≠B[i]的B-. 使得

S-2＝B′－B-

和v^′=A′(B-B′)+v′。因为B-+S-1仍等于B′，且A′B-+v^′=Z，所以算法仍应输出B[i].根据决定性的算法，输出为B-[i]=B[i]. 但由于B-[i]≠B′[i]，于是得到一个矛盾，换言之，决定性的算法是不存在的。

综上要求1和要求2，我们得出结论，协议1不允许U2知道A的信息，它也不允许U1知道B的信息，所以定理的结论成立。

3.2 安全性与复杂性分析

如果随机数不是从实数域中产生, U1可能获取一些有关B的信息。比如，向量B的元素是在域[0，90]中，我们也知道随机数是从域[0，280]中产生，如果向量B+S2的一个元素是320，那么我们推知向量B的原始元素一定比40大。

还要特别说明以上的协议不涉及一方的输入到处乱串的情形。例如，U2发送B-+S2取送B+v2，其中B-是一个任意的向量。在以上的举例中，参与者中谁也不能获取对方的秘密输入信息。

在协议的第三步中，额外的随机数v′的用途是为U2保密了A′・B的真实值，要是允许U1知道A′・B的真实结果，如果同一B用来计算几个标量数乘的话，U1就可以知道B的部分信息或者可能是B的全部信息。上面的协议是假设商品服务器没有串通U1和U2中的任一方。然而，我们可以提高协议的安全性，方法之一就是使用多个商品服务器而不只是一个商品服务器。例如，如果我们用m组商品服务器，这样就将向量A和B缩减为m对较短向量，通过执行上面的协议，每一个商品服务器可帮助计算m个较小向量中的一对标量数乘，这m对标量数乘之和是最终A和B的标量数乘。

这种方法的通信成本只有4n，具有这种开销的解法是充分的有效而成为实用。

4 总结

本文主要研究了一类特殊的安全多方计算――可调节安全级别的安全多方计算。首先提出了一种新的安全范型：基于一种可接受安全模式的多方安全算法问题，称新问题为实践的安全多方算法问题（PSMC）；其次描述了新范型的解法能解决的一类问题――标量数乘问题。最后介绍计算模型，包括两方模型和商品服务器模型；特别，对于商品服务器模型我，描述基于它的标量数乘问题的解法，并对其进行安全与复杂性分析。

对于可调节安全级别的安全多方计算，用户可以根据实际需求在性能和安全性之间进行调节。如果不能有信息泄露，安全性对于用户是很重要的，那么他们在我们的解法中能调整相应的参数来提高安全级别。如果用户认为泄露部分信息仍是可接受的，那么他们可以选择一个能有效达到他们的需求的参数。实用需求的新模型能通向多方安全计算问题的有前景的应用，因此，很值得继续研究。

参考文献

[1] A.C.Yao. Protocols for secure computations. In Proc. 23rd IEEE Symp.On theFoundation of Computer Science, pp. 160-164. IEEE, 1982.

[2] C.Cachin,S,Micali and putationally private information retrieval with polylogarithmic communication. Advances in Cryptotogy:EUROCRYPT ’99,Lecture Notes in Computer Science,1592:402-414,1999.

[3] B,Chor and putationally private information retrieval (extended abstract).In Proceedings of the twentyninth annual ACM symposium on theory of Computing,EI Paso,TX USA,May 4-6 1997.

[4] Chen Jie.Data disguising techniques of secure multi-party computation.Journal of GuiZhou university,2006,Vol23:15―19.

[5] Wenliang Du.and Mikhail J. Atalah. Privacy-Preserving Cooperative Scientifi Computations.In 14th IEEE Computer Security Foundations Workshop,June 11-13 2001,Nova Scotia,Canada.

[6] Maurer U. Secure multi-party computation made simple. In:Proc. of SCN ‘02,LNCS 2576,2002.