2.5.2 安全多方计算中的密码协议

1.不经意传输协议

在上文描述的百万富翁问题的解决方案中，在富翁B得到9个盒子之后，如何确定其会将其余盒子全部销毁是一个在现实中很难解决的问题。不经意传输（Oblivious Transfer，OT）协议则从根本上提出了一个解决方案，避免了富翁B未按照协议销毁其他盒子而产生的安全问题。从直观上来看，不经意传输协议的功能是保证富翁B从富翁A提供的两个或者多个备选项目中只能选择其中一个，而得不到其他备选项目的任何信息，同时还能保证富翁A不知道富翁B选择的具体是哪一个。

不经意传输协议是安全多方计算研究中的一个基础的密码协议，具体的定义如下：

定义2-11 不经意传输协议指的是，Alice输入一个包含两个信息的集合{m₀，m₁}，Bob选择一个标签b∈{0，1}，一个不经意传输协议满足以下条件：Bob作为协议的一方，一定可以获得m_b，但无法获得m_1-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阶循环群G_q中的元素。

（2）Alice输入n个消息m₁，m₂，…，m_n∈G_q，同时Bob确定欲选择的消息编号t。

（3）Bob选择随机数r，并计算y=grht，将y发送给Alice。

（4）Alice选择一组随机数k_i，使用y计算n组消息：（a₁，b₁），（a₂，b₂），…，（a_n，b_n），并发送给Bob。其中，，。

（5）Bob计算。

不经意传输协议的过程看似比较复杂，但如果我们对比上文中百万富翁问题的解决方案的不经意传输协议构造，就会更容易理解。其中，y对应的便是“组合锁”，而（a_i，b_i）则对应由组合锁改造的新锁保护的明文，Bob在收到所有被保护的明文之后，只能对第t个明文进行解密，因为y是由t构造的。

2.混淆电路

安全多方计算目前的主流构造方法主要有两种，第一种是使用混淆电路，第二种则是通过秘密分享的思想。下面会对混淆电路、秘密分享的原理和思想分别进行介绍。

混淆电路是姚期智院士针对百万富翁问题，于1986年提出的一种解决方案，该方案的提出也验证了安全多方计算的可行性。混淆电路的思想比较简单：将双方需要计算的函数（所需参数为双方各自的输入信息）转化为“加密电路”的形式，该“加密电路”可以保证双方在不泄露各自输入信息的情况下，正确地计算出函数的结果。因此，“加密电路”的设计是混淆电路方法的研究重点和难点。但是，由于任意函数在理论上均存在一个等价的电路表示，在计算机中可以使用加法器和乘法器等电路进行实现，而这些乘法器或加法器又可以通过“与门”“异或门”等逻辑电路来表示。也就是说，如果能够实现基本的加密版本逻辑电路，那么可以实现加密版本的计算函数。

接下来，我们通过文献[66]对“与门”加密版本的实现来介绍“加密电路”的实现方法以及工作原理。

假设在安全两方计算中，交互两方A和B欲计算的门电路为“与门”，两个输入数据分别为a和b，一个输出数据为r，即r=aandb。我们可以用表2-3所示的真值表的方式来描述该电路门（也就是说，“与门”电路与以下真值表是等价的，真值表的加密版本也就对应了“与门”电路的加密版本）。

第一步：A方进行密钥生成。

为了避免使用真实的输入数据和输出数据，对输入和输出的每一个值都生成相应的密钥，在交互过程中只使用该密钥代替真实值进行传递，从而避免了真实输入数据的泄露。输入及输出结果对应的密钥见表2-4。

第二步：A方进行电路的加密。

对原始的真值表中真实的输入和输出数据进行替换得到其加密版本，见表2-5。

第三步：A方将输出的密文发送给B方。

A方将第二步得到的密文打乱顺序之后发送给B方，同时要告知B方k_aj和k_bi的信息，让B方进行解密。其中，k_aj对应A方的输入数据a，但k_bi对应B方的输入数据b，由于A方并不知道B方的真实输入数据是多少，便无法确定应该向B方提供k_b0还是k_b1。此时便可使用上文介绍的不经意传输协议满足该需求，既能保证B方根据自己的输入数据b的编号i选择对应的k_bi，又能保证B方只能获得k_b0和k_b1中的一个。

第四步：B方进行解密。

B方使用A方提供的k_aj（j=0或1）以及使用不经意传输协议选出的k_bi（i=0或1）对四个密文进行解密，使用的加密算法可以保证只有在使用正确的密钥进行解密时才可以得到合法的明文，也就是说，如果k_aj和k_bi对应的密文为，那么只有在对使用密钥k_aj和k_bi进行解密时才能得到合法的明文，其他几个明文都会是乱码或者特殊的符号。

此时，B方将解密得出的明文k_r0或k_r1发送给A方，A方便可得出正确的结果r=0或者r=1，并同步给B方即可。在这个过程中，A方并没有告诉B方k_aj对应的真实值j=0或j=1，因此A方的信息未泄露。另外，B方通过不经意传输协议选择了输入对应的密钥，在计算出正确结果并发送给A方之前，也并未泄露自己的输入数据。所以，双方均在未泄露自己输入数据的前提下，完成了“与门”的计算。

以上便是混淆电路协议的简单构造。混淆电路作为安全多方计算领域最基础的协议之一，对密码学实际应用的意义非凡，从1986年发展至今，仍有大量的专家学者在进行探索。混淆电路源于安全两方计算方案，现在已经被推广到安全多方计算的方案设计。另外，也有众多技术（如“Free-XOR”）用于混淆电路的构造中[67]，以提高基于混淆电路的安全多方计算的效率。

3.秘密分享

除了使用混淆电路，秘密分享是另外一个用于构造安全多方计算的主流技术。秘密分享是现代密码学的一个重要工具，是门限密码学的基础。提到门限密码学，我们可以使用一个有趣的例子进行简单的介绍。

门限密码学是指将基本的密码系统分布于多个参与方之间，只有所有的参与方或者足够多的参与方联合起来才能保证密码系统正常运行。门限密码学有很多应用场景，假设某国的特工局局长将本国的特工名单保存在一个保险箱中，而局长希望将保险箱的密钥切分为4个部分，由4位副局长分别持有。考虑到特工职业的特殊性，局长提出了两个要求：①因为特工属于高危职业，为了防止因某位副局长意外牺牲而导致其持有的部分密钥随之消失，局长希望无须4位副局长同时提供密钥，也能打开保险箱（容错性要求）；②为了防止因某几位副局长叛变而导致特工名单泄露，局长希望至少3位副局长同时提供密钥才能打开保险箱（安全性要求）。

考虑到以上两个要求，局长确定了保险箱最终的密钥管理方式：任意3位副局长同时提供密钥，便可打开保险箱；若提供密钥的副局长少于3位，则无论如何都无法打开保险箱。这样的系统便需要使用门限密码学来设计。

从图2-7中可以看到，如果将密钥分为6段，每段都有两份，那么每个副局长都持有其中3段，比如a副局长持有第1段、第2段和第3段，使用这样的分割方法可以保证任意3位副局长都可以恢复完整的密钥，但如果只有1位或者2位副局长，就无法完成密钥的恢复。以上便是门限密码学的应用。

在安全多方计算中，秘密分享的应用场景主要为使用秘密分享方案的同态特性进行约定函数的计算。也就是说，秘密分享的内容不再是密钥，而是参与方的输入数据，通过将输入数据切分成多个随机的碎片，分发给其他参与方。每个参与方根据自己掌握的碎片进行相关的计算，将中间结果进行聚合，从而得到最终结果。在本节中，我们会使用具体的例子简述这种思想的构造方法。使用秘密分享进行函数计算的协议主要由两部分构成：秘密分发和秘密重构。

随着秘密分享技术的发展，目前已经出现了多种协议的实现方案，在此我们使用著名的Shamir秘密分享协议来介绍一下秘密分发和秘密重构两个部分是如何完成的。Shamir秘密分享协议使用多项式对秘密输入进行分发，并通过拉格朗日插值方法对秘密输入进行恢复。为了方便理解，我们仍以4位副局长对密钥保管为例，局长希望将密钥S分发给4位副局长，且只要其中3位副局长同时提供各自持有的信息就可恢复密钥。Shamir秘密分享协议会为密钥S生成一个多项式f（x）=S+a₁x+a₂x2，并随机选取该多项式的点值，即（x_i，y_i）作为密钥的局部信息分发给各位副局长。这便完成了秘密分发。由于该多项式共有3个未知的系数（S，a₁，a₂），故至少需要3个点值才能对密钥S进行恢复，且任意3个不同的点值均可。这便完成了秘密重构。

接下来，以3个参与方之间的安全计算场景为例，简单地介绍使用秘密分享进行加法和乘法操作的基本步骤，帮助读者理解秘密分享的基本原理。

假设某公司的3个员工分别为P₁，P₂，P₃，3人希望在不泄露自己真实工资的情况下，计算3人的平均工资。从本质上来讲，这个问题可以抽象为多方之间的求和问题。我们在此介绍一下使用秘密分享进行求和的思想。假设员工P₁，P₂，P₃的工资分别为x，y，z。为了计算r=（x+y+z）/3，可以采取以下两个步骤。

（1）秘密分享阶段。每个员工将自己的输入信息（即工资）切分成3份，并分发给另外两个同事；在分发完成之后，员工_iP拥有3个值，分别为x_i，y_i，z_i。

（2）秘密重构阶段。每个员工分别在本地计算r_i=（x_i+y_i+z_i）/3，最终三个员工再将自己的结果r_i进行公开，3人的平均工资则为r=r₁+r₂+r₃。

在以上两个步骤中，每个员工都只得到了同事工资的部分信息，并不能恢复其真实工资。另外，根据最终公布的结果r_i也无法直接推断出x_i，y_i，z_i三个碎片信息。因此，该方法便使用秘密分享的思想，在保护了各个参与方输入信息的前提下，完成了均值的计算。

使用秘密分享的方法计算求和函数是非常简单、直观的，但如果要计算两个数的乘积，就需要引入一些“辅助信息”。仍以上述的场景为例，假设3个员工都有强烈的好奇心，希望在对自己工资保密的前提下，计算他们工资的乘积，即r=xyz。此时，仅仅通过将工资的数值进行简单的切分和分享是很难做到的，因为乘法会涉及交叉项的计算。举个例子，xy=（x₁+x₂）（y₁+y₂）=x₁y₁+x₁y₂+x₂y₁+x₂y₂。按照秘密分享进行加法计算的思想，直接计算x₁y₂和x₂y₁是很困难的，但是如果加入“辅助信息”，就可以解决这个问题。为了方便理解，我们先计算r＇=xy，在完成r＇的计算后，计算r便很自然。其中，计算r＇的具体方法如下。

（1）在计算r＇之前，先通过某种手段完成三元组（辅助信息）的秘密分发。3个值分别为

a=a₁+a₂+a₃

b=b₁+b₂+b₃

c=c₁+c₂+c₃

式中，c=ab。

（2）秘密分发。与秘密分享计算加法的秘密分发阶段类似，由于以r＇=x·y的计算为例，在此仅进行x和y的分发。通过分发阶段，不同员工持有的碎片信息见表2-6。

（3）秘密重构。

①借助辅助信息，计算两个中间变量（使用秘密分享进行加法计算的思想），即

ma=x-a

mb=y-b

②为了恢复r＇=xy，根据公式

展开可得

通过该公式，我们发现将xy的乘法问题转化为3个乘法子问题以及加法问题。已知两个中间值m a和mb已经通过秘密分享的加法计算被重构，因此只要每一方都能计算出式（2-15）中ma·b+mb·a+c的碎片信息即可。通过将3者计算的碎片信息与ma·mb相加，便可得到最终的计算结果r＇=xy=ma·mb+ma·b+mb·a+c。不同员工计算的碎片信息见表2-7。

以上便是使用辅助信息（三元组[a，b，c]）进行乘法运算的示例，通过秘密分享实现了乘法和加法运算。在此基础上，可以使用这两种基本运算设计或者拟合更多、更复杂的运算，从而构造完整的、通用的安全多方计算。