并行安全多方计算协议应用研究

摘要：安全多方计算蕴含了对任何密码协议问题在原则上的实现方案，它能在原则上告诉我们哪些问题是可以解决的，哪些问题是不可能解决的。首先介绍了并行安全多方计算（SPMC）的相关工具和概念知识；接着通过模拟改进后的密码学就餐问题显示SPMC的实际应用，并在此基础上构建了SPMC的协议；最后通过“直和”方法对其安全性进行了验证分析，提出了值得进一步探讨的SPMC问题以及SPMC协议的改进研究。

关键词：并行；安全多方计算；线性密钥共享体制

中图分类号：TP309文献标识码：A文章编号：16727800（2012）009014503

0引言

随着网络技术的不断发展，网络安全中的多方计算变得越来越普遍，极大地改变了计算的含义及计算的方式。计算可能发生于相互信任的参与者之间，此时问题是很容易解决的；也有可能存在于部分信任的合作者之间，甚至存在于竞争者之间，此时问题的计算也随之复杂起来。这些参与者们特别担心的是在完成该计算的过程中，有可能出现他们各自输入的信息被他人获悉或者被泄露的情况，也就是要确保自己数据的安全性与秘密性。由此提出了安全多方计算（SMC，secure multiparty computation）协议的问题。

简单来说，SMC问题可以用数学的形式描述为：有n个参与者P-1，P-2，…，P-n，通过一种安全的方式来共同计算一个函数，这里的安全是指输入输出信息的保密性与输出结果的正确性。具体来讲，每个参与者P-i，有一个自己的秘密输入信息x-i，n个参与者要共同计算一个函数f（x-1，x-2，…，x-n）=（Y-1，Y-2，…，Y-n），使得计算结束时每个参与者P-i只能得到Y-i，除此之外得不到其它地方的任何信息。

对于并行安全多方计算（SPMC，secure parallel multiparty computation）的概念提出时间并不长，实际上，SPMC是作为SMC的一个拓展的概念。一般情况下，SMC是针对一个特定的函数进行计算的，而对于SPMC来说，是指同时安全多方计算了多个函数，并且每个函数对应的攻击者结构是不同的。

1预备知识

SPMC协议的设计，需要一些基本的工具以及概念知识。

1.1密钥共享

为了描述一般密钥共享方式，引入存取结构的概念。

定义1：存取结构AS（access structure）。设P={P-1，…，P-n}是n个参与者集合，用AS来命名P上的一个存取结构，也就是AS是由P上的一些子集组成的一个非空子集合，即AS2+p，而且满足单调性质：如果同时满足A∈AS和BP，而且AB，那么有B∈AS。

通常研究SPMC问题利用的是线性多密钥共享体制（LMSSS），那么线性密钥共享体制是一个必需的理论知识。

定义2：线性密钥共享体制（LSSS，linear secret sharing scheme）。令P={P-1，…，P-n}为参与者集合，其AS是P上一个存取结构。令集合S为主密钥空间，R为随机输入集合，集合S-i为子密钥空间，分配函数为Π：S×RS-1×…×S-n，那么对存取结构AS的密钥共享体制的实现是：将一个主密钥s∈S通过分配函数Π在参与者P-1，…，P-n之间实行共享，也即Π（s，r）=（s-1，…，s-n），其中r∈R，每个子密钥s-i为对应参与者P-i所掌握，1≤i≤n，满足下列条件：①重构要求：即分配函数是线性的，对于A∈AS，集合A中的成员可以恢复主密钥s，即H（S|Π（S，R）|-A）=0，这里H（·）为信息熵或熵函数，Π（S，R）|-A为在集合A条件下的分配函数；②安全性要求：对于BAS，从集合B中选择任何成员得不到主密钥s的任何信息，即H（S|Π（S，R）|-B）=H（S）。

在1≤i≤n条件下，如果|S|=|S-i|，该密钥共享体制就是完美的密钥共享体制。令K为某个有限域，如果主密钥空间S=K，随机输入集合R和子密钥空间S-i都是K上的有限维子线性空间，当分配函数Π是线性时，就得到了我们所定义的情况了。

1.2攻击者

在SMC协议中，我们可以将攻击者（adversary）理解为一个有破坏协议安全性或正确性的企图成员，比如说一个电脑黑客。简单地来说，被攻击者收买或者腐败的参与者中的一些子集组成的集合称之为攻击者结构Λ（adversary structure）。其一个极大攻击者结构为Λ-m={B∈Λ|ABAΛ}，而且由单调性质可知Λ和Λ-m是彼此唯一确定的。例如（t，n）门限攻击者结构Λ={APA|≤t}，其对应的极大攻击者结构为Λ-m={APA|=t}。

1.3通信复杂性

SMC协议的复杂性度量也就是通信复杂性。通信复杂性度量有两种方式，一种是轮复杂性 （round complexity），是指执行协议时通信的次数。另一种是协议执行中发送的bit总数，也就是信息传输量。这两种通信复杂性有时候要综合考虑，轮数少但发送的bit数未必少，反之亦然。

1.4安全性定义

在处理SPMC安全性的要求时，采取以往不同的思想和路径，即所要证明的现实协议与理想模型是具有相同的安全性来推出。

比如，比较图1（理想模型）和图2（现实协议）各自处理过程。图1中添加了一个完全可信的第三方T，在理想模型中的攻击者可以与现实协议进行同样的攻击，但他无法入侵T。可想而知，理想模型是我们所期望达到的最安全的模型。但是在现实情况下，这个完全可信的第三方T并不一定存在，因此想要安全地共同计算某一个函数f，就需要设计复杂的协议，一般的现实协议都是通过多轮参与者之间的信息交互来完成的，而攻击者在每轮的交互后都能从被收买者处获得一些信息。

2并行安全多方计算应用

前面我们已经知道并行安全多方计算（SPMC）是指同时安全多方计算多个函数，并且每个函数针对的攻击者结构不同。正如LSSS是设计SMC协议的一个重要工具，为此推广提出了LMSSS是设计SPMC协议的一个重要工具。本节首先通过模拟实际SPMC应用问题，然后对SPMC协议的构造与一般的“直和”方法进行比较，也就是安全性得到满足。

2.1就餐协议问题

这里把一个经典的密码学家就餐问题改成更加通俗易懂的，然后模拟通过SMC协议去解决。具体问题是：某公司的一个部门的3个同事A、B、C与公司经理M晚上加完班后，相约一同去某个星级餐馆共进晚餐。然而在就餐进行得差不多的时候，经理M因紧急事情已先行离开，此时侍者正好通知他们晚餐需匿名支付账单，这里可能存在的情况有：一种情况是其中一个同事正在付账；另一种情况是经理M离开的时候正好在前台已经付了账，但没及时通知他们。这里要求他们彼此尊重匿名付账的权力，而且也要知道M是不是在付账。首先设定要求：3个同事A、B、C共同围坐在餐桌边，每个同事将菜单放置于左边而互相隔离开来； 每个同事在他和右边同事之间抛掷一枚硬币，每个同事广播他能看到的两枚硬币是否同一面；如果有一个同事付账，则他说相反的结果，具体运行处理过程如图3所示。

但此时如果某个同事在付账，而另外两位同事不能精确定位到具体是哪位同事。为此我们假设同事A没在付账，他要试图弄清其他哪个同事在付账，那么用数学抽象的表达形式为：

同事A需要知道同事B和C投掷硬币的结果，令Colle（i），Coin（i）分别表示同事和掷币结果，0≤i≤2，那么有

Colle（i）付款输出 = Coin（i1） Coin（i）（1）

Colle（i）没付款输出 = Coin（i1） Coin（i） 1（2）

此类的就餐问题，可以做个延伸，改成任意数量的同事和公司多个领导（比如总经理或者普通部门经理）“就餐问题”协议，处理过程类同。但是利用上面类同的解决方法可能考虑的并不周全，因为还有可能涉及具体的其它可能性，比如说公司领导的重要性程度不一样，公司领导与这些同事的关系融洽度，这都有可能影响公司领导是否会在就餐的时候付账。而且重点要求的是恶意的或者有欺骗性的参与者不能读出报文，但他可能会在第4步撒谎来破坏系统。那么就涉及到下面的SPMC的问题构建了。

2.2SPMC协议构建

首先设一个就餐同事参与者集合为P={P-1，P-2，P-3}，这里令有限域为K，而且满足|K|>3，假设K=

瘙 綄 -5。假设有两种付账情况，也就是对应的有两种不同的存取结构。定义集合P上的两个存取结构AS-1={APA|≥2and{P-1，P-2}∩A≠}，AS-2={APA|≥2and{P-3}∩A≠}，那么根据前面极小存取结构的定义，我们得到各自对应的极小存取结构为：

（AS-1）-m={{P-1，P-2}，{P-1，P-3}，{P-2，P-3}}，（AS-2）-m={{P-1，P-3}，{P-2，P-3}}（3）

显然，相对应的攻击者结构Λ-1=2+PAS-1和Λ-2=2+PAS-2都是满足Q+2条件的。假设这些参与者们针对前面的攻击者结构（Λ-1，Λ-2）来安全地计算函数f-1=x+2-2x-3，f-2=x-1x-2+x-3，其中P-i，1≤i≤3持有秘密输入（x（1）-i，x+（2）-i）。这里令M（K，M，Ψ）是一个相对于e-1，e-2计算fAS1，fAS2的具有乘性的单调张成方案，其中M是一个d×1上的阶矩阵。

（1）输入共享阶段。对于1≤i≤3，每个参与者将自己的秘密输入利用M（K，M，Ψ）在所有参与者中间共享，即参与者P-i秘密地从随机输入集合R=K+1-2中随机选取ρi，计算（x+（1）-i，x+（2）-i，ρ-i）M+τ，并将子密钥（x+（1）-i，x+（2）-i，ρ-i）（M-P-j）+τ传送给Pj，1≤j≤5。

（2）计算阶段。由于p=2，q=1，因此计算阶段有3小步：①输入（x+（1）-1，x+（2）-1），（x+（1）-2，x+（2）-2），（x+（1）-3，x+（2）-3），同时计算z-11=x-2x-3，z-12=x-1x-2，得输出z+（1）-1=x+（1）-2x+（1）-3， z+（2）-1=x+（2）-1x+（2）-2；②输入（x+（1）-2，x+（2）-2）和（z+（1）-1，z+（2）-1），计算z-21=x-2z-1，z-22=z-1，得输出z+（1）-2=x+（1）-2z+（1）-1，z+（2）-2=z+（2）-1；③输入（x+（1）-3，x+（2）-3）和（z+（1）-2，z+（2）-2），再计算z-31=z-2，z-32=z-2+x-3，输出z+（1）-3=z+（1）-2，z+（2）-3=z+（2）-2+x+（2）-3。所以输入输出（x+（1）-i，x+（2）-i），（z+（1）-i，z+（2）-i）要求都通过M（K，M，Ψ）在成员中被秘密共享，1≤i≤3。

（3）重构输出阶段。如果所有参与者都能获得最终函数值，那么每个参与者P-i，1≤i≤3都可以将自己关于（x+（1）-2x+（1）-2x+（1）-3，x+（2）-1x+（2）-2+x+（2）-3）的子密钥共享给其他每个参与者；如果x+（1）-2x+（1）-2x+（1）-3要求只被P-1掌握，x+（2）-1x+（2）-2+x+（2）-3要求只被P-2掌握，那么P-1就会知道x+（2）-1x+（2）-2+x+（2）-3，P-2就会知道x+（1）-2x+（1）-2x+（1）-3，需要通过各自设计一个简单的SMC协议来分别计算x+（1）-2x+（1）-2x+（1）-3和x+（2）-1x+（2）-2+x+（2）-3的重构函数。

2.3安全性分析——与“直和”方法的比较

从安全性角度来说，前面构建的协议中所有输入和输出的每一步都是在多秘密共享中进行的。我们知道一种利用“直和”的方法来解决针对（Λ-1，…，Λ-m）结构，能够安全地并行计算函数f-1，…，f-m，即在理想模型条件下的。那么，可以通过把上面SPMC的实现与“直和”方法比较，得到是否满足安全性的要求。

对于任意的B∈Λ-i-1∩…Λ-i-k，则有如下{S+i-1，…，S+i-k}{S+1，…，S+m}{S+i|B∈AS-i，1≤i≤m}。按照LMSSS的安全性需求，参与者在集合B中关于{S+i-1，…，S+i-k}获得不到任何的信息，也就是说，某个参与者中间传输的信息在函数f-i1，…，f-ik输入时不会泄露给其他参与者。因此一个攻击者收买的成员AB，除了在B中成员已经给出的输入输出信息之外，不会获得B之外的其他参与者在函数f-i1，…，f-ik上的任何输入信息。因此，上面所采用的并行安全多方计算协议和“直和”方法具有相同的安全性。

具体各个阶段SPMC协议与“直和”方法的信息交互的复杂度比较如表1所示。

表1协议信息交互复杂度比较

[]参与条件[]SPMC复杂度（bit）[]“直和”复杂度（bit）

输入共享阶段[]变量x1，…，x-5[]361og|K|[]361og|K|

计算阶段[]f-1含p个乘法，f-2含q个乘法[]p≤q，36qlog|K|P=q，nlog|K|[]p≤q，20（p+q）log|K|P=q，nlog|K|+4plog|K|[]

重构输出阶段[]x+（1）-1+x+（1）-2x+（1）-3只被P-1掌握，x+（2）-1，x+（2）-2只被P-2掌握[]nlog|K|[]nlog|K|-20log|K|[]

3结语

目前对于SPMC问题的研究还在起步阶段，还有许多问题等待去开发和研究。本文模拟了实际生活中SPMC的应用问题，同时利用LMSSS来构造协议，并通过与“直和”方法的比较对其安全性进行了分析。然而本文提出的SMC问题的解决方法都是基于比较理想的模型，所以对一些恶意模型或者大部分参与者存在欺骗的情况下的协议，以及SPMC协议的改进等都亟需进一步的研究。

参考文献：

[1]A YAO.Protocols for secure computation[A].Proceedings of IEEE FOGS’82[C].1982.

[2]GOLDREICH S.MICALI A.WIGDERSON.How to play any mental game[A].Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing[C].1987（1）.

[3]刘木兰.密钥共享体制与安全多方计算[J].北京电子科技学院学报，2006（8）.

[4]LIANGLIANG XIAO，MULAN LIU.Linear secret sharing schemes and rearrangement of access structures[J].Acta Mathematae Applicatae Sinica，2004（4）.

[5]张志芳.乘性单调张成方案[J].中国科学院研究生院学报，2006（6）.

[6]R CANETTI.Security and composition of multiparty cryptographic protocols[J]. Journal of Cryptology，2003（1）.