姚期智 - 亿万富翁问题

Solution

Mathematical Model

该过程是一个非对称加密。
Alice 有公钥，有私钥，资产 $i$ 亿元；Bob 有公钥，无私钥，资产 $j$ 亿元。

1. Bob 操作

1. 选取一个大数字 $X$，$E(X) = k$，$D(k) = X$。

2. 令 $m = k - j + 1$，将 $m$ 作为密文传输给 Alice。

2. Alice 操作

1. 计算 $m, \ m + 1, \ m + 2, \ \cdots, \ m + 9$，即 $k - j + 1, \ k - j + 2, \ k - j + 3, \ \cdots, k - j + 10$。

2. 解密：令 $y_u = D(k - j + u)$，不难发现 $y_j = D(K) = X$。

3. 求模：令 $z_u = y_u \mod P$，其中 $P$ 是一个较大的质数。

4. 保持 $z_1, z_2, z_3 \cdots, z_i$ 不变，$z_{i + 1}, z_{i + 2}, \cdots z_{10}$ 加 1。并将 $z_1 \sim z_{10}$ 重传给 Bob。

3. Bob 检验

若 $X \mod P = z_j$，则证明 $j \leq i$；若 $X \mod P \neq z_j$，则证明 $j > i$。