虽然同态加密为很多隐私保护的场景提供了解决方案，但由于其算法的特殊性以及实用性不佳的问题，其应用场景受到了明显的限制。
比如，加法同态加密算法无法进行明文之间的乘法运算，在使用乘法运算较多的算法进行协同训练的场景中，每个参与方均无法对其他成员的隐私数据进行乘法运算，这大大地降低了协同训练的可行性。
另外，全同态加密算法的实现也受到训练算法的极大影响，尤其对于复杂算法，全同态加密算法的效率会明显降低。
因此，同态加密算法会受到应用场景的限制，只有在计算相对简单的场景中，同态加密算法才能发挥其优势。
对于其他复杂的场景，则需要使用安全多方计算完成类似的功能。
安全多方计算的概念由姚期智院士首先提出。
安全多方计算现在已经发展为密码学的一个重要分支，不仅激起了学术界的研究热情，在工业界也受到了广泛关注。
1.百万富翁问题
安全多方计算能够在无可信第三方的辅助下，既保证各方的输入数据均不泄露，又可以使用各方的输入数据完成预期的协同计算。
也就是说，参与计算的各方对自己的数据始终拥有控制权，只需在各个参与方之间公开计算逻辑，即可得到相应的计算结果。安全多方计算是如何实现这种效果的呢？
在此，我们使用百万富翁问题来简述安全多方计算的实现方法和挑战。
图灵奖获得者姚期智院士于1982年提出了安全多方计算这个概念，并设计了百万富翁问题来说明安全多方计算的目标。
百万富翁问题的描述非常简单，即两个百万富翁想比较谁更富有，但都不想泄露自己具体的财富值。
解决该问题最自然的方法是找到一个可信第三方对二者的财富进行比较，然后公布结果，但在实际场景中很难找到完全可信的第三方，而安全多方计算便提供了无须可信第三方的解决方案。
接下来，我们描述一个简单的解决方案：
假设两个富翁A和B的财富值分别为fA，fB，均为1～9的整数。 9个整数分别对应100万，200万，…，900万元。 富翁A可按照自己的财富值在编号分别为1～9的9个盒子内放入水果，并在上锁后发送给富翁B，其中每把锁的钥匙均相同，并由富翁A自己保存。 若盒子编号i＜fA，则放入一个苹果；若盒子编号i=fA，则放入一个橙子； 若盒子编号i＞fA，则放入一个香蕉。如果fA=5，那么9个盒子中的水果
|
富翁B在收到富翁A的9个盒子之后，按照自己的财富值选取其中编号为i=fB的盒子，并按照协议销毁其他几个盒子。 待其他盒子被销毁之后，富翁A将钥匙发送给富翁B。 富翁B打开盒子之后，若盒子内为苹果，则其财富值小于富翁A； 若盒子内为橙子，则其财富值等于富翁A； 若盒子内为香蕉，则其财富值大于富翁A。 假设fB=7，则富翁B获得编号为7的盒子，待其他盒子被销毁之后，富翁A将钥匙发送给富翁B，富翁B打开盒子发现其中的水果为香蕉，便可得出结论： 富翁B的财富值大于富翁A的财富值 |
以上便是百万富翁问题的解决方法之一，这个简单的协议建立在双方都是诚实或者半诚实的参与方的前提下，双方不会恶意地输入错误的财富值扰乱协议的正确执行。
也就是说，我们可以保证富翁B不会选择错误的盒子或者将错误的比较结果返回给富翁A，但是我们却无法保证富翁B能够克制自己的好奇心，如实地销毁其他盒子。
因为即使富翁B不销毁其他盒子，也可以保证协议正常执行，完全符合一个半诚实参与方的要求。
因此，在实际应用中，双方通常使用密码协议实现这些理想的限制条件，即使面对半诚实参与方，也可以确保隐私不会泄露。
比如，密码学中的不经意传输协议，便可以保证在以上场景中富翁B只能从富翁A的发送内容中获取其中一个盒子，而不能获得其他盒子的相关信息；
同时，富翁A也无从得知富翁B所选取的具体是哪个编号的盒子。
安全多方计算的本质就是综合使用众多功能不同的密码协议，达到多方之间安全地得到约定函数的计算结果。
接下来，我们介绍一下在安全多方计算中常用的密码协议及其功能。
2.安全多方计算中的密码协议
1）不经意传输协议
在上文描述的百万富翁问题的解决方案中，在富翁B得到9个盒子之后，如何确定其会将其余盒子全部销毁是一个在现实中很难解决的问题。
不经意传输（ObliviousTransfer，OT）协议则从根本上提出了一个解决方案，避免了富翁B未按照协议销毁其他盒子而产生的安全问题。
从直观上来看，不经意传输协议的功能是保证富翁B从富翁A提供的两个或者多个备选项目中只能选择其中一个，而得不到其他备选项目的任何信息，同时还能保证富翁A不知道富翁B选择的具体是哪一个。
不经意传输协议是安全多方计算研究中的一个基础的密码协议，具体的定义如下：定义2-11 不经意传输协议指的是，Alice输入一个包含两个信息的集合{m0，m1}，Bob选择一个标签b∈{0，1}，一个不经意传输协议满足以下条件：
Bob作为协议的一方，一定可以获得mb，但无法获得m1-b； 同时，协议的另一方Alice无法得知b的具体值 |
以上介绍的是“2取1”的不经意传输协议，即协议的某一方从另一方输入的两个信息中选择一个，但现实场景往往比较复杂，比如对于上文的百万富翁问题来说，需要从9个盒子中选择一个。
因此，在密码学研究中，众多学者将目光转向“n取1”的不经意传输协议。
另外，根据不同的场景，衍生出了更多的版本，比如“n取k”的不经意传输协议，以满足不同的功能需求。
在此，我们主要介绍“n取1”的不经意传输协议的实现过程。
在介绍复杂的实现方案之前，我们先使用百万富翁问题的例子简单地介绍一下实现方案的主要思想。在百万富翁问题的解决方案中，我们希望富翁B仅从9个盒子中选择一个，并强制让富翁B销毁其余几个。
我们可以按照以下方式直观地理解利用不经意传输协议完成这个目标的主要思想：
在富翁A发送9个盒子之前，富翁B先使用所需要的箱子编号y构造一把“复杂”的组合锁，并发送给富翁A（其中编号y是构造锁的关键信息，而且富翁A无法根据锁的信息恢复出富翁B使用的编号）。
富翁A在拿到锁之后，可以以一种黑盒的方式对组合锁进行改造，改造结果为9把不同的新锁，并分别对9个盒子进行上锁，再将9个盒子发送给富翁B。
新锁的特殊性如下：
由于这些新锁均改造于编号y构造的组合锁，因此只有编号为y的盒子上的新锁可以用富翁B的钥匙打开，其余盒子均被锁死，无法打开。
因此，富翁B只能打开编号为y的盒子，而富翁A并不能根据组合锁的信息分析编号y到底是多少。
以上便是对不经意传输协议实现方案的一种不严谨的比喻，接下来我们使用严谨的数学语言来描述不经意传输协议的构造过程，读者可以将两种描述进行对比。
Tzeng构造了一个两轮的“n取1”不经意传输协议[65]，过程如下：
（1）双方协商出两个公共参数g、h，二者均为q阶循环群Gq中的元素。 （2）Alice输入n个消息m1，m2，…，mn∈Gq，同时Bob确定欲选择的消息编号t。 （3）Bob选择随机数r，并计算y=grht，将y发送给Alice。 （4）Alice选择一组随机数ki，使用y计算n组消息：（a1，b1），（a2，b2），…，（an，bn），并发送给Bob。 其中， 
|
不经意传输协议的过程看似比较复杂，但如果我们对比上文中百万富翁问题的解决方案的不经意传输协议构造，就会更容易理解。
其中，y对应的便是“组合锁”，而（ai，bi）则对应由组合锁改造的新锁保护的明文，Bob在收到所有被保护的明文之后，只能对第t个明文进行解密，因为y是由t构造的。
2）混淆电路
安全多方计算目前的主流构造方法主要有两种：
第一种是使用混淆电路 第二种则是通过秘密分享的思想 |
下面会对混淆电路、秘密分享的原理和思想分别进行介绍。
混淆电路是姚期智院士针对百万富翁问题，于1986年提出的一种解决方案，该方案的提出也验证了安全多方计算的可行性。
混淆电路的思想比较简单：
将双方需要计算的函数（所需参数为双方各自的输入信息）转化为“加密电路”的形式，该“加密电路”可以保证双方在不泄露各自输入信息的情况下，正确地计算出函数的结果。
因此，“加密电路”的设计是混淆电路方法的研究重点和难点。
但是，由于任意函数在理论上均存在一个等价的电路表示，在计算机中可以使用加法器和乘法器等电路进行实现，而这些乘法器或加法器又可以通过“与门”“异或门”等逻辑电路来表示。
也就是说，如果能够实现基本的加密版本逻辑电路，那么可以实现加密版本的计算函数。
3）秘密分享
除了使用混淆电路，秘密分享是另外一个用于构造安全多方计算的主流技术。秘密分享是现代密码学的一个重要工具，是门限密码学的基础。
门限密码学是指将基本的密码系统分布于多个参与方之间，只有所有的参与方或者足够多的参与方联合起来才能保证密码系统正常运行。
门限密码学有很多应用场景，假设某国的特工局局长将本国的特工名单保存在一个保险箱中，而局长希望将保险箱的密钥切分为4个部分，由4位副局长分别持有。
考虑到特工职业的特殊性，局长提出了两个要求：
①因为特工属于高危职业，为了防止因某位副局长意外牺牲而导致其持有的部分密钥随之消失，局长希望无须4位副局长同时提供密钥，也能打开保险箱（容错性要求）； ②为了防止因某几位副局长叛变而导致特工名单泄露，局长希望至少3位副局长同时提供密钥才能打开保险箱（安全性要求）。 |
考虑到以上两个要求，局长确定了保险箱最终的密钥管理方式：
任意3位副局长同时提供密钥，便可打开保险箱；若提供密钥的副局长少于3位，则无论如何都无法打开保险箱。
这样的系统便需要使用门限密码学来设计。
如果将密钥分为6段，每段都有两份，那么每个副局长都持有其中3段，比如a副局长持有第1段、第2段和第3段，使用这样的分割方法可以保证任意3位副局长都可以恢复完整的密钥，但如果只有1位或者2位副局长，就无法完成密钥的恢复。
以上便是门限密码学的应用。
在安全多方计算中，秘密分享的应用场景主要为使用秘密分享方案的同态特性进行约定函数的计算。
也就是说，秘密分享的内容不再是密钥，而是参与方的输入数据，通过将输入数据切分成多个随机的碎片，分发给其他参与方。
每个参与方根据自己掌握的碎片进行相关的计算，将中间结果进行聚合，从而得到最终结果。在本节中，我们会使用具体的例子简述这种思想的构造方法。
使用秘密分享进行函数计算的协议主要由两部分构成：秘密分发和秘密重构。
随着秘密分享技术的发展，目前已经出现了多种协议的实现方案，在此我们使用著名的Shamir秘密分享协议来介绍一下秘密分发和秘密重构两个部分是如何完成的。
Shamir秘密分享协议使用多项式对秘密输入进行分发，并通过拉格朗日插值方法对秘密输入进行恢复。
为了方便理解，我们仍以4位副局长对密钥保管为例，局长希望将密钥S分发给4位副局长，且只要其中3位副局长同时提供各自持有的信息就可恢复密钥。
Shamir秘密分享协议会为密钥S生成一个多项式f（x）=S+a1x+a2x2，并随机选取该多项式的点值，即（xi，yi）作为密钥的局部信息分发给各位副局长。这便完成了秘密分发。
由于该多项式共有3个未知的系数（S，a1，a2），故至少需要3个点值才能对密钥S进行恢复，且任意3个不同的点值均可。
这便完成了秘密重构。
3.安全多方计算在联邦学习中的应用
在安全多方计算发展初期，绝大多数工作致力于安全多方计算存在性的验证，因此方案的效率都不容乐观。
经过不断的发展，目前基于混淆电路的方案和基于秘密分享的方案都已经有了高效的实现。
其中，基于混淆电路的方案更适合进行逻辑运算或者数字的比较等运算，而基于秘密分享的方案则更适合进行算术运算。
因此，为了进一步提高安全多方计算的效率，目前设计了通用的安全多方计算框架，将基于混淆电路和秘密分享的方案进行融合，让它们分别负责不同类型的运算。
高效的安全多方计算作为兼顾数据隐私性和可用性的有效工具，在机器学习领域也受到了广泛关注。
使用上述计算加法和乘法的思想，将用户的隐私数据分发给两个不会合谋的服务器，两个服务器使用各自的数据碎片进行线性回归和逻辑回归的模型训练。
在具体实现中，使用基于秘密分享的安全多方计算进行矩阵和向量的乘法等算术操作，在需要进行数值的大小比较时，便使用ABY框架，将基于秘密分享的安全多方计算转化为基于混淆电路的协议对数值进行比较，在完成比较之后再通过该框架转化为基于秘密分享的协议进行后续计算。
此方案大大地提高了安全多方计算在实际应用中的效率。
联邦学习作为一种保护用户数据隐私的机器学习通用解决方案，固然离不开安全多方计算的辅助。
在横向联邦学习的安全聚合阶段，大规模的客户端在向服务器上传模型参数时，为了保护各个客户端的隐私，便可以通过安全多方计算进行安全的聚合。
Bonawitz等人提出了一种在联邦学习中进行安全聚合的方法mask-then-encrypt，并被后续多个工作进行了扩展。
该方法的主要思想是在各个客户端之间共享一些随机值，每个客户端在上传参数值之前，将真实的参数值与随机值相加或者相减，从而掩盖真实的参数值，但聚合过程又会将这些随机值抵消，从而得到正确的聚合结果。
当然，安全多方计算在联邦学习中的应用研究并未止步于此，后续仍有很多工作致力于安全多方计算的优化，比如降低方案的时间开销和解决客户端掉线或者不诚实的问题。
