张兴兰，郑炜



基于博弈论的安全多方计算的研究

张兴兰，郑炜

（北京工业大学信息学部，北京 100124）

在经典的百万富翁协定中，参与者其中之一获取到财产大小的结论后，有可能不告诉另外一个参与者，也可以不遵守这个协议，结合博弈论可以避免这个问题，一个参与者一定会选择做出对自己有利的决定，因此，可以设计一个协议，遵循这个协议的参与者获得的利益大于背离这个协议的利益。目前，基于博弈论的问题计算效率较低，该协议通过引入一个二叉树大大提高了计算效率。

博弈论；百万富翁问题；安全多方计算；排序二叉树

1 引言

多方安全计算指在一个参与者都不信赖彼此的环境中，每位参与者通过网络共同完成各种计算任务的同时又不会泄露自己的数据[1]。这里面的安全指既能够通过计算得到正确的结果，又不会让别的参与者得知输入的各种隐私信息。多方安全计算在生活中随处可见，尤其是在现在这个互联网时代，如在网上的拍卖会，网络上的投票系统[2]等。

在文献[3]中，Yao首先提出了百万富翁比较财产多少的问题，在2个人不告诉对方财产数额的前提下，比较出谁更有钱。在文献[4,5]中，Goldreich等设计出了一个通用性高的多方安全计算协议。在文献[6]中，冯登国等设计了一个有半诚实第三方的两方安全比较协议。在文献[7]中，李顺东等运用不经意传输协议，设计出了一种有效的两方安全比较协议。在文献[8,9]中，作者利用半诚实的模型，分别对数据库中的隐私数据和网络空间中认证的策略进行了深入的理论研究。……