V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
nobody123123
V2EX  ›  奇思妙想

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

  •  
  •   nobody123123 · 2020-10-13 18:30:06 +08:00 · 3421 次点击
    这是一个创建于 1263 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    21 条回复    2020-10-16 11:16:22 +08:00
    sillydaddy
        1
    sillydaddy  
       2020-10-13 19:10:34 +08:00 via Android   ❤️ 1
    比较工资这个确实很有意思。
    假如这个做成一个网站,需要解决的最主要问题是,用户会提交真实的工资信息,这点其实感觉并没有好的办法来保证。
    nobody123123
        2
    nobody123123  
    OP
       2020-10-13 19:25:12 +08:00 via iPhone
    @sillydaddy 出发点是:用户想知道自己的排名,只有提交真实数据才能得出正确的统计信息。用加密算法解决隐私问题后,用户更愿意提供真实的数据。
    sillydaddy
        3
    sillydaddy  
       2020-10-13 19:27:01 +08:00 via Android   ❤️ 1
    全同态加密理论上可以在服务器上执行任意的程序运算任意的数据,而不需向服务器暴露任何数据。
    只不过现在的问题是时间开销和空间开销都很大,目前只有一些特殊的应用可以用。

    可以参考这个帖子
    https://v2ex.com/t/700927#reply11
    sillydaddy
        4
    sillydaddy  
       2020-10-13 19:28:15 +08:00 via Android
    @nobody123123 也对,但还是不能保证有多少比例的用户提供真实信息啊。
    lvybupt
        5
    lvybupt  
       2020-10-13 19:34:30 +08:00
    今年的三大密会上关于 MPC 的文章还超过了 30 篇。
    这个领域前期有意思,后期几乎是现代密码学最难的部分,没有之一。
    oxogenesis
        6
    oxogenesis  
       2020-10-13 19:42:57 +08:00
    门槛太高,推广不太现实
    geelaw
        7
    geelaw  
       2020-10-13 20:12:27 +08:00 via iPhone
    我对知乎文章里提到的那个方案很怀疑——它可证明安全吗?显然为了正确性我们需要 ax+y 和 bx+y 作为整数小于 n,即没有“溢出”。

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

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

    @sillydaddy #1 诚实提供输入的问题无法用密码学技术解决,需要使用机制设计。
    nobody123123
        8
    nobody123123  
    OP
       2020-10-13 21:56:20 +08:00
    @geelaw 那边知乎文档里面具体 python 代码的实现我其实不是很明白里面变量`n`的作用。不过尝试了下利用[paillierlib]( https://pypi.org/project/paillierlib/)这个 python 库很容易实现。Alice 当然最终只会知道 a,b 的大小关系,不会知道自己比 Bob 具体多几块钱的( Alice 肯定知道自己有几块钱)。
    optional
        9
    optional  
       2020-10-13 22:01:11 +08:00
    可以多比几次,,二分法找到答案
    nobody123123
        10
    nobody123123  
    OP
       2020-10-13 22:12:15 +08:00
    其实,在我的想法里,整个过程服务器只是负责撮合两个用户进行对比,秘密原文不会离开客户端,所有的加密揭秘在双方的客户端内解决。服务器记录并汇总所有的比较结果,从而给出统计数据。
    这里所有的参与者必然都是互相信任的才可以。
    如果参与者互不信任,就可能是类似于区块链那样的系统了,玩不动...
    zsxzy
        11
    zsxzy  
       2020-10-13 22:12:21 +08:00
    已经运用到区块链里面, 零知识证明
    nobody123123
        12
    nobody123123  
    OP
       2020-10-13 22:14:32 +08:00
    @optional 你说的关键点了。一定不能任意变换自己的数字,进行 N 次比较。否则,通过二分法很快就逼出对方的实际数字了。
    geelaw
        13
    geelaw  
       2020-10-13 22:50:36 +08:00
    @nobody123123 #8 我在 #7 第二段已经提出了一个(在特定场景下)让 Alice 知道自己比 Bob 多 /少多少钱的方法了,反驳的方式应该是提出那个攻击的错误,或者(更好方式是)提供一个安全证明。

    想当然安全不代表真的安全,你怎么知道“Alice 当然最终只会知道 a,b 的大小关系,不会知道自己比 Bob 具体多几块钱”呢?
    nobody123123
        14
    nobody123123  
    OP
       2020-10-13 23:22:41 +08:00
    @geelaw sorry,你在#7 中的描述我不是很明白。
    你的意义是:如果“Alice 知道 Bob 比她多 1 块钱或者 2 块钱”这个前提下,使用文章中的算法进行比较,可能会泄漏 Blob 的具体数字。 对吗?
    仔细验证了下,确实如你说所。不知道尝试修改 ax+y 这个函数能否避免这个问题。本质上这个计算结果除了能够比较出大小,还暴露额外的信息, 算是个缺陷吧。

    不过话说回来了,到实际应用中, 如果"Alice 知道 Bob 比她多 1 块钱或者 2 块钱",既然都知道大小,那也就不用比了。。。
    nobody123123
        15
    nobody123123  
    OP
       2020-10-13 23:25:17 +08:00
    @sillydaddy 感谢🙏 https://v2ex.com/t/700927#reply11
    这个帖子不错,学习了
    geelaw
        16
    geelaw  
       2020-10-13 23:28:16 +08:00
    @nobody123123 #14 “既然知道大小,那就不用比了”是天真的想法,说不定 Alice 就是想知道到底是多 1 还是多 2,而 Bob 对此则毫不知情。也可以换一个场景:Alice 知道 Bob 和她的财富差距是 1 或者 2,但是不知道是四种情况的哪一种,那么经过计算,Alice 不但知道了是多还是少,而且还对差距有更多掌握。

    安全的方案必须满足:经过计算之后了解的 额外 信息不能超过计算所允许得到的,无论先前已经掌握多少信息。
    nobody123123
        17
    nobody123123  
    OP
       2020-10-13 23:38:57 +08:00
    @geelaw 你的意思我 Get 到了。 “经过计算之后了解的 额外 信息不能超过计算所允许得到的,无论先前已经掌握多少信息” 这个说的很好。
    sillydaddy
        18
    sillydaddy  
       2020-10-14 09:59:47 +08:00 via Android
    @nobody123123
    发现了一个问题,假如任何客户端都可以向服务器添加自己的工资,以便获取自己的工资排名,那么,服务器可以伪造 N 个客户端,来获取真实客户端的工资,而无需解密它们。方法就是用这伪造的 N 个客户端作为标尺,比如让 N 个客户端的工资比较均匀地分布在 0 到 100 万。排序后就可以衡量出任一真实客户端的工资。

    另一个问题就是,真实客户端可以操纵多个账号,提供多个不同的工资,其中只有一个是自己的真实工资。另外几个是用来扰乱的。如果别的客户端都是诚实的,这个客户仍然可以得到自己工资的真实排名,因为用来扰乱的那几个工资对他来说是可见的,只要把这几个工资从最后的统计结果中减去,就能得到自己想要获知的真实排名。有点像囚徒博弈,一个客户端无论是否加入干扰数据,都不损害他自己获取的排名的准确性,但大家都这么做时,每个人获取的排名都变得不准确了。
    doveyoung
        19
    doveyoung  
       2020-10-14 17:32:53 +08:00
    密码学,真是有趣呀( dog
    nobody123123
        20
    nobody123123  
    OP
       2020-10-14 19:17:39 +08:00
    @sillydaddy 这里必须假设所有参方放必须相互信任,否则实现起来就非常麻烦了。
    举一个例子:假设 telegram 说自己使用了端到端加密来进行通信,服务器不会拿到聊天明文。但是普通人是没办法自己动手去证实这个事情的。如果有一天 telegram 客户端被有意或者无意的插入了恶意代码,将消息明文旁路转发一份到某个隐秘的服务器上,其实我也并不知道,也没办法验证。我因为相信 telegram 使用了端到端加密,所以更愿意使用它,但是我却不知道 telegram 有没有忽悠我, 也不知道它会不会有其它方面的安全问题
    所以解决这个问题最简单的方式可能是...不去解决🙊, 从产品层面上去限制用户的行为
    no1xsyzy
        21
    no1xsyzy  
       2020-10-16 11:16:22 +08:00
    差分隐私的问题不能靠同态加密解决。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2685 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 15:13 · PVG 23:13 · LAX 08:13 · JFK 11:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.