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

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

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

A A A将盒子上锁，并按 1 1 1到 10 10 10的顺序发交给 B B B。

B B B选择自己财产的数字对应的箱子，即第 9 9 9个盒子，然后交个 A A A。

由 A A A打开盒子，共同判定结果：蓝球，因此 B B B更富有。

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

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

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

step1： A A A和 B B B共同协商一种公钥加密体制( E E E为加密算法， D D D为解密算法)。

step2： A A A随机选择一个大随机数 x x x,用B的公钥加密得 E ( x ) E(x) E(x)，然后将 E ( x ) − i E(x)-i E(x)−i发送给 B B B。

step3： B B B首先计算 N N N个数 y u = D ( E ( x ) − i + u ) , u = 1 , 2 , . . . , N y_u=D(E(x)-i+u),u=1,2,...,N yu​=D(E(x)−i+u),u=1,2,...,N然后随机选择大素数 p p p，再计算 N N N个数 z u ≡ y u   m o d   p , u = 1 , 2 , … , N z_u \equiv y_u \bmod p,u=1,2,…,N zu​≡yu​modp,u=1,2,…,N接着验证对于所有的 0 ≤ a ≠ b ≤ N − 1 0 \le a \neq b \le N-1 0≤a=b≤N−1是否都满足 ∥ z a − z b ∣ ≥ 2 \|z_a-z_b|≥2 ∥za​−zb​∣≥2，若不满足，则重新选择大素数 p p p重新验证。 最后， B B B将 p p p及以下的 N N N个数串发送给 A A A: z 1 , z 2 , . . . , z j , z j + 1 + 1 , z j + 2 + 1 , … , z N + 1 z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1 z1​,z2​,...,zj​,zj+1​+1,zj+2​+1,…,zN​+1.- step4：设 A A A收到 N N N个数串的第 i i i个数 z i ≡ x   m o d   p z_i \equiv x \bmod p zi​≡xmodp，则结论是 i ≤ j i \le j i≤j；否 i ≥ j i \ge j i≥j。

step5： A A A 将结果告诉 B B B。

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

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

(2)要求 z n z_n zn​中的任何两个数 z a , z b z_a,z_b za​,zb​满足 ∥ z a − z b ∣ ≥ 2 \|z_a-z_b|≥2 ∥za​−zb​∣≥2是为了保证 B B B发送给 A A A的 N N N个数的数列 z 1 , z 2 , . . . , z j , z j + 1 + 1 , z j + 2 + 1 , … , z N + 1 z_1,z_2,...,z_j,z_{j+1}+1,z_{j+2}+1,…,z_N+1 z1​,z2​,...,zj​,zj+1​+1,zj+2​+1,…,zN​+1中任意两个数不同,一般称这样的数列为“好数列”。因为若数列中存在两个数 z m = z n ， m < n z_m=z_n，m