王 宁 顾昊旻 郑 彤

1(国网河南省电力公司信息通信公司 河南 郑州 450052)2(安徽继远软件有限公司基础运维分部 安徽 合肥 230088)

0 引 言

安全多方计算研究一组互不信任的参与方之间保护隐私的合作计算问题，最早由图灵奖得主姚期智先生于1982年提出[1]。文献[1]构造了这样一个问题(简称百万富翁问题)：两个百万富翁Alice和Bob在街头相遇，其中Alice拥有财富a，Bob拥有财富b。他们希望在不泄露自身财富信息的前提下比较出他们谁更富有，即两方秘密比较a和b的大小。此后，出现了很多解决百万富翁问题的安全方案[2-3]。

安全多方排序问题是百万富翁问题(两方秘密比较)的自然推广：假定有n个参与者P1,P2,…,Pn分别拥有隐私秘密x1,x2,…,xn(令X={x1,x2,…,xn})，他们希望在不泄露各自隐私秘密的前提下得到各自秘密在有序序列X′中的位置p(xi)，其中X′是X中n个秘密按从小到大排序的序列。排序问题是计算机科学领域最为重要并得到广泛研究的核心问题之一，它是求解许多复杂问题的基本构成单元。同样地，安全多方排序在保护用户隐私的多方协作计算领域有着很重要的应用价值，是很多复杂协议的基础协议。例如，保护用户隐私的电子投标和拍卖[4]、保护用户隐私的在线电子交易[5]、保密数据库查询[6]等。

目前，国外对安全多方排序问题的研究成果并不多。在为数不多的研究成果中，多数作者采用了基于比较的排序思想，因而至少需要Ω(nlogn)次两方秘密比较。例如，2011年，文献[7]基于排序网络提出了一个安全多方排序协议。……