我们首先以“百万富翁”问题为例来说明安全多方计算协议。百万富翁问题是姚期智先生在1982年提出的第一个安全双方计算问题。问题可以描述为：两个百万富翁街头邂逅，都想知道到底谁更富有，但是又都不想让别人知道自己有多少钱。在没有可信的第三方的情况下如何进行呢？为了便于说明，不妨假设问题是Alice知道一个值a，Bob知道一个值b，他们想确定a是否小于b，而且Alice得不到b的任何信息，Bob也得不到a的任何信息。我们可以采用下面这个协议。

假设i和j的取值范围是从1到100，Bob有一个公开密钥和一个私人密钥。

（1）Alice选择一个大随机数x，并用Bob的公开密钥加密：c=EB（x）。

（2）Alice计算c-i，并将结果发送给Bob。

（3）Bob计算下面的100个数：yu=DB（c-i+u），1≤u≤100，DB是使用Bob的私人密钥的解密算法。

他选择一个大的随机数p（p的大小应比x稍小一点，Bob不知道x，但Alice能容易地告诉他x的大小），然后计算下面100个数：

然后他对所有u≠v验证|zu-zv|≥2，并对所有的u验证0≤zu≤p-1，如果不成立，Bob就选择另一个素数并重复试验。

（4）Bob将以下数列发送给Alice(www.daowen.com)

（5）Alice检查这个数列中的第i个数是否同余x模p。如果同余，她得出的结论是i≤j；如果不同余，她得出的结论是i＞j。

（6）Alice把这个结论告诉Bob。

Bob在第（3）步中所作的验证完全是为了保证第（4）步产生的数列中没有任何一个数出现两次，否则，如果za=zb，Alice就将知道ai≤j＜b。

该协议有一个缺点：Alice在Bob之前就熟悉了计算的结果。没有什么能阻止她完成该协议直到第（5）步，然后在第（6）步拒绝告诉Bob结果，甚至在第（6）步有可能对Bob撒谎。

当然，这个协议不能防止主动欺骗者。没有办法防止Alice（或Bob）谎报他们的值。如果Bob是一个隐蔽执行这个协议的计算机程序，那么Alice通过反复执行这个协议可以知道他的值。Alice可以在执行这个协议时，指定她的值为60。在得知她的值大时，她可以将她的值指定为30，再次执行这个协议。在得知Bob要大一些之后，她可以称她的值为45再次执行这个协议，依此继续下去，直到Alice发现Bob的值达到她所希望的精确度。

假设参与者不主动欺骗，很容易把这个协议推广到多个参与者。任何数量的人通过一系列诚实应用这个协议可以发现他们的值的顺序，并且没有一个参与者能够得知另一个参与者的值。