王蕊聪,冯雁

(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]设计的排序方案,这些方案的安全性主要取决于计算机计算能力的强弱,即随着攻击者计算能力的增强,这些方案的安全性也会降低。与基于量子的安全多方排序相比,传统多方排序方案都存着效率不高或安全性保障不强等问题。

量子密码与经典密码学对应的许多方面也得到了相应的研究,如量子密钥分配协议[8−11]、量子秘密共享协议[12−14]、量子多方计算协议[15−18]等。而关于量子化的排序问题,文献[19]较早提出了利用形变量子化方法进行研究,推导出排序相关分布函数的一般方法,但只是从理论上分析了利用量子排序的可能性;文献[20]设计了基于量子隐式模n+1加法的保密排序协议,但由于用到了特殊滤光器以避免不可见光子进入操作系统,设备复杂度高,实际应用实现难度大。

本文受到文献[21]中关于向量编码,以及文献[22]中基于量子傅里叶变换的安全多方量子求和[23,24]的启示,将向量编码与安全多方量子求和方法结合起来,提出了一个新的安全多方量子排序协议,该协议简单、安全且效率较高。

1 预备知识

1.1 安全性定义

图1 安全性定义图Fig.1 Diagram of security definition

1.2 安全多方量子求和

本方案用量子傅里叶变换方法进行多方安全求和,以下为对该量子傅里叶变换的定义。对未知态|x〉进行傅里叶变换,定义为[22]

对态|y〉进行傅里叶逆变换,定义为[22]

且存在右边定义[22]

基于态|y〉进行傅里叶逆变换推导,可得

在安全多方求和计算过程中每个参与者对自己收到的中间数据需要进行一个Cj操作,Cj操作符定义为

(6)式中的下标t代表该粒子发送到量子信道中,|j〉t表示参与者从发起求和的发起者那里接受到的辅助量子态,用以辅助求和计算。|x〉i即为算符U一个特征值为exp(2πixi/N)的特征向量。

2 安全多方量子排序协议

假设有N个富翁P1、P2、P3、···、Pn,每个富翁Pi的资产为si(其中s1≠s2≠s3···≠sn),每个富翁都想安全地知道自己的资产在所有富翁资产中的排名,又不想向其他富翁泄漏自己的资产,借鉴向量编码和安全多方量子求和的思想,将排序问题转化为求和问题,所有参与者根据向量编码规则执行n次多方求和协议,从而确定各自的秘密在整个序列中的位置,达到保密计算的效果。

所提出协议执行过程如下:

2.1 参与者准备阶段

1)协议由n个参与者P1、P2、P3、···、Pn(半诚实)和一个第三方P0(半诚实)组成,每个参与者拥有各自的秘密si,且si∈ {1,2,···,n}。

2)P1、P2、P3、···、Pn各自拥有秘密si∈{1,2,···,n},每个参与者将各自的秘密数值si用一个长度为N的向量表示为Vi=(xi1,xi2,···,xin),其中向量的编码规则为如果1≤j

3)首先发起人P0准备一个m-bit长的随机的基态|x0〉h,其中m=log2N(其中N为上述的向量长度)且|x0〉h是P0的私有态,然后P0对|x0〉h应用量子傅里叶变换得到

4)P0再准备另外一个m-bit的辅助态 |0〉t,并对 |φ1〉|0〉t执行m个 CNOT 门,得到

很显然|φ2〉是个纠缠态,下标h代表着该粒子是用户保留,而下标t代表该粒子发送到量子信道中。

5)每个参与者Pi都根据自己的向量准备n个私有粒子态 |x1〉i,|x2〉i,|x3〉i,···,|xn〉i。

2.2 协议操作阶段

1)P0将计算得到的m-bit粒子(辅助量子态|j〉t)通过默认量子信道发送给P1。

2)P1接收到辅助量子态|j〉t,首先准备自己的私有粒子态|x1〉1,然后对|j〉t|x1〉1应用一个操作符Cj,其中|x1〉1即为U的一个特征值为exp(2πix1/N)的特征向量,随即对整个P0和P1的复合量子系统进行一个Cj操作[(6)、(7)式],得到

3)P1通过量子信道传送辅助态|j〉t给P2,将手中的|x1〉1保留。P2执行与P1类似的过程,操作完后同样通过量子信道传送辅助态|j〉t给P1。之后的每个用户均执行该过程,如果每位用户均诚实执行操作过程,会得到

4)最后,Pn发送辅助量子态|j〉t给P0,P0对其应用m重CNOT门,得到结果

至此,协议参与者进行的操作阶段已经完成。

2.3 测量公布结果阶段

1)P0在适当测量基上测量第二个m-bit位的粒子(|0〉t),如果测量的结果均为|0〉,则继续下一步,否则认为可能存在第三方攻击者窃取并修改了中间数据,立即结束本次交互。

4)P0将该数字序列公布,该序列即为si的由小至大的升序排序序列,各参与者寻找与si相等的序列号,该序列号对应的数值即为各参与者的排名。

理论上,该方案适用于整数N确定后,任意不大于N的参与者,均可使用该方案获得参与者秘密数据在所有参与者数据中的排名。

3 实验验证

使用量子计算云平台IBM Q Experience上的模拟器对本协议核心量子求和部分的正确性进行验证,即将量子计算过程转化为量子可逆逻辑电路[26,27],在模拟器上设计出实验电路图,根据实验结果确定本协议执行的正确性。

3.1 实验量子电路图

基于文献[28],验证重点是关于量子傅里叶变换理论计算到逻辑电路的实现,量子傅里叶变换即作用在空间C2n上的离散傅里叶变换,其把一组标准正交基{|x〉}用另一组标准正交基{|y〉}表示:Y=UX。此处U即为量子傅里叶变换的核心操作,即作用在Hilbert空间中任意矢量上的变换矩阵UQFT,该矩阵可拆分为一系列逻辑门。一个量子比特的量子傅里叶变换就是单个H门操作,多量子位态空间上的傅里叶变换就是对H门的推广。将任意量子态制备成叠加态,从而进行酉变换完成指数级加速。根据方案中的量子多方求和方法设计量子电路,完成关于安全多方量子排序的验证。

验证:当参与者数目m=4,参与者拥有私密数据1≤n<8,即N=7,假设有参与者P1、P2、P3、P4,P1所拥有秘密数值是6,P2是5,P3是3,P4是7。实验电路如图2～4所示,其中q[6]、q[7]、q[10]、q[11]分别表示参与者P1、P2、P3、P4,q[3]、q[4]、q[5]则为辅助量子比特,第三方测量位P0用q[0]、q[1]、q[2]表示。

1)P1、P2、P3、P4各个用户将各自的秘密用一个长度为N的向量表示,其生成的二维向量分别为:V1=(0,0,0,0,0,1,1)、V2=(0,0,0,0,1,1,1)、V3=(0,0,1,1,1,1,1)、V4=(0,0,0,0,0,0,1)。由此可知,需要进行7次求和计算,并公布计算结果,方可得出4个参与者的排名。

2)P0开始初始化,进行傅里叶变换并用CNOT门添加辅助量子进行辅助检测,电路图如图2所示。

3)参与者依次通过Cj(这里使用CNOT门和Toffoli门分割量子态)向下复合,并将结果传回给P0。此处以参与者输入手中拥有的数字1、1、1、0为例,电路图如图3所示。

4)P0通过执行CNOT门变换及傅里叶逆变换,并最终对q[0]、q[1]、q[2]进行测量并收集结果,电路图如图4所示。

图2 量子傅里叶变换和CNOT门初始化Fig.2 Quantum Fourier transform and initialization of CNOT gate circuit

图3 实验电路图Fig.3 Diagram of experimental circuit

图4 傅里叶逆变换和测量电路Fig.4 Inverse Fourier transform and measurement circuit

图5 实验结果Fig.5 Experimental results

3.2 实验结果分析

分别改变参与者输入为 0、0、0、0,0、0、1、0,0、1、1、0,1、1、1、0以及 1、1、1、1得到计算结果,并绘制结果如图6,其中横坐标代表的二进制编码表示的是依次按列调用排序协议得到的统计结果,将二进制编码转化成十进制即为排名信息分布,纵坐标代表计算的每一列,例如纵坐标5表示第5列计算结果对应010(十进制数为2)。

至此P0只需将该数据公布,各参与者把自己的数字当做编号,对照查看自己的排名(由小至大)。例如参与者P1秘密数字为6,查看纵坐标6对应横坐标排名为3,所以根据参与者P1、P2、P3、P4的秘密数字为6、5、3、7,其所得到的排名分别为3、2、1、4。

图6 计算结果分布Fig.6 Distribution of calculation results

4 安全性分析

4.1 内部参与者攻击

由协议可知,P1无法得到关于P0私有秘密s1的任何信息,因为P0只向P1发送了辅助量子比特|j〉t,其中没有任何有用信息,现在对P1和P2进行分析,分两种情况:一种是参与者对第三方发送过程的中间数据进行攻击,一种是参与者对其他参与者进行攻击。

1)P1测量辅助量子比特|j〉t,显然他可以以相同概率1/N得到|j〉(j∈{0,1,···,N−1}),然而测量结果j与P0手中的纠缠态没有关系,也无法推导出更多数据,因此这样的攻击无效。

2)在将U操作算子应用于辅助比特|j〉t后,P2再次测量它。P2知道P1的秘密状态|x1〉已经进化成与|j〉t相同的状态。基于量子傅里叶变换的辅助态|j〉t,他可以在辅助态|j〉t上执行量子傅里叶逆变换,期望提取|x1〉。其攻击描述可表示为

通过上述推导,如果P2测量辅助状态,他会以等概率1/N得到|l〉t(l∈{0,1,···,N−1})。这意味着P2无法获得任何关于P1的秘密信息,因为他不能从具有下标h和t的纠缠量子系统的部分量子位中提取全局相位信息。事实上,任何局部酉算子都是如此(除非直接测量),否则部分量子位不能完全分离复合系统的纠缠。因此,即使P2执行这种攻击,他仍然无法得到任何关于P1的私密信息|x1〉。

4.2 截取-重发攻击

协议采用对协议2.2中步骤3)、4)和协议2.3中步骤1)中的辅助量子比特进行检测,来避免截取-重发攻击。在协议中,参与者事实上并没有将自己的私有数据通过量子信道传送,而是将自己的私有态通过U操作与初始量子系统进行复合得到纠缠态,再根据适当的傅里叶逆变换操作来得到求和结果。假设有攻击者通过量子信道获取P0所发送的中间数据|j〉t,攻击者得到的中间数据只有|j〉t,攻击者一旦对其进行测量,由于该复合系统是纠缠的,就会对P0手中拥有的量子态进行塌缩,在协议2.3步骤1)中P0对复合系统进行CNOT门还原,再对|j〉t进行测量,理论上,如果没有攻击者攻击,可以测得|j〉t为|0〉t,但是由于攻击者攻击,使之前的数据塌缩,P0可以正确获得|j〉t刚好为|0〉t的概率为1/2N,所以P0会发现信息被窃取,可以立即停止当前协议,废除数据,重新开始协议进行计算。同理,攻击者对P1及其它参与者采取这样的攻击都适用上述分析,因此,理论上协议可以抵御截取-重发攻击。

5 结论

将多方排序问题转化为求和问题,基于量子傅里叶变换求和设计出一种安全多方量子排序协议,以求取一组秘密数据的排序序列,参与者可获得自己对应的排名,且该排名不会被其他参与者知晓。相较于其他量子排序协议,所提出协议只需要执行O(n)轮次就能够得到排名,一定程度上降低了通信和计算开销。通过在IBM Q平台上对协议进行验证,可知此协议执行正确有效。同时,此协议还能够抵御恶意攻击者的截取-重发攻击,以及n−2名以下参与者的联合攻击。