安全多方计算之一：什么是安全多方计算-阿里云开发者社区

1. 安全多方计算简介

安全多方计算问题（SMC，Secure Multi-party Computation）由由中国计算机科学家、2000年图灵奖获得者姚启智教授于1982年在论文《Protocols for secure computations》中以百万富翁问题（两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方及其他第三方知道自己财富的任何信息）提出，开创了密码学研究的新领域。

安全多方计算定义：是指在一个互不信任的多用户网络中，n nn个参与者P 1 , P 2 , . . . , P n P_1,P_2,...,P_nP1,P2,...,Pn，每个持有秘密数据x i x_ixi，希望共同计算出函数f ( x 1 , x 2 , . . . , x n ) = ( y 1 , y 2 , . . . , y n ) f(x_1,x_2,...,x_n)=(y_1,y_2,...,y_n)f(x1,x2,...,xn)=(y1,y2,...,yn)，P i P_iPi仅得到结果y i y_iyi，并且不泄露x i x_ixi给其他参与者。

平均薪水问题是一个简单的安全多方计算问题，即某公司n nn位职员想了解他们每月的平均薪水有多少，但又不想让任何其他人知道自己的薪水。

设公司n nn个职员A 1 , A 2 , … , A n A_1,A_2,…,A_nA1,A2,…,An，他们的薪水分别为x 1 , x 2 , … , x n x_1,x_2,…,x_nx1,x2,…,xn。该问题可形式化描述为：对n nn个秘密输入x 1 , x 2 , … , x n x_1,x_2,…,x_nx1,x2,…,xn，在不泄露各自秘密的情况下计算函数值:f ( x 1 , x 2 , … , x n ) = ( x 1 + x 2 + … + x n ) / n f(x_1,x_2,…,x_n)=(x_1+x_2+…+x_n)/nf(x1,x2,…,xn)=(x1+x2+…+xn)/n执行以下协议：

(1)A 1 A_1A1选择一个随机数r rr并加上他的薪水得r + x 1 r+x_1r+x1发送给A 2 A_2A2
(2)A 2 A_2A2加上他的薪水得r + x 1 + x 2 r+x_1+x_2r+x1+x2发送给A 3 A_3A3
(3)A 3 , A 4 , A 5 , … , A n − 1 A_3,A_4,A_5,…,A_{n-1}A3,A4,A5,…,An−1继续执行同样操作
(4)A n A_nAn加上他的薪水得r + x 1 + x 2 + … + x n r+x_1+x_2+…+x_nr+x1+x2+…+xn发送给A 1 A_1A1
(5)A 1 A_1A1将其减去随机数r rr再除以总人数n nn便得公司职员的平均薪水( x 1 + x 2 + … + x n ) / n (x_1+x_2+…+x_n)/n(x1+x2+…+xn)/n
(6)A 1 A_1A1向A 2 , A 3 , … , A n A_2,A_3,…,A_nA2,A3,…,An公布平均薪水的结果

2. 基本概念

2.1 参与者

参与者指参与协议的各方，每个参与者被抽象为具有概率多项式时间算法的图灵机根据参与者在协议中的行为将其分为以下三类：

（1）诚实参与者：诚实参与者完全按照要求完成执行过程中的各个步骤，同时保密自己的所有输入、输出及中间结果。诚实参与者也会根据自己的输入、输出以及中间结果来推导其他参与者的信息，但是不会被攻击者腐败。

（2）半诚实参与者：半诚实参与者在协议的执行过程中，完全按照协议的要求完成协议的各个步骤，但同时可能将自己的输入、输出及中间结果泄露给攻击者。

（3）恶意参与者：恶意参与者在协议的执行过程中，完全按照攻击者的意志执行协议的各个步骤，他不但将自己的所有输入、输出及中间结果泄露给攻击者，还可以根据攻击者的意图改变输入信息、伪造中间及输出信息，甚至中止协议。

2.2 攻击者

安全多方计算协议中，攻击者会破坏协议安全性或正确性，通过腐败参与者的一个子集，来控制其对协议进行攻击。根据攻击者对恶意参与者的控制程度、攻击者的计算能力、网络同步与异步状态、自适应性等准则，可以对攻击者有不同的分类。其中按照对恶意参与者的控制程度，将攻击者分为以下下三类：

（1）被动攻击者：又称为半诚实攻击者。被动攻击者只是监听恶意参与者的输入、输出及中间计算结果，并不控制恶意参与者的行为（比如修改恶意参与者的输入输出）。

（2）主动攻击者：除了监听任意参与者的输入、输出及中间结果外，主动攻击者还控制恶意参与者的行为（如恶意篡改参与者的输入，按照自己的意图控制恶意参与者的输出等）。

（3）隐蔽攻击者：Aumann和Lindell于2007年提出介于被动攻击者与主动攻击者之间的攻击者类型，即隐蔽攻击者（Convert adversary）。隐蔽攻击者以被发现的概率为（称为遏制因子）危险去攻击协议，被隐蔽攻击者腐败的参与者可以进行主动的腐败行为。

3. 安全多方计算的模型

安全多方计算的模型主要有三种：半诚实模型、恶意模型与隐蔽攻击模型。

（1）半诚实模型：如果所有参与者都是半诚实或诚实的，称此模型为半诚实模型。半诚实成员完全遵守协议，但它会收集协议执行过程中的所有记录，并试图推断其他成员的输入，半诚实模型中的攻击者都是被动的。

半诚实模型下的理想模型定义：在理想模型中，存在一个诚实第三方T TT，该第三方能够与所有参与者进行保密通信，且对对参与者发送给的所有信息保密。攻击者不能得到诚实参与者与T之间交换的任何信息。

输入：参与者A AA拥有x xx，参与者B BB拥有y yy。
参与者发送输入至T TT：参与者按要求将输入发送至T TT。
T TT回应参与者：T TT收到输入( x , y ) (x,y)(x,y)后，计算( x , y ) (x,y)(x,y)。T TT发送f 1 ( x , y ) f_1(x,y)f1(x,y)至参与者A AA，发送f 2 ( x , y ) f_2(x,y)f2(x,y)至参与者B BB。
输出：诚实的参与者总是输出从T TT接收到的信息；恶意的参与者会输出任意一个多项式函数，该多项式函数跟初始输入及从T TT得到的信息的有关。

（2）恶意模型：有恶意参与者的模型称为恶意模型。恶意参与者完全按照攻击者的意愿执行协议的各个步骤，他不但将自己的所有输入、输出以及中间结构泄露给攻击者，还可以根据攻击者的意图改变改变输入信息、伪造中间及输出信息，甚至终止协议。恶意模型中的攻击者是主动的。

恶意模型下的理想模型定义：在理想模型中，存在一个诚实第三方T TT。

输入：每一个参与者都有一个输入，用w ww表示。
参与者发送输入至T TT：恶意参与者有根据当前输入w ww，决定拒绝发送消息或将某个发送给T TT。

T TT回应第一个参与者：如果T TT收到一对输入( x , y ) (x,y)(x,y)，他计算( x , y ) (x,y)(x,y)，并将第一个元素f 1 ( x , y ) f_1(x,y)f1(x,y)发回给第一个参与者。否则，T TT就向两个参与者都发送一个终止符⊥ \bot⊥，终止协议。
T TT回应第二个参与者：如果第一个参与这是恶意的，他会根据自己的输入以及诚实第三方T TT的回应，决定是否让T TT终止协议。如果他要求T终止协议，T TT就将终止符⊥ \bot⊥发送给第二个参与者来终止协议。否则T TT将发送f 2 ( x , y ) f_2(x,y)f2(x,y)至第二个参与者。

输出：诚实的参与者总是输出从T接收到的信息；恶意的参与者会输出任意一个多项式函数，该多项式函数跟初始输入及从T得到的信息的有关。

（3）隐蔽攻击模型：有被隐蔽攻击者参与的模型称为隐蔽攻击者模型，被腐败的参与者可以进行主动的腐败行为，但仅在能小于一定概率不被发现的情况下才可实施腐败行为。

4. 安全多方计算的密码学工具

（1）秘密共享

秘密共享定义如下：将原始秘密m mm在参与者集合中P 1 , P 2 , . . . , P n P_1,P_2,...,P_nP1,P2,...,Pn分享，P i P_iPi持有子秘密m p i m_{p_i}mpi，只有特定参与者的集合才能够从他们的子秘密中恢复秘密m mm，而其他参与者不能得到秘密m mm的任何信息。

常见的秘密共享方案包括：Shamir秘密共享方案、Asmuth-Bloom方案、Feldman的VSS方案、Pedersen的VSS方案以及无分发者Joint-Shamir-RSS方案（Joint Shamir Random Secret Sharing）。

（2）同态加密

R.Rivest等人1978年首次在《On data banks and privacy homomorphisms》中以隐私同态（Privacy homomorphism）的概念提出。同态性使得可以在加密数据上进行运算，从而保护用户数据隐私。Gentry, C. 于2009年在《Fully homomorphic encryption using ideal lattics》给出了全同态的定义，并基于理想格构造了一系列全同方案。

全同态加密方案是指, 对于n nn个明文消息m 1 , m 2 , … , m n m_{1}, m_{2}, \ldots, m_{n}m1,m2,…,mn , 及对应的密文c 1 , c 2 , … , c n c_{1}, c_{2}, \ldots, c_{n}c1,c2,…,cn , 其加密算法E EE与解密算法D DD满足, 对于有限域上的任意可计算函数f ffD ( f ( E ( m 1 ) , E ( m 2 ) , … , E ( m n ) ) = f ( m 1 , m 2 , … , m n ) D\left(f\left(E\left(m_{1}\right), E\left(m_{2}\right), \ldots, E\left(m_{n}\right)\right)=f\left(m_{1}, m_{2}, \ldots, m_{n}\right)\right.D(f(E(m1),E(m2),…,E(mn))=f(m1,m2,…,mn)

全同态加密体制使得可以在加密数据上进行任意计算与分析，可应用于加密云存储服务，隐私信息检索，隐私数据挖据等许多重要领域。比如许多企业需要委托第三方（云计算数据中心）对数据进行处理分析，但是数据中含有商业机密等敏感信息，可以首先使用全同态加密算法对数据加密后再发送给第三方，这样云端服务器不用解密就可以直接处理数据，完成后返给用户，用户对数据解密得到处理结果。

（3）比特承诺

比特承诺方案（Bit Commitment Scheme）解决这样的问题：Alice向Bob承诺一个预测（比特值），直到一段时间之后才揭示着预测（比特值）；在这期间，Alice不能改变自己的预测（比特值）。

比特承诺的一个直观例子：Alice 把消息M MM(承诺)放在一个箱子里(只有Alice有钥匙)并将它锁住送给Bob，等到 Alice 决定向 Bob证实消息M MM时，Alice把消息M MM及钥匙给 Bob，Bob 能够打开箱子并验证箱子里的消息同 Alice出示的消息是否相同，且Bob 确信箱子里的消息在他保管期间没有被篡改。

常见的比特承诺方案有基于对称密码算法的，基于单向函数的以及基于数学难解问题的（大数分解、离散对数等）。

（4）零知识证明

零知识证明（Zero Knowledge Proof） 由S.Goldwasser、S.Micali 及 C.Rackoff于1985年在论文《The Knowledge Complexity of Interactive Proof Systems》（交互式证明系统中的知识复杂性）首次提出，是一种用于证明者在不泄露任何其他信息的情况下证明其掌握知识正确性的密码学协议。

该协议的一方称为证明者（Prover），用P PP表示；协议的另一方称为验证者（Verifier），用V VV表示。零知识证明指P PP试图使V VV相信某个论断是正确的，但却不向V泄露任何有用的信息，即P PP在论证的过程中V VV得不到任何有用的信息。

（5）混合网络

1981年，Chaum首次在《Untraceable electronic mail, return addresses, and digital pseudonyms》提出混合网络（MN，Mix-Network），用于保护参与者的隐私。

混合网络是一个多方协议，协议的输入是一个密文表，该密文表中的密文与明文有一一对应的关系。混合网将这个密文表随机置换后输出另外一个密文表，称之为盲表（Blinded table）。同输入的密文表一样，输出的盲表中的密文和相同的一组明文也是一一对应的，即输出的密文表是输入密文表的随机置换。混合网络的安全性在于攻击者无法确定输出盲表中的某一条密文与输入密文表中的哪一条密文是对应的。