浙江龙网

  1. 首页 > 生活百科 > >

MPC：百万富翁问题( 二 )

生活百科


文章插图

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

MPC：百万富翁问题

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

MPC：百万富翁问题

文章插图
  • 第三步，Alice将输出的密文发送给Bob：Alice将第二步得到密文\(E_{k_{aj},k_{bi}}(k_{rt})\)打乱数据【混淆】之后发送给Bob，同时告知Bob\(k_{aj},k_{bi}\)的信息，让Bob解密 。其中\(k_{aj}\)对应Alice的输入数据\(a\)，\(k_{bi}\)对应于Bob的输入数据 ， 但由于Alice不知道Bob的真实输入数据，便无法确定应该向Bob提供\(k_{b0}\)还是\(k_{b1}\)，这是便可以使用OT ， 既能保证Bob根据自己的输入数据\(b\)的编号\(i\)对应的\(k_bi\) ， 又能保证Bob只能获得\(k_{b0}\)和\(k_{b1}\)中的一个 。
  • 第四步，Bob解密：Bob使用Alice提供的\(k_{aj}\)和OT协议选出的\(k_{bi}\)对四个密文解密，其中只有密文是\(E_{k_{aj},k_{bi}}(k_{rt})\)时才能正确解密，否则得到的是乱码 。然后Bob将解密结果发给Alice ， Alice得到正确结果\(r=0\)或者\(r=1\) ， 并同步给Bob 。
?：
  • 整个过程 ， Alice没有告诉Bob关于\(k_{aj}\)对应的真实值，Bob通过OT得到了\(k_{bi}\)，也没有泄露信息，所以双方在均未泄漏数据的前提下完成了“与门”计算
SSSS的应用在MPC中，主要是利用其同态特性进行函数计算，下面介绍使用SS构造实现加法和乘法运算：
加法假设某公司的 3 个员工分别为 \(P_1, P_{2}, P_{3}\)，3 人希望在不泄露自己真实工资的情况下, 计算3人的平均工资 。
从本质上来讲, 这个问题可以抽象为多方之间的求和问题 ， 我们在此介绍一下使用秘密分享进行求和的思想 。
假设员工\(P_{1}, P_{2}, P_{3}\) 的工资分别为\(x, y, z\) ， 为了计算\(r=(x+y+z) / 3\)，可以采取以下两个步骤：
  • 秘密分享阶段 。每个员工将自己的输入信息 (即工资) 切分成3份, 并分发给另外两个同事; 在分发完成之后, 员工$ P_{i}$ 拥有 3 个值, 分别为$x_{i}, y_{i}, z_{i}$ 。
  • 秘密重构阶段 。每个员工分别在本地计算 $ r_{i}=\left(x_{i}+y_{i}+z_{i}\right) / 3$，最终三个 员工再将自己的结果 $r_{i} $进行公开, 3 人的平均工资则为 $ r=r_{1}+r_{2}+r_{3}$。
在以上两个步骤中, 每个员工都只得到了同事工资的部分信息, 并不能恢复其真实工资 。另外, 根据最终公布的结果$ r_{i}$ 也无法直接推断出\(x_{i}, y_{i}, z_{i}\) 三个碎片信 息 。因此，该方法便使用秘密分享的思想 ， 在保护了各个参与方输入信息的前提下完成均值计算 。
乘法假设员工\(P_{1}, P_{2}, P_{3}\) 的工资分别为\(x, y, z\)，为了计算\(r=xyz\)。
而对于乘法计算，就比较复杂了 ， 因为乘法会涉及交叉项，例如\(xy=(x_1+x_2)(y_1+y_2)=x_1y_1+x_1y_2+x_2y_1+x_1y_2\)，其中直接计算\(x_1y_2,x_2y_1\)是非常麻烦的【因为信息属于两个人】，这时就需要引入一些辅助信息：
  • 三元组生成和分发 ， 即\(P_1\)有\(a_1,b_1,c_1\)，\(P_2\)有\(a_2,b_2,c_2\)，\(P_3\)有\(a_3,b_3,c_3\) 。
\(\begin{array}{l} a=a_{1}+a_{2}+a_{3} \\ b=b_{1}+b_{2}+b_{3} \\ c=c_{1}+c_{2}+c_{3} \end{array}\)
其中\(c=ab\) 。
  • 密秘分发，即将\(x,y\)分发，得到以下结果：

MPC：百万富翁问题

文章插图
  • 秘密重构
（1）借助辅助信息，先计算出：\(ma=x-a,mb=y-b\)，即利用上述加法特性，以\(x-a\)为例：三方共享计算\(x_1-a_1,x_2-a_2,x_3-a_3\)，然后得到\(x-a\)
（2）计算\(xy=(x-a+a)(y-b+b)=(m a+a)(m b+b)=m a \cdot m b+m a \cdot b+m b \cdot a+c\)，可以看出将\(xy\)问题转化为三个乘法问题和加法问题，其中\(ma,mb\)已经得到，因此只需各方计算出\(ma.b+mb.a+c\)的碎片即可：
MPC：百万富翁问题

文章插图
（3）然后将\(ma.b+mb.a+c\)与\(ma.mb\)相加 ， 便可以得到\(xy\)，进而通过这种方法求出\(xyz\) 。
?：

上一篇：SimpleDateFormat线程安全问题排查

下一篇：没有了