作者：好个盖碗茶
链接：https://www.zhihu.com/question/66376147/answer/246278043
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

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

我们可以用它来设计具体的比富协议(假设 Alice 财富是 ，Bob的财富是 )：

第一步：Bob生成两个非常大的随机正整数 和 ，但是并不公开只有他自己知道；

第二步：Alice生成一对属于自己的密钥(公钥是pub，私钥是pri)，用公钥加密自己的财富的到 ，并将它和公钥一起公布出去；

第三步：Bob得到Alice公布出来的数据以后，首先用Alice公钥计算出，然后用Paillier算法的同态属性计算出，并将这两个结果也公布出去；

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

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

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

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

import random
import paillier.keygen as keygen
import paillier.crypto as crypto

# Alice生成自己的公私钥(足够长)
pk, sk = keygen.generate_keys()


# 比较Alice的财富a和Bob的财富b
def compare(a, b):
    # Bob生成两个随机数x和y
    x = random.getrandbits(100)
    y = random.getrandbits(128)

    # Alice公布自己公钥pk
    print("Alice: pk =", pk)

    # Alice计算a的密文并公布
    e_a = crypto.encrypt(pk, a)
    print("Alice: E(a) =", e_a)

    # Bob计算b*x+y的密文并公布
    n, _ = pk
    e_bxy = crypto.encrypt(pk, b * x + y)
    print("Bob: E(b*x+y) =", e_bxy)

    # Bob计算a*x+y的密文并公布
    e_axy = crypto.secure_addition(
        crypto.scalar_multiplication(e_a, x, n),
        crypto.encrypt(pk, y),
        n,
    )
    print("Bob: E(a*x+y) =", e_axy)

    # Alice根据密文反解出b*x+y
    bxy = crypto.decrypt(pk, sk, e_bxy)

    # Alice根据密文反解出a*x+y
    axy = crypto.decrypt(pk, sk, e_axy)

    # Alice公布最终的大小结果
    if axy > bxy:
        print("winner: Alice")
    elif bxy > axy:
        print("winner: Bob")
    else:
        print("tie")


if __name__ == '__main__':
    alice_a = 2578466
    bob_b = 2333333
    compare(alice_a, bob_b)

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

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