2.5.1 百万富翁问题

安全多方计算能够在无可信第三方的辅助下，既保证各方的输入数据均不泄露，又可以使用各方的输入数据完成预期的协同计算。也就是说，参与计算的各方对自己的数据始终拥有控制权，只需在各个参与方之间公开计算逻辑，即可得到相应的计算结果。安全多方计算是如何实现这种效果的呢？在此，我们使用百万富翁问题来简述安全多方计算的实现方法和挑战。

图灵奖获得者姚期智院士于1982年提出了安全多方计算这个概念，并设计了百万富翁问题来说明安全多方计算的目标。百万富翁问题的描述非常简单，即两个百万富翁想比较谁更富有，但都不想泄露自己具体的财富值。解决该问题最自然的方法是找到一个可信第三方对二者的财富进行比较，然后公布结果，但在实际场景中很难找到完全可信的第三方，而安全多方计算便提供了无须可信第三方的解决方案。接下来，我们描述一个简单的解决方案。

假设两个富翁A和B的财富值分别为f_A，f_B，均为1～9的整数。9个整数分别对应100万，200万，…，900万元。富翁A可按照自己的财富值在编号分别为1～9的9个盒子内放入水果，并在上锁后发送给富翁B，其中每把锁的钥匙均相同，并由富翁A自己保存。若盒子编号i＜f_A，则放入一个苹果；若盒子编号i=f_A，则放入一个橙子；若盒子编号i＞f_A，则放入一个香蕉。如果f_A=5，那么9个盒子中的水果如图2-6所示。

图2-6 富翁A发送给富翁B的9个盒子

富翁B在收到富翁A的9个盒子之后，按照自己的财富值选取其中编号为i=f_B的盒子，并按照协议销毁其他几个盒子。待其他盒子被销毁之后，富翁A将钥匙发送给富翁B。富翁B打开盒子之后，若盒子内为苹果，则其财富值小于富翁A；若盒子内为橙子，则其财富值等于富翁A；若盒子内为香蕉，则其财富值大于富翁A。

假设f_B=7，则富翁B获得编号为7的盒子，待其他盒子被销毁之后，富翁A将钥匙发送给富翁B，富翁B打开盒子发现其中的水果为香蕉，便可得出结论：富翁B的财富值大于富翁A的财富值。

以上便是百万富翁问题的解决方法之一，这个简单的协议建立在双方都是诚实或者半诚实的参与方的前提下，双方不会恶意地输入错误的财富值扰乱协议的正确执行。也就是说，我们可以保证富翁B不会选择错误的盒子或者将错误的比较结果返回给富翁A，但是我们却无法保证富翁B能够克制自己的好奇心，如实地销毁其他盒子。因为即使富翁B不销毁其他盒子，也可以保证协议正常执行，完全符合一个半诚实参与方的要求。因此，在实际应用中，双方通常使用密码协议实现这些理想的限制条件，即使面对半诚实参与方，也可以确保隐私不会泄露。比如，密码学中的不经意传输协议，便可以保证在以上场景中富翁B只能从富翁A的发送内容中获取其中一个盒子，而不能获得其他盒子的相关信息；同时，富翁A也无从得知富翁B所选取的具体是哪个编号的盒子。

安全多方计算的本质就是综合使用众多功能不同的密码协议，达到多方之间安全地得到约定函数的计算结果。接下来，我们介绍一下在安全多方计算中常用的密码协议及其功能。