基于量子求和的安全多方量子排序协议

王蕊聪,冯雁

(1北京电子科技学院网络空间安全系,北京 100070;2西安电子科技大学,陕西 西安 710126;3中国科学技术大学,安徽 合肥 230026)

0 引言

在安全多方计算执行的过程中,计算可能发生在互不信任甚至互相竞争的多方中,安全多方排序问题是信息保密的安全多方计算的核心问题之一,其主要思想是:假设有n名参与者P1,P2,P3,···,Pn,每个参与者各自拥有一个秘密数值x1,x2,x3,···,xn,他们希望在没有可信第三方的情况下,能够设计出某种计算方式,让所有参与者参与排序,每个参与者可以安全获得自己秘密数值的排名,且排名在各参与者之间也同样保密的一种安全方案。

目前,国内外围绕安全多方排序开展了很多研究,取得了不少研究成果。关于传统多方排序[1−3],大多数采用了基于比较的排序思想,即文献[4]中对百万富翁问题的自然推广,人们针对这个问题,利用传统的密码算法设计了各种能够提高排序效率的协议,但却至少需要nlogn次两方秘密比较,计算开销大。文献[5]提出了随机化的安全希尔排序,虽然以较高概率成功排序,但该协议需要执行O(log2n)轮,通信和计算开销较大。也有基于经典密码学的同态加密[6]体制的保密排序方案,以及基于大数分解NP问题的RSA密码体制[7]设计的排序方案,这些方案的安全性主要取决于计算机计算能力的强弱,即随着攻击者计算能力的增强,这些方案的安全性也会降低。与基于量子的安全多方排序相比,传统多方排序方案都存着效率不高或安全性保障不强等问题。……