Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？ 第1页

高能预警，一步到位

@将离，一个心理学专业的影视博主，邀请一个生物实验室的博士回答密码学问题……巧了，虽然现在的我只破译生命的密码，但当年拿命修过密码学+数论+抽代。希望看完这个答案大家会对密码学产生浓厚的兴趣！如果还没有，可以看经典大片《模仿游戏》和原著 The Code Book 入坑，你一定会冒着生命危险选这门课。

更新：感谢密码学博士 @刘天任 点评~已给出简化版并将原答案作为公平升级版。愿意点开这个回答的朋友应该也会对他和他的各种回答感兴趣。

这问题其实就是 Tiercé problem 又称 socialist millionaire problem，中文硬翻叫社会主义百万富翁问题，是姚氏百万富翁问题的变种，0-9是简化，其实多少都可以，默认没有第三方存在。2001年的论文 A Fair and Efficient Solution to the Socialist Millionaires' Problem 针对该问题给出了适用于两个数都小的情况下也适用的公平高效的解决方案^[1]，我不完全跟随该论文，简单写一下具体协议，再通俗地讲一下为什么没有泄露自己的数。学过数论和群论的朋友读起来会比较轻松。

0-9 十个数全是整数，只要是整数都好说（其实不是也行，反正计算机里都是 bits）。首先一开始 Alice 和 Bob 共同都知道的信息是，其中 为质数， 是整数模 乘法群， 就是质数 阶群，，，，，是 的生成元。为什么这么取值最后讲。当然 Alice 知道自己的数字是 ，Bob 知道自己的数字是 ，开始：

第一步，Alice 随机从 取数字 ，算出 ，同样，Bob 算出 ，然后互相交换 和 得到新的共有知识

第二步，Alice 取 算出 ，同样 Bob 这边 ，得到 ，然后交换 和 得到新共有知识 和

第三步，Alice 算出 ，Bob 算出 ，交换，双方又获得新知识 并检查 是否成立，如果成立则 ，否则

就这？为啥？

因为只有 的时候 ，毕竟 都是不会为 的。

现在有同学要问了， 为什么取这么大， 个 bit 是怎么来的，Fabrice Boudot, Berry Schoenmakers 和 Jacques Traore 在2001年取的 ，是因为计算机算力也就只能做 次运算，如果设 ，是计算上不可能破解的。现在2022了但应该是不用换更大数字的，而且这个数取多少其实不是重点。

仔细观察的同学会发现，所有共享信息里都可以用 的形式表示，而 是秘密，想破解出 就等同于解离散对数，可以当作不可能解出。所有有关 和 的共享信息都长这样： ，而 是随机秘密，因式分解等于无解，所以就算 和 只取 0-9 也是不会破解的。

完毕！

PS：如果硬要有一个第三方，第三方可以站那看着 Alice 和 Bob 玩~

如果 Alice 人品不行，想在第三步先骗 Bob 把 给自己后逃之夭夭怎么办？

可以稍作改动：

第二步，Alice 取 算出 ，同样 Bob 这边 ，得到 ，然后交换 和 得到新共有知识 和

第三步，Alice 算出 ，Bob 算出 ，交换，双方又获得新知识

第四步，Alice 和 Bob 一点一点逐 bit 公开 和 ，各自检查是否 ，如果成立则 ，否则

这样一来一方想跑的时候也只比另一方多了解了一个 bit.

书本推荐 Katz & Lindell 的 Introduction to Modern Cryptography，建议把抽象代数/数论基础打好之余把可计算性和计算复杂性思维养好。如果有选修密码学来抄答案的，请引用文中论文以免被开除 : )

参考

1. ^A Fair and Efficient Solution to the Socialist Millionaires' Problem https://www.win.tue.nl/~berry/papers/dam.pdf

无需第三方，可以GC（一个等式电路），同态（Bob公钥加密b后发送给Alice，Alice做减法并盲化后发给Bob，Bob解密即可。结果为零说明相等，否则不等）或者秘密共享上的比较协议

A的数字为a，B的数字为b。

那么A在第a天到操场坐一天，B在第b天到操场坐一天。并约定双方其他日子都不去操场。

如果需要前提“对方想尽办法知道自己的数字而自己需要避免”的话，把操场改成无法设置隐身的社交软件即可。