MPC：百万富翁问题 _生活百科

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

百万富翁问题

文章插图
将问题具体化：
Alice有\(i\)亿元， Bob有\(j\)亿元，为方便描述，我们限定\(0<i, j \leq 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\)阶循环群\(G_q\)中的元素
Alice输入\(n\)个消息\(m_1,...,m_n\in G_q\)，同时Bob确定选择的消息编号\(t\)
Bob选择随机数\(r\)，计算\(y=g^rh^t\)，并将其发送给Alice
Alice选择一组随机数\(k_i\)，计算\(n\)组消息：\((a_i,b_i)\)，并发送给Bob，其中\(a_i=g^{k_i},b_i=m_i*(\frac{y}{h_i})^{k_i}\)
Bob计算出\(m_t=\frac{b_t}{a_t^r}\)

?：

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

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

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

混淆电路的核心就是“加密电路”设计，这是研究重点和难点，由于任意函数理论上都存在一个等价的电路表示，在计算机中可以使用加法器和乘法器实现，而乘法器/加法器可以通过“与门”、”异或门“等逻辑电路来表示。
下面介绍一种”与门“函数实现加密电路：
假设在安全两方计算中，参与方A和B要计算”与门“的门电路，即两者输入分别是\(a,b\)，输出是\(r=a（and）b\)：