➢ 多方安全计算的底层技术
以姚期智在1982年给出的百万富翁问题和解决方案为引子，此后的学者不断受到启发，扩展出了更多的基于密码学算法的应用协议和框架，满足让多方安全地完成任意计算任务。
自1986年姚期智提出第一个通用的多方安全计算框架（常被称为Yao’s Garbled Circuit，姚氏混淆电路）以来，30多年间已经有BMR、GMW、BGW、SPDZ等多种多方安全计算协议陆续被提出。至今，每年仍有大量的研究工作在改进和优化这些多方安全计算框架。
这些通用的多方安全计算框架都是从两方、三方的简单场景中衍生而来的，基于的是几个最关键的底层密码学协议或框架，主要包含不经意传输（Oblivious Transfer，简称OT）、混淆电路（Garbled Circuit，简称GC）、秘密分享（Secret Sharing，简称SS）等。主流的两方安全计算主要采用不经意传输和混淆电路这两种密码学技术，而更通用的多方安全计算涉及不经意传输、混淆电路、秘密分享等多种密码学技术。接下来我们对这三个底层技术进行介绍。
● 不经意传输（OT）
不经意传输也称茫然传输，是一种基本的密码学原语，可以在数据传输与交互过程中保护隐私。在OT协议中，数据发送方同时发送多个消息，而接收方仅获取其中之一。发送方无法判断接收方获取了具体哪个消息，接收方也对其他消息的内容一无所知。
最早的OT协议是在1981由Michael O.Rabin提出的，在Rabin的OT协议中，发送者Alice发送一条消息给接收者Bob，而Bob以1/2的概率接收到信息。在协议交互结束后，Alice并不知道Bob是否接收到了信息，而Bob能确信地知道自己是否收到了信息。显而易见，这种模式并不具备落地的实用价值。
1985年，Shimon Even, Oded Goldreich和Abraham Lempel提出了更为实用的2选1OT协议。如图2-1所示，在这种形式的不经意传输模型中，Alice每次发两条信息（m0、m1）给Bob, Bob提供一个输入，并根据输入获得输出信息。在协议结束后，Bob得到了自己想要的那条信息（m0或者m1），而Alice并不知道Bob最终得到的是哪条。值得注意的是，1988年，Claude Crépeau证明了Rabin的OT协议和2选1OT协议是等价的。
图2-1 2选1OT协议
1986年，Brassard等人又将2选1OT协议扩展为了N选1OT协议，其实现逻辑如图2-2所示。
图2-2 N选1OT协议
在多方安全计算应用中，比如PSI、混淆电路等，一般需要执行大量的OT协议来完成复杂的计算，效率问题使得OT协议的实用价值并不高。1996年Beaver依据混合加密构想提出了第一个OT扩展协议，但这一协议需要计算复杂的伪随机发生器，在实际中也不高效。基于扩展的思想，Ishai等人在2003年提出将基础的OT协议与随机语言模型结合，通过少量基础OT的计算代价和大量对称加密操作来提高大量OT操作的效率，可以达到一分钟执行数百万次的OT协议，该协议可以同时满足实用性和安全性需求，具有重要的意义，也得到了很广泛的应用。
● 混淆电路（GC）
混淆电路是一种将计算任务转化为布尔电路并对真值表进行加密打乱等混淆操作以保护原始输入数据隐私的思路。利用计算机编程将目标函数转化为布尔电路后，对每一个门输出的真值进行加密，参与方之间在互相不掌握对方私有数据的情况下共同完成计算。最早的混淆电路是姚期智院士针对百万富翁问题提出的解决方案，因此又称为“姚氏混淆电路”。
GC协议的基础是“电路”。根据计算理论，所有可计算的问题都可以转换为各个不同的电路，例如加法电路、比较电路、乘法电路等。因此，函数计算可以被规约为对电路的计算。
电路是由一个个门（gate）组成的，例如与门、非门、或门、与非门等。完成一个函数的计算，首先需要构建一个由与门、或门、非门、与非门组成的布尔逻辑电路，每个门都包括输入线和输出线，布尔逻辑电路如图2-3所示。
图2-3 布尔逻辑电路
GC协议的关键是“混淆”，也就是对电路内部所有的输入和输出都通过加密+打乱的方式进行混淆，用加密的值的计算来代替明文的传输以达到计算双方无法获得对方的输入值。混淆要覆盖电路的所有环节，因此，以门为单位，每个门有一张对应的真值表，如图2-4所示。
图2-4 真值表示例
为了计算门电路，Alice将输入对应的密钥Ra,0或Ra,1发送给Bob；Bob和Alice执行OT协议，Alice获得Bob输入对应的密钥Rb,0或Rb,1；Bob根据获得的两个密钥对加密真值表的每一行尝试解密，最终只有一行能解密成功，并提取相关的加密信息Rc,0或Rc,1；最后，Bob将计算结果返回Alice, Alice确定最终的计算结果。在以上过程中，Alice和Bob的交互仍然都是密文或随机数。
由于混淆电路需要对每一位进行电路门计算并且电路门数量巨大，导致计算效率较低。例如，计算AES加密算法大约需要30000个电路门，计算50个字符串大约需要250000个电路门。因此，研究者提出了一系列的电路优化策略，还提出了新的混淆电路协议，包括由Goldreich等人提出基于秘密分享和OT协议的GMW编译器，以及基于“Cut and Choose”[1]的适用于恶意模型的混淆电路等。
● 秘密分享（SS）
秘密分享也称秘密分割或秘密共享，它给出了一种分而治之的秘密信息管理方案，原理是将秘密拆分成多个分片（share），每个分片交由不同的参与方管理。它源于经典密码理论，最早由Sharmir和Blakley在1979年分别基于拉格朗日插值多项式和线性几何投影理论独立提出。秘密分享一般用于两方或多方计算中的算术计算场景。
秘密分享为存储高敏感、高机密数据提供了良好的解决方案。对于敏感信息的存储应具备高机密性和高可靠性。如果采用单点存储，则机密性提高的同时又难以抵抗内部泄露带来的风险，如果采用多备份存储，则机密性又无法保障。
如图2-5所示，秘密可以通过将超过一定门限数量的若干个分片重新组合进行复原，但单一的分片无法获取关于秘密的有效信息。因此，即使有参与者出现问题，在一定数量范围内，秘密仍能完整恢复，从而有效地防止系统外敌人的攻击和系统内用户的背叛。
图2-5 秘密分享的概念图
同时，秘密分享还具有同态的特性。A和B两个秘密被随机分成多个碎片（X1，X2，…，Xn）和（Y1，Y2，…，Yn），并分配到不同参与节点（S1，S2，…，Sn）中，每个拿到碎片节点的运算结果再求和能够重新构造原始的秘密值。图2-6给出了一个基于秘密分享的计算示例。这也是实现不交换原始数据，直接进行计算的重要基础。
图2-6 基于秘密分享的求和计算
目前，秘密分享的实现方案主要有以下几个。
（1）（t，n）阈值密钥分享方案。即将秘密分享给n个参与方，允许任意t个参与方将秘密数据解开，但任何不多于t-1个参与方的小团体都无法将秘密数据解开。目的是利用n个共享中的至少t个共享之间的相互协作来控制某些重要任务，如导弹发射的控制、支票签署等。
（2）多秘密分享方案。同时保护多个秘密，将不同的秘密和不同的授权子集联系在一起。
（3）带除名的秘密分享方案。n个用户参与的秘密分享方案中如果有一个用户不能信赖，则可将这个用户除名，变成有n-1个用户参与的秘密分享方案。