安全多方计算之二：一文搞懂百万富翁问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了安全多方计算之二：一文搞懂百万富翁问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方及其他第三方知道自己财富的任何信息，这是由中国计算机科学家、2000年图灵奖获得者姚启智教授于1982年在论文《Protocols for secure computations》中提出的姚氏百万富翁问题，开创了密码学研究的新领域：安全多方计算(Secure Multi-party Computation)。

安全多方计算之二：一文搞懂百万富翁问题
姚期智，1946年12月24日出生于中国上海，由于计算理论及其在密码学和量子计算中的应用方面的贡献获2000年图灵奖。2004年，当选为中国科学院外籍院士。同年，57岁的姚期智辞去普林斯顿大学终身教职，加盟清华大学高等研究中心，担任全职教授。2016年放弃美国国籍成为中国公民，正式转为中国科学院院士，加入中国科学院信息技术科学部，现任清华大学交叉信息研究院院长。

1. 解决方案

假设两个百万富翁 $A$ 和 $B$ 的财产在 $1$ 到 $10$ 之间， $A$ 为 $4$ ， $B$ 为 $9$ 。

$A$ 选择 $10$ 个相同的个盒子，按照顺序代表 $1$ 到 $10$ ：
$A$ 用自己财产的数字与盒子的数字进行比较，如果小于该数字，则放一个黑球，若大于等于则放一个蓝球。

安全多方计算之二：一文搞懂百万富翁问题

$A$ 将盒子上锁，并按 $1$ 到 $10$ 的顺序发交给 $B$ 。
$B$ 选择自己财产的数字对应的箱子，即第 $9$ 个盒子，然后交个 $A$ 。
由 $A$ 打开盒子，共同判定结果：蓝球，因此 $B$ 更富有。

现实中，上述方案一般通过密码学工具实现。

2. 协议描述

姚氏百万富翁问题可形式化描述为:对两个秘密输入 $i$ 和 $j$ ，判断函数值 $f(i,j)=i-j\le 0$ 还是 $f(i,j)=i-j\ge 0$ 。

假定 $\le i,j \le N$ 。为了在不让任何第三方参与的情况下比较 $i$ 和 $j$ 的大小，又不向对方泄漏各自的数值，则可执行如下的协议:

step1： $A$ 和 $B$ 共同协商一种公钥加密体制( $E$ 为加密算法， $D$ 为解密算法)。
step2： $A$ 随机选择一个大随机数 $x$ ,用B的公钥加密得 $E (x)$ ，然后将 $E (x) - i$ 发送给 $B$ 。
step3： $B$ 首先计算 $N$ 个数 $y_u=D(E(x)-i+u),u=1,2,...,N$ 然后随机选择大素数 $p$ ，再计算 $N$ 个数 $z_u \equiv y_u \bmod p,u=1,2,…,N$ 接着验证对于所有的 $\le a \neq b \le N-1$ 是否都满足 $z_a-z_b|≥2$ ，若不满足，则重新选择大素数 $p$ 重新验证。最后， $B$ 将 $p$ 及以下的 $N$ 个数串发送给 $A$ : $z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1$ .- step4：设 $A$ 收到 $N$ 个数串的第 $i$ 个数 $z_i \equiv x \bmod p$ ，则结论是 $\le j$ ；否 $\ge j$ 。
step5： $A$ 将结果告诉 $B$ 。

3. 协议说明

(1) 由于 $z_i \equiv y_i \bmod p \equiv D(E(x)-i+i)\equiv x \bmod p$ ，因此
当且仅当 $i\le j$ 时,数列 $z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1$ 中才存在数 $z_i \equiv x \bmod p$ ；否则该数列中任何数模 $p$ 都不与 $x$ 同余，此时 $i > j$ 。该步骤是协议的核心步骤，通过构造数列，实现了 $i$ 与 $j$ 大小的判断，类似于放置黑球与蓝球。

但该协议无法判断出 $i = j$ 的情况，是该协议的一个缺点，后续相关研究对此进行了改进。

(2)要求 $z_n$ 中的任何两个数 $z_a,z_b$ 满足 $z_a-z_b|≥2$ 是为了保证 $B$ 发送给 $A$ 的 $N$ 个数的数列 $z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1$ 中任意两个数不同,一般称这样的数列为“好数列”。因为若数列中存在两个数 $z_m=z_n，m<n$ ，则 $A$ 可以判断出 $B$ 的秘密数大致范围为 $m\le j<n$ 。

（3） $A$ 比 $B$ 先知晓了最终的结果，若 $A$ 欺骗 $B$ 告诉他相反的结论，则该协议是不公平的。为增加公平性, $B$ 可以要求与 $A$ 交换角色，即原来 $A$ 执行的步骤现由 $B$ 执行，而由 $B$ 执行的步骤改由 $A$ 执行。这样 $B$ 也可以首先得出结论。

4. 协议举例

设 $A$ 和 $B$ 两个百万富翁的财富， $A$ 的财富是 $900$ 万， $B$ 的财富是 $400$ 万，都不超过 $1000$ 万。即 $A$ 和 $B$ 的秘密数分别为 $i = 9$ 和 $j = 4$ ， $N = 10$ 。

step1： $A$ 和 $B$ 选定RSA公钥算法对数据加密，其中 $n = 221$ ， $B$ 的公钥 $35$ ，私钥 $11$ 。
step2： $A$ 随机选择整数 $x = 92$ ，计算 $\equiv 92^{35} \bmod 221=105$ ，然后把 $E (x) - i = 105 - 9 = 96$ 发送给B。
step3：对 $u = 1, 2, \dots, 10$ ， $B$ 分别计算 $y_u=D(E(x)-i+u)=D(96+u)$ 即 $y_1=D(96+1)\equiv 97^{11}\bmod 221=193$ $y_2=D(96+2)\equiv 98^{11}\bmod 221=106$ $y_3=D(96+3)\equiv 99^{11}\bmod 221=44$ $y_4=D(96+4)\equiv 100^{11}\bmod 221=94$ $y_5=D(96+5)\equiv 101^{11}\bmod 221=186$ $y_6=D(96+6)\equiv 102^{11}\bmod 221=136$ $y_7=D(96+7)\equiv 103^{11}\bmod 221=103$ $y_8=D(96+8)\equiv 104^{11}\bmod 221=195$ $\underline{y_9=D(96+9)\equiv 105^{11}\bmod 221=92}$ $y_{10}=D(96+10)\equiv 106^{11}\bmod 221=98$

取素数 $p = 109$ ，计算 $z_u \equiv y_u \bmod p \equiv y_u\bmod 109,u=1,2,…,10$ 得
$z_1\equiv y_1 \bmod 109\equiv 193\bmod 109=84$ $z_2\equiv y_2 \bmod 109\equiv 106\bmod 109=106$ $z_3\equiv y_3 \bmod 109\equiv 44\bmod 109=44$ $z_4\equiv y_4 \bmod 109\equiv 94\bmod 109=94$ $z_5\equiv y_5 \bmod 109\equiv 186\bmod 109=77$ $z_6\equiv y_6 \bmod 109\equiv 136\bmod 109=27$ $z_7\equiv y_7 \bmod 109\equiv 103\bmod 109=103$ $z_8\equiv y_8 \bmod 109\equiv 195\bmod 109=86$ $\underline{z_9\equiv y_9 \bmod 109\equiv 92\bmod 109=92}$ $z_{10}\equiv y_{10} \bmod 109\equiv 98\bmod 109=98$

$B$ 对数列进行验证，并将 $p = 109$ 及以下数列发送给 $A$ $z_1 = 84,z_2=106,z_3=44,z_4= 94,z_5+1= 78,z_6+1=28,z_7+1=104,z_8+1=87,\underline{z_9+1=93},z_{10}+1=99$

step4： $A$ 检查该数列中的第 $9$ 个数是 $93$ ，由于 $\neq 92\bmod 109$ ，因此 $i > j$ ，即 $A$ 比 $B$ 更富有。
step5： $A$ 将结果告诉 $B$ 。

5. 协议扩展

（1）社会主义百万富翁问题

社会主义百万富翁问题是百万富翁问题的引申，描述如下：Alice有数值 $a$ ，Bob有数值 $b$ ，不泄漏各自任何信息的情况下得到 $a = b$ 或 $a\neq b$ 。

（2）向量相等判定

Alice有向量 $A=(a_1,a_2,...,a_n)$ ，Bob有向量 $B=（b_1,b_2,...,b_n)$ ，不泄漏各自任何信息的情况下得到 $A = B$ 或 $\neq B$ 。

（3）安全数据排序文章来源地址https://www.toymoban.com/news/detail-500234.html

安全多方单数据排序： $n$ 个参与方 $P_1,P_2,...,P_n$ ，每个持有秘密数据 $x_i（i=1,2,...,n）$ ，在 $P_i$ 不泄露 $x_i$ 任何信息给其他参与者的情况下，得到 $x_i$ 在这些数据中的排序位置 $y_i$ 。
安全多方多数据排序： $n$ 个参与方 $P_1,P_2,...,P_n$ ，每个持有秘密数据集 $X_i（i=1,2,...,n)$ ，将 $n$ 个数据集合的并集 $X=X_1\cup X_2,...,X_n$ 中所有的数据按照小到大的顺序安全地排成一个序列，排序结束后， $P_i$ 能够知道 $X_i$ 中的每个数在并集 $X$ 的排序位置。