第四节 安全多方计算技术

一 安全多方计算的定义

安全多方计算技术（Security Multi-Party Computation, SMC）起源于1982年世界著名计算机学家姚期智（Andrew Chi-Chih Yao）的百万富翁问题：

“两个百万富翁想比较一下谁更富有，但是他们不想让对方、更不想让第三方知道自己确切的钱数。”

由此可以得出安全多方计算技术是解决两方或多方参与且互不信任的前提下保护隐私的协同计算问题，安全多方计算技术要确保参与方信息的独立性和计算的正确性，同时又可以保护各参与方的信息不泄露给其他参与方或第三方。[60]

安全多方计算技术要解决的问题可以描述如下：一组参与方希望共同计算某个约定的函数，每个参与方提供函数的一个输入，要求参与方提供的输入对其他参与方保密（出于安全考虑）。[61]如果存在安全可信第三方，则安全多方技术所要解决的问题可以轻易地得到解决：只需各个参与方将各自的输入交给安全可信第三方，由安全可信第三方计算后得到函数值，再将函数值发布给各参与方。但现实中很难找到这样的安全可信第三方，从而安全多方计算技术的研究应运而生。安全多方计算在电子投票、电子选举、电子拍卖、秘密共享、门限签名等场景中有着重要的作用。

根据参与方在安全多方计算中的行为，将参与方划分为以下三种类型：

（一）恶意参与方

在安全多方计算执行过程中，恶意参与方参与计算的目的就是获取其他参与方的输入、输出及中间结果。恶意参与方可能将自己的输入、输出或中间结果泄露给攻击方，同时可能不按照计算的要求完成计算的每个步骤，甚至篡改数据或执行步骤。

（二）半诚信参与方

在安全多方计算执行过程中，半诚信参与方完全按照计算的要求完成计算的每个步骤，严格保密自己的输入、输出及中间结果。半诚信参与方可能通过收集其他参与方的中间结果试图推导其原始输入数据、输出数据，也有可能将自己的输入、输出或中间结果泄露给攻击方。

（三）诚信参与方

在安全多方计算执行过程中，诚信参与方完全按照计算的要求完成计算的每个步骤，不篡改数据也不会修改计算步骤，同时严格保密自己的输入、输出及中间结果。但诚信参与方可能通过收集其他参与方的中间结果试图推导其原始输入数据、输出数据。诚信参与方与半诚信参与方的根本区别在于诚信参与方不会被攻击方腐败。[62]

根据攻击方在安全多方计算中腐败的参与方的不同，安全多方计算中将攻击方划分为以下三种类型：

（一）主动攻击方

主动攻击方是安全多方计算中的恶意参与方。主动攻击方可以腐败安全多方计算中的其他参与方后获取被腐败方的输入、输出及中间结果，甚至可以让腐败方篡改输入、输出及中间结果，篡改计算步骤，直至计算终止。

（二）被动攻击方

被动攻击方是安全多方计算中的半诚信参与方。被动攻击方可以腐败安全多方计算中的其他参与方后获取被腐败方的输入、输出及中间结果。被动攻击方不能篡改输入、输出及中间结果，不能篡改计算步骤，不能阻止计算。这也是被动攻击方与主动攻击方的区别。

（三）易变攻击方

易变攻击方是混乱的，在安全多方计算的不同周期，可能是不同的攻击方，有时候是被动攻击方，有时候是主动攻击方。

根据参与方的不同，安全多方计算模型有以下两种：

（一）半诚信模型

所有参与方均为半诚信参与方或诚信参与方，则此模型为半诚信模型。

定义2.2：设n元函数f:（{0,1}∗）n→（{0,1}∗）n，其中fi（x1, x2, …, xn）表示f（x1, x2, …, xn）中的第i个元素。令f1（x1, x2, …, xn）表示子序列fi1（x1, x2, …, xn）, …, fit（x1, x2, …, xn），其中I = {i1, i2, …, in}⊂[m]def= {1,2, …, n}。设∏是表示计算f的n方协议，在用输入=（x1, x2, …, xn）执行协议过程中，第i 个参与方 Pi的观察表示为 VIEWi∏（）。令，其中I = {i1, i2, …, it}。

（二）恶意模型

有恶意参与方的模型即为恶意模型。

安全多方计算模型以保护诚信参与方，不保护半诚信参与方，取缔恶意参与方为目的。

安全多方计算具有如下三个特性：

（一）安全性

任何参与方只能得到安全多方计算后的中间结果或输出，不能得到其他参与方的输入数据、中间结果。

（二）公平性

若恶意参与方不能在其他诚信参与方或半诚信参与方获得中间结果或输出之前获得其他诚信参与方或半诚信参与方的中间结果或输出，则称为完全公平。若恶意参与方攻击其他半诚信参与方后，在其他半诚信参与方之前获得中间结果或输出，则称为部分公平。

（三）正确性

安全多方计算模型的参与方输入数据后经过计算等得到正确的中间结果和输出。

1982年，世界著名计算机学家姚期智提出了基于两方的安全计算协议。1987年，在密码学理论的支持下，O. Goldreich, A. Wigderson和S. Micali等人提出了基于多方的安全计算协议，其中协议是可以计算的任意函数。当存在被动攻击方时，给出并证明了存在n-Secure协议；当存在主动攻击方时，给出并证明了存在（n-1）-Secure协议。1998年，在信息学理论的支持下，D. Chaum, I. Damgard和C. Crepeau等人研究了基于安全模型的安全多方计算，并证明了当存在被动攻击方时，存在（n-1）-Secure协议；当存在主动攻击方时，存在（-1）-secure协议。1990年，S. Goldwasser和L. Levin等人提出了当大部分参与方（超过参与方的50%）都被腐败时的安全多方计算协议。随后O. Goldreich, N. Linial和S. Goldwasser等人对于不安全的通讯信道、拥有无限计算能力的攻击者模型下的安全多方计算协议进行了研究。R. Ostrovsky和M. Yung在安全信道模型下对移动攻击者（Mobile Adversaries）进行了研究。

二 安全和模型（Secure Sum）

文献 [15] 提出垂直分布数据中基于SMC技术的k-Means方法，文献 [16] 提出在垂直分布和水平分布数据中基于SMC技术的k-Means方法。在水平分布数据中利用SMC求平均值协议可以在不泄露隐私的情况下完成聚类挖掘，在垂直数据中使用SMC中的Secure SUM技术和Secure-Means技术在不泄露隐私的情况下完成聚类挖掘。安全和模型主要应用于分布式数据挖掘系统，算法如下：

输入：s个参与方，分别属于s个站点，每个参与方输入数据Vi（s≥3）

输出：

算法：

设的范围是[0,n]；

设S1是主站点，产生随机数R，且R∈ [0, n]；

主站点S1计算R+V1mod n后发送给站点S2；

……

从站点 Sl接收 V = R +Vjmod n，计算 R +Vjmod n =（Vj+V）mod n后发送给站点；

……

站点Ss重复步骤4后，发送给Sl；

Sl-R后得到结果输出。

三 安全积模型（Secure Multiplication）

通过计算各站点子项集的向量标量积确定频繁项集，引入随机向量，使用代数方法计算确定频繁项集。如果x1, x2, …, xm属于X站点，y1, y2, …, yn属于Y站点，则要构造向量和…，通过计算和的向量积以确定 {x1, x2, …, xm, y1, y2, …, yn} 是否是频繁的，实现基于关联规则的安全积模型。

在垂直分布式数据中，基于SMC方法，文献 [63] 提出了在半信任第三方服务器上，采用标量积协议的保持隐私的ID3算法。文献 [64]提出使用同态加密的方法计算属性的信息增益，通过比较信息增益生成决策树。文献 [65] 基于标量积和xln（x）协议的隐私保持C4.5算法，实现基于分类的安全积模型。

输入：站点A有=（x1, x2, …, xn），站点B有=（y1, y2,…, yn）

输出：站点A、B均获得

算法：

（1）A、B站点共同产生随机矩阵C

（2）站点A

1．产生维向量R

2. X′ = C×R, X″=X+X′

3. X″发送到站点B

（3）站点B

1. S′ =xi″×yi

2. Y′=×Y

3. S′和Y′发送到站点A

（4）站点A

1. S″ =Y′×Ri

2. S=S′-S″

3. S发送到站点B

四 安全交集模型（Secure Intersection）

文献 [18] 提出在水平分布式数据实现隐私保护数据挖掘要分别计算各站点的置信度（Confidence）和支持度（Support）。首先使用可交换加密算法，计算全局候选集；其次计算候选集全局支持度；最后基于SMC中的Secure SUM技术和Secure-Union技术实现累加后判断其是否属于频繁项集。这种与加密技术结合的方法，实现了信息共享的最小化，在挖掘的同时增加的开销任务较小，实现基于关联规则的安全交集模型。

输入：s个参与方，各参与方数据Vi（i∈ [1, s]），各参与方生成公钥（Ei, Di）

输出：V1∩V2∩…∩Vs

算法：

M=Vi
for s-1 steps do
  M′ = newarray[ M ], j=0
  for each X ∈M do
    M′[j ++]= encrypt（X, Ei）
  end for
  随机变换M′顺序，发送到Simod k
end for
M′ = newarray[ M ], j=0
for each X ∈ M do
  M′[j ++]= encrypt（X, Ei）
end for
随机变换M′顺序，发送到Si mod 2
输出M

五 安全并集模型（Secure Union）

文献[60—66]给出了基于Pohlig -Hellman加密的安全并集模型算法，Pohlig-Hellman加密理论主要有以下两个定理支持：

定理2-1 EKi1（…EKin（M）…）= EKj1（…EKjn（M）…）

定理2-2 ∀M1∈M, ∀M2∈M，且M1≠M2，对给定的k, ε＜，则有Pr（EKi1（…EKin（M1）…）= EKj1（…EKjn（M2）…））＜ ε

输入：s个参与方，各参与方数据Vi（i∈ [1, s]），各参与方生成符合定理2.1的密钥（Ei, Di）

输出：V = V1∪V2∪…∪Vs

算法：

令V=Ф

各站点加密各自数据Ei（Di）

for i=1 to s

V = V∪Ei（Di）

end for

消除V中的重复项

各站点解密Di（V）

输出V