安全多方计算之一：什么是安全多方计算

1. 安全多方计算简介

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

安全多方计算定义：是指在一个互不信任的多用户网络中，$n$个参与者$P_1,P_2,\dots ,P_n$，每个持有秘密数据$x_i$，希望共同计算出函数$f(x_1,x_2,\dots ,x_n)=(y_1,y_2,\dots ,y_n)$，$P_i$仅得到结果$y_i$，并且不泄露$x_i$给其他参与者。

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

设公司$n$个职员$A_1,A_2,\dots ,A_n$，他们的薪水分别为$x_1,x_2,\dots ,x_n$。该问题可形式化描述为：对$n$个秘密输入$x_1,x_2,\dots ,x_n$，在不泄露各自秘密的情况下计算函数值:$$f(x_1,x_2,\dots ,x_n)=(x_1+x_2+\dots +x_n)/n$$执行以下协议：

• (1)$A_1$选择一个随机数$r$并加上他的薪水得$r+x_1$发送给$A_2$
• (2)$A_2$加上他的薪水得$r+x_1+x_2$发送给$A_3$
• (3)$A_3,A_4,A_5,\dots ,A_{n-1}$继续执行同样操作
• (4)$A_n$加上他的薪水得$r+x_1+x_2+\dots +x_n$发送给$A_1$
• (5)$A_1$将其减去随机数$r$再除以总人数$n$便得公司职员的平均薪水$(x_1+x_2+\dots +x_n)/n$
• (6)$A_1$向$A_2,A_3,\dots ,A_n$公布平均薪水的结果

2. 基本概念

2.1 参与者

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

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

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

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

2.2 攻击者

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

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

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

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

3. 安全多方计算的模型

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

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

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

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

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

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

• 输入：每一个参与者都有一个输入，用$w$表示。
• 参与者发送输入至$T$：恶意参与者有根据当前输入$w$，决定拒绝发送消息或将某个发送给$T$。
  • $T$回应第一个参与者：如果$T$收到一对输入$(x,y)$，他计算$(x,y)$，并将第一个元素$f_1(x,y)$发回给第一个参与者。否则，$T$就向两个参与者都发送一个终止符$\perp$，终止协议。
  • $T$回应第二个参与者：如果第一个参与这是恶意的，他会根据自己的输入以及诚实第三方$T$的回应，决定是否让$T$终止协议。如果他要求T终止协议，$T$就将终止符$\perp$发送给第二个参与者来终止协议。否则$T$将发送$f_2(x,y)$至第二个参与者。
• 输出：诚实的参与者总是输出从T接收到的信息；恶意的参与者会输出任意一个多项式函数，该多项式函数跟初始输入及从T得到的信息的有关。

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

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

（1）秘密共享

秘密共享定义如下：将原始秘密$m$在参与者集合中$P_1,P_2,\dots ,P_n$分享，$P_i$持有子秘密$m_{p_i}$，只有特定参与者的集合才能够从他们的子秘密中恢复秘密$m$，而其他参与者不能得到秘密$m$的任何信息。

常见的秘密共享方案包括：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$个明文消息$m_1,m_2,\dots ,m_n$ , 及对应的密文$c_1,c_2,\dots ,c_n$ , 其加密算法$E$与解密算法$D$满足, 对于有限域上的任意可计算函数$f$ $$D(f\left(E\left(m_1\right),E\left(m_2\right),\dots ,E\left(m_n\right)\right)=f\left(m_1,m_2,\dots ,m_n\right)$$

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

（3） 比特承诺

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

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

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

（4）零知识证明

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

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

（5）混合网络

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

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

M.Jakobsson和A.Juels提出了基于Mix-Match的安全多方计算协议，该类协议包括Mix与Match两个阶段：Mix阶段通过构造混合网络，生成盲表；Match阶段通过执行PET协议进行查表，得到对应的输出。最后参与者共同解密输出。

（6）不经意传输

不经意传输（OT，Oblivious Transfer）又称健忘传输或茫然传输，由Rabin于1981年提出。不经意传输是从一个消息集合秘密获取取部分消息的方法，该协议执行完毕后，接收方知道他是否收到这个秘密，但发送方却不知道（oblivious）。

考虑这样的场景：A意欲出售许多个问题的答案，B打算购买其中一个问题的答案，但又不想让A知道他买的哪个问题的答案。即B不愿意泄露给A他究竟掌握哪个问题的秘密，此类场景可通过不经意传输协议实现。

不经意传输包括：1-out-of-2不经意传输、1-out-of-n不经意传输、m-out-of-n不经意传输。

5. 学习参考

（1）David Evans、Vladimir Kolesnikov、Mike Rosulek，《A Pragmatic Introduction to Secure Multi-Party Computation》（中文版：《实用安全多方计算导论》）

• 第1章 引言（Introduction）
• 第2章 安全多方计算定义（Defining Multi-Party Computation）
• 第3章 安全多方计算基础协议（Fundamental MPC Protocol）
• 第4章 实现技术（Implementation Techniques）
• 第5章 不经意数据结构（Oblivious Data Structures）
• 第6章 恶意安全性（Malicious Security ）
• 第7章 其他威胁模型（Alternative Threat Models）
• 第8章 总结（Conclusion）

（2）Wenliang Du，Mikhail J. Atallah，《Secure Multi-Party Computation Problems and Their Applications:A Review and Open Problems》

（3）Oded Goldreich（以色列），《Secure Multi-Party Computation》

（4）Yehuda Lindell（以色列），《Secure Multiparty Computation》

（5）冯登国， 《Concretely efficient secure multi-party computation protocols: survey and more》

（6）Facebook AI Research，《CRYPTEN: Secure Multi-Party Computation Meets Machine Learning》

（7）安全多方计算专栏、密码学专栏