MPC：百万富翁问题 - PamShao

学习文章：“一起学MPC：（一）百万富翁问题”和“【隐私计算笔谈】MPC系列专题（一）：安全多方计算应用场景一览”

百万富翁问题#

将问题具体化：

Alice有i亿元，Bob有j亿元，为方便描述，我们限定0<i,j≤10。现在想在不暴露和的情况下，比较i和j的大小。

解决思路#

第二步：Bob把第j个箱子上的编号撕掉，并将其他箱子都销毁掉，把这个没有编号的箱子发给Alice

以上是解决百万富翁问题的思路之一，但是建立在双方都是诚实的或者半诚实的前提下，即双方不会恶意的输入或者输出错误值扰乱协议的正确执行，也就是说可以保证Bob不会选择错误的箱子或者将错误的箱子发送给Alice，但是无法保证Bob能克制住自己的好奇心，将其他的箱子都销毁掉，因为即使Bob不销毁其他的箱子，协议也能正常执行，符合一个半诚实参与方的要求。

在实际应用中，双方使用密码协议实现这些理想的限制条件，即即使是半诚实的参与方，协议也不会泄露隐私。比如OT，可以保证Bob只能选一个箱子，而不能获取其他箱子的内容，同时Alice也无法得知Bob选的是哪个箱子。

下面给出其他的方式解决以上问题

OT#

对于百万富翁问题存在的隐患，即确认Bob是否会将其与的箱子销毁是一个很难解决的问题。OT可以解决该问题，可以避免Bob未按照协议销毁其他箱子而产生的安全问题。

直观上看，OT协议只能保证Bob从Alice准备的10个箱子中选择一个，而得不到其他箱子（其他信息），同时还能保证Alice不知道Bob选择了哪个箱子。

所以这里符合(1−n)OT，即n取1，下面用一个例子介绍方案的思想：

• Alice在锁上箱子前，Bob先利用所需箱子的编号j构造一把“复杂”的组合钥匙（可以看做OPRF(j)），将其发送给Alice；

• Alice拿到组合钥匙后，通过一种黑盒的方式对组合锁进行改造，生成10把不同的新锁，并分别对10个箱子进行上锁；【新锁的特性是只有编号为j的箱子上的新锁可以用Bob的组合钥匙打开，其余箱子上的新锁无法被打开】；

• Bob只能打开编号为j的箱子，而Alice并不能根据组合钥匙分析出编号j。

换成具体协议(1−n)−OT表示：

• 双方协商出公参数：g,h，都是q阶循环群Gq中的元素
• Alice输入n个消息m1,...,mn∈Gq，同时Bob确定选择的消息编号t
• Bob选择随机数r，计算y=grht，并将其发送给Alice
• Alice选择一组随机数ki，计算n组消息：(ai,bi)，并发送给Bob，其中ai=gki,bi=mi∗(yhi)ki
• Bob计算出mt=btatr

• 其中y就是组合钥匙，(ai,bi)就是新锁
• 通过OT协议可以实现Bob只能获取编号为j的箱子，对其他的箱子一无所知，且Alice也不知道Bob选择的哪个箱子，这样其他箱子销毁与否无关紧要，从而避免了以上说的安全问题。

GC#

混淆电路是姚针对百万富翁问题在1986年提出的一种解决方案，同时也验证了安全多方计算的可行性，即百万富翁问题就是MPC的一个简单例子，即参与方在不泄漏自身数据的情况下完成某种计算，下面介绍利用混淆电路实现该功能！

混淆电流的思路是将双方需要计算的函数转换为“加密电路”，其中“加密电路”可以保证双方在不泄漏各自输入信息的情况下，正确的计算函数的结果。

混淆电路的核心就是“加密电路”设计，这是研究重点和难点，由于任意函数理论上都存在一个等价的电路表示，在计算机中可以使用加法器和乘法器实现，而乘法器/加法器可以通过“与门”、”异或门“等逻辑电路来表示。

下面介绍一种”与门“函数实现加密电路：

假设在安全两方计算中，参与方A和B要计算”与门“的门电路，即两者输入分别是a,b，输出是（）r=a（and）b：

• 下表是“与门”真值表

• 第一步，Alice密钥生成：对输入和输出的每个值都生成对应的密钥，在交互过程中使用该密钥替换真实值进行传输，从而避免真实数据的泄露。

• 第二步，Alice进行电路加密（就是替换）：对原始真值表真实的输入和输出数据进行替换得到加密版本：

• 第三步，Alice将输出的密文发送给Bob：Alice将第二步得到密文Ekaj,kbi(krt)打乱数据【混淆】之后发送给Bob，同时告知Bobkaj,kbi的信息，让Bob解密。其中kaj对应Alice的输入数据a，kbi对应于Bob的输入数据，但由于Alice不知道Bob的真实输入数据，便无法确定应该向Bob提供kb0还是kb1，这是便可以使用OT，既能保证Bob根据自己的输入数据b的编号i对应的kbi，又能保证Bob只能获得kb0和kb1中的一个。
• 第四步，Bob解密：Bob使用Alice提供的kaj和OT协议选出的kbi对四个密文解密，其中只有密文是Ekaj,kbi(krt)时才能正确解密，否则得到的是乱码。然后Bob将解密结果发给Alice，Alice得到正确结果r=0或者r=1，并同步给Bob。

• 整个过程，Alice没有告诉Bob关于kaj对应的真实值，Bob通过OT得到了kbi，也没有泄露信息，所以双方在均未泄漏数据的前提下完成了“与门”计算

SS#

SS也能构造MPC，下面介绍使用SS构造实现加法和乘法运算：

加法#

假设某公司的 3 个员工分别为 P1,P2,P3，3 人希望在不泄露自己真实工资的情况下, 计算3人的平均工资。

从本质上来讲, 这个问题可以抽象为多方之间的求和问题，我们在此介绍一下使用秘密分享进行求和的思想。

假设员工P1,P2,P3 的工资分别为x,y,z ，为了计算r=(x+y+z)/3 ， 可以采取以下两个步骤：

• 秘密分享阶段。每个员工将自己的输入信息 (即工资) 切分成3份, 并分发给另外两个同事; 在分发完成之后, 员工Pi 拥有 3 个值, 分别为 xi,yi,zi。
• 秘密重构阶段。每个员工分别在本地计算 ri=(xi+yi+zi)/3 ，最终三个 员工再将自己的结果 ri进行公开, 3 人的平均工资则为 r=r1+r2+r3 。

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

乘法#

假设员工P1,P2,P3 的工资分别为x,y,z ，为了计算r=xyz 。

而对于乘法计算，就比较复杂了，因为乘法会涉及交叉项，例如xy=(x1+x2)(y1+y2)=x1y1+x1y2+x2y1+x1y2，其中直接计算x1y2,x2y1是非常麻烦的【因为信息属于两个人】，这时就需要引入一些辅助信息：

• 三元组生成和分发，即P1有a1,b1,c1，P2有a2,b2,c2，P3有a3,b3,c3。

a=a1+a2+a3b=b1+b2+b3c=c1+c2+c3

其中c=ab。

• 密秘分发，即将x,y分发，得到以下结果：

（1）借助辅助信息，先计算出：ma=x−a,mb=y−b，即利用上述加法特性，以x−a为例：三方共享计算x1−a1,x2−a2,x3−a3，然后得到x−a

（2）计算xy=(x−a+a)(y−b+b)=(ma+a)(mb+b)=ma⋅mb+ma⋅b+mb⋅a+c，可以看出将xy问题转化为三个乘法问题和加法问题，其中ma,mb已经得到，因此只需各方计算出ma.b+mb.a+c的碎片即可：

（3）然后将ma.b+mb.a+c与ma.mb相加，便可以得到xy，进而通过这种方法求出xyz。

• SS的乘法需要使用辅助信息三元组，在加法和乘法基础上，可以组合出更加复杂的运算，构造出更加完整、通用的MPC协议。
• GC构造的MPC更适合于逻辑运算或数字的比较运算，比如百万富翁问题。
• SS构造的MPC更适用于算术运算。

姚期智院士在提出“百万富翁问题”的同时，给出了三种解决办法【OT、GC、SS？】，并讨论了在秘密投票（Secret Vote）、不经意协商（Oblivious Negotiation）、隐私查询数据库（Private Querying of Database）的应用。

之后 Goldreich 在1987年对安全多方计算（Secure Multi-Party Computation）进行了讨论，提出了可以计算任意函数的计算意义下安全的安全多方计算协议。Goldreich 还从理论上证明了可以通过通用电路（Universal Circuit）估值来实现所有的安全多方计算协议。其后于1988年，Goldreich 对安全多方计算进行了总结和安全性定义。

之后在 1989 年，Beaver 等人研究了信息论安全模型下的安全多方科学计算问题，提出了可以实现信息论安全的，复杂程度为常数轮的安全多方算数运算协议。

应用#

安全多方计算兼具理论研究和实际应用价值，在电子投票、隐私保护的数据挖掘、机器学习、区块链、生物数据比较、云计算等领域有着广泛的应用前景。

现实生活中的投票选举通过统一采用空白选票、投票箱、有公信力的计票人以及全程录像直播等方式来确保公平公正。而在电子投票领域，投票人在家投票时，家中的计算机可能已被感染病毒，投票结果可能被恶意获取篡改等，因此电子投票系统必须保证投票人知道自己的投票信息是否被正确提交，是否被恶意攻击者篡改，同时要保护投票人的投票信息不被除了计票人外的其他人获取。安全多方计算为这种分布式环境下如何进行保护隐私信息和确保结果正确性的问题提供了良好解决方案。

Cramer 等人基于 ElGamal 门限加密技术和零知识证明提出了首个多选一电子投票方案，之后 Damgard 等人基于 Pailier 同态加密技术提出了多选多的电子投票方案。在1992年，A.Fujioka 等使用盲签名技术提出了著名的 FOO 电子投票协议。

数据挖掘作为一个非常有效的数据分析工具，可以发现数据中隐含的规律，对科学和政策研究、商务决策等方面有着重要应用。然而被挖掘的数据中往往都有着大量敏感性的信息，因此必须受到保护，在隐私保护下进行数据挖掘。

在多方情况下进行数据挖掘时，参与者往往不愿意共享数据，只愿意共享数据挖掘的结果，这种情况在科学和医学研究等方面非常常见，如各个医疗机构的病人信息是敏感信息，不会愿意透露。应用安全多方计算可以在保护各方数据信息不被泄露的同时多方协作完成数据挖掘。

机器学习已被应用到各个领域，引发了大量变革，如图像和语音识别、异常检测等。而在机器学习想要取得好的效果，需要大量数据进行模型训练，训练数据的隐私保护同样是问题，在多个机构合作进行模型训练时，数据分布在不同参与者处，安全多方计算可以在保护敏感数据的隐私性的同时让各个机构成功进行模型训练。

总之，当各个参与者处于分布式环境下，又有数据隐私保护的要求时，十分适合应用安全多方计算来解决问题。

参考#

1、联邦学习-技术及实践