两富人比谁钱多。如何能实现互相保密但可以比出谁钱多?

两个富人想比较谁的钱多,他们之间可以发送任何信息,但不能告诉对方自己有多少钱。比较苛刻的是,他们也不能说自己大致有多少钱(诸如大于1000小于2000)。请问要如何实现?方法是否有优劣?这种保密的算法或者通信方法应用前景如何?

我的回答

姚期智在1982年提出的百万富翁问题应该是开创了安全多方计算的先河,后面涌现了茫茫多的协议算法,比较常见的是利用同态加密来实现。

举个实际例子,比如Paillier加密算法就具有比较好的同态属性:

\[E(m_1,r_1) \cdot E(m_2,r_2) = E(m_1+m_2,r_1+r_2)\] \[E(m,r)^C=E(m \cdot C,r \cdot C)\]

我们可以用它来设计具体的比富协议(假设 Alice 财富是 $a$ ,Bob的财富是 $b$ ):

第一步:Bob生成两个非常大的随机正整数 $x$ 和 $y$ ,但是并不公开只有他自己知道;

第二步:Alice生成一对属于自己的密钥(公钥是pub,私钥是pri),用公钥加密自己的财富的到 $E(a)$ ,并将它和公钥一起公布出去;

第三步:Bob得到Alice公布出来的数据以后,首先用Alice公钥计算出 $E(b \cdot x+y)$,然后用Paillier算法的同态属性计算出 $E(a \cdot x+y) = E(a)^x \cdot E(y)$,并将这两个结果也公布出去;

第四步:Alice得到Bob公布出来的计算结果以后,用自己的私钥分别反解出 $A = a \cdot x+y 和 B = b \cdot x+y$ 的值。Alice虽然对 $x$ 、 $y$ 和 $b$ 一无所知,但她只要比较 $A$ 和 $B$ 的大小就行了。而对于Bob来说,他对 $A$ 、 $B$ 和 $a$ 也是一无所知,如果他也想要知道相对大小,要么Alice告诉他,要么把角色对换重新执行一遍协议即可。

这个方法有效的前提是Alice和Bob都会诚实地执行协议,关于如何防止他们作弊而使得比较结果是可验证的,可以参考李向阳他们在2013年发表的一篇论文,当然具体细节会比上述协议稍微复杂一些。

这种不泄漏自己信息比较大小的算法有什么实际应用?一个很直观的应该就是在线拍卖,所有的竞价方希望决出一个最高竞价(或者第二竞价)但是并不希望频繁泄漏自己的竞价策略。另一方面来讲,比较大小只是同态加密的一个非常非常小的应用方向,很明显如果拥有全同态的加密系统,我们可以很放心地把数据加密然后交给别人计算,然后把他计算出来的结果解密即可而不用担心原始数据泄露。不过很遗憾Paillier加密系统不具备这种性质,不过处理比富问题刚好够用了。

最后写了段简单的Python程序来模拟了整个过程:

#!/usr/bin/env python

from paillier import *
from primes   import *


# Bob
b = 2333333
x = generate_random(100)
y = generate_random(128)


# Alice
a = 2578466
pri, pub = generate_keypair(512)
E_a = encrypt(pub, a)
print("Alice: pub =", pub)
print("Alice: E(a) =", E_a)


# Bob
E_bxy = encrypt(pub, b*x+y)
E_axy = e_add_const(pub,  \
    e_mul_const(pub, E_a, x), y)
print("Bob: E(b*x+y) =", E_bxy)
print("Bob: E(a*x+y) =", E_axy)


# Alice
bxy = decrypt(pri, pub, E_bxy)
axy = decrypt(pri, pub, E_axy)
print("Alice: b*x+y =", bxy)
print("Alice: a*x+y =", axy)

以下是输出打印(应该很直观了吧):

Alice: pub = <PublicKey: 57260485827495331038137791081238079100193827091391940852359475859586518327943168849210437768592904465951784468822218044573139771391693942549840228088557>
Alice: E(a) = 4968512766090949180669170559957452717494049844479002110445123942551676679906252413711009624735729906635967551926069731416878655716309624313367185335551492246695219172804484937096244634803236873292495605021741681328394185268831677160127700775541140435576607127972386587900675971625862609134341949097306109694
Bob: E(b*x+y) = 78069472270630060916606096600507250169159579661207403128669332538535612717207871265810735387655792138231410905886798136066046955699948551501839777500559977007762158634331881486742617837691582987876994902606739653098544230039086128371956175439177761045082327247819561763324114826997271075910092429003392478
Bob: E(a*x+y) = 104561632080136594066348339301905599982191403947698856626743680045058520250858370819374335554314580722136907382008024868484633580579612028150379242570803004867721472194721685344550543943705587829046277503121661431237459322367517951428419482725455956873466560779025879725945654431808048866844777222317703313
Alice: b*x+y = 25176283170138758568634968198123146770
Alice: a*x+y = 25200844139169272487711888736752166063