[百万富翁问题] 同态加密的有趣玩法

[nobody123123]

偶然了解到 [百万富翁问题]

两个百万富翁都想比较到底谁更富有，但是有都不想让别人知道自己有多少钱。在没有可信的第三方的情况下如何进行？

具体可以参考网上的文章，例如https://www.zhihu.com/question/66376147
一个解决办法是使用同态加密来解决保密问题。

基于这个算法能不能做一些好玩的事情呢? 比如: 大家通过这种方式，互相比较工资，在不暴露每个人具体的数额的情况下，得知自己的排名。如果加上自己的行业，职位，工龄等信息，会得到更多有用的统计信息。 整个过程所有参与方（包括服务器）都不会知道每个人具体的数额。

[sillydaddy]

比较工资这个确实很有意思。
假如这个做成一个网站，需要解决的最主要问题是，用户会提交真实的工资信息，这点其实感觉并没有好的办法来保证。

[nobody123123]

@sillydaddy 出发点是：用户想知道自己的排名，只有提交真实数据才能得出正确的统计信息。用加密算法解决隐私问题后，用户更愿意提供真实的数据。

[sillydaddy]

全同态加密理论上可以在服务器上执行任意的程序运算任意的数据，而不需向服务器暴露任何数据。
只不过现在的问题是时间开销和空间开销都很大，目前只有一些特殊的应用可以用。

可以参考这个帖子
https://v2ex.com/t/700927#reply11

[sillydaddy]

@nobody123123 也对，但还是不能保证有多少比例的用户提供真实信息啊。

[lvybupt]

今年的三大密会上关于 MPC 的文章还超过了 30 篇。
这个领域前期有意思，后期几乎是现代密码学最难的部分，没有之一。

[oxogenesis]

门槛太高，推广不太现实

[geelaw]

我对知乎文章里提到的那个方案很怀疑——它可证明安全吗？显然为了正确性我们需要 ax+y 和 bx+y 作为整数小于 n，即没有“溢出”。

看起来并不安全，考虑 Alice 知道 Bob 比她多 1 块钱或者 2 块钱，在多 1 块钱的情况下 A 和 B 有 1/2 的概率奇偶性不同，在多 2 块钱的情况下 A 和 B 的奇偶性一定相同。这样经过一次计算，Alice 就可以得到 Bob 财富的信息。

而且百万富翁问题的第一个、最经典的解法是用乱码电路。当然既然本帖提到了同态加密，那么这个问题（半诚实安全性）可以很容易用带有电路保密性的全同态加密算法解决。

@sillydaddy #1 诚实提供输入的问题无法用密码学技术解决，需要使用机制设计。

[nobody123123]

@geelaw 那边知乎文档里面具体 python 代码的实现我其实不是很明白里面变量`n`的作用。不过尝试了下利用[paillierlib]( https://pypi.org/project/paillierlib/)这个 python 库很容易实现。Alice 当然最终只会知道 a，b 的大小关系，不会知道自己比 Bob 具体多几块钱的（ Alice 肯定知道自己有几块钱）。

[optional]

可以多比几次，，二分法找到答案

[nobody123123]

其实，在我的想法里，整个过程服务器只是负责撮合两个用户进行对比，秘密原文不会离开客户端，所有的加密揭秘在双方的客户端内解决。服务器记录并汇总所有的比较结果，从而给出统计数据。
这里所有的参与者必然都是互相信任的才可以。
如果参与者互不信任，就可能是类似于区块链那样的系统了，玩不动...

[zsxzy]

已经运用到区块链里面, 零知识证明

[nobody123123]

@optional 你说的关键点了。一定不能任意变换自己的数字，进行 N 次比较。否则，通过二分法很快就逼出对方的实际数字了。

[geelaw]

@nobody123123 #8 我在 #7 第二段已经提出了一个（在特定场景下）让 Alice 知道自己比 Bob 多 /少多少钱的方法了，反驳的方式应该是提出那个攻击的错误，或者（更好方式是）提供一个安全证明。

想当然安全不代表真的安全，你怎么知道“Alice 当然最终只会知道 a，b 的大小关系，不会知道自己比 Bob 具体多几块钱”呢？

[nobody123123]

@geelaw sorry，你在#7 中的描述我不是很明白。
你的意义是：如果“Alice 知道 Bob 比她多 1 块钱或者 2 块钱”这个前提下，使用文章中的算法进行比较，可能会泄漏 Blob 的具体数字。 对吗？
仔细验证了下，确实如你说所。不知道尝试修改 ax+y 这个函数能否避免这个问题。本质上这个计算结果除了能够比较出大小，还暴露额外的信息, 算是个缺陷吧。

不过话说回来了，到实际应用中, 如果"Alice 知道 Bob 比她多 1 块钱或者 2 块钱"，既然都知道大小，那也就不用比了。。。

[nobody123123]

@sillydaddy 感谢🙏 https://v2ex.com/t/700927#reply11
这个帖子不错，学习了

[geelaw]

@nobody123123 #14 “既然知道大小，那就不用比了”是天真的想法，说不定 Alice 就是想知道到底是多 1 还是多 2，而 Bob 对此则毫不知情。也可以换一个场景：Alice 知道 Bob 和她的财富差距是 1 或者 2，但是不知道是四种情况的哪一种，那么经过计算，Alice 不但知道了是多还是少，而且还对差距有更多掌握。

安全的方案必须满足：经过计算之后了解的 额外 信息不能超过计算所允许得到的，无论先前已经掌握多少信息。

[nobody123123]

@geelaw 你的意思我 Get 到了。 “经过计算之后了解的 额外 信息不能超过计算所允许得到的，无论先前已经掌握多少信息” 这个说的很好。

[sillydaddy]

@nobody123123
发现了一个问题，假如任何客户端都可以向服务器添加自己的工资，以便获取自己的工资排名，那么，服务器可以伪造 N 个客户端，来获取真实客户端的工资，而无需解密它们。方法就是用这伪造的 N 个客户端作为标尺，比如让 N 个客户端的工资比较均匀地分布在 0 到 100 万。排序后就可以衡量出任一真实客户端的工资。

另一个问题就是，真实客户端可以操纵多个账号，提供多个不同的工资，其中只有一个是自己的真实工资。另外几个是用来扰乱的。如果别的客户端都是诚实的，这个客户仍然可以得到自己工资的真实排名，因为用来扰乱的那几个工资对他来说是可见的，只要把这几个工资从最后的统计结果中减去，就能得到自己想要获知的真实排名。有点像囚徒博弈，一个客户端无论是否加入干扰数据，都不损害他自己获取的排名的准确性，但大家都这么做时，每个人获取的排名都变得不准确了。

[doveyoung]

密码学，真是有趣呀（ dog

[nobody123123]

@sillydaddy 这里必须假设所有参方放必须相互信任，否则实现起来就非常麻烦了。
举一个例子：假设 telegram 说自己使用了端到端加密来进行通信，服务器不会拿到聊天明文。但是普通人是没办法自己动手去证实这个事情的。如果有一天 telegram 客户端被有意或者无意的插入了恶意代码，将消息明文旁路转发一份到某个隐秘的服务器上，其实我也并不知道，也没办法验证。我因为相信 telegram 使用了端到端加密，所以更愿意使用它，但是我却不知道 telegram 有没有忽悠我, 也不知道它会不会有其它方面的安全问题
所以解决这个问题最简单的方式可能是...不去解决🙊, 从产品层面上去限制用户的行为