基于Bell态的量子安全多方求和

常泓,吴怡婷,林崧

(1福建师范大学数学与信息学院,福建 福州 350007;2福建师范大学数字福建大数据安全技术研究所,福建 福州 350007;3福建师范大学数字福建环境监测物联网实验室,福建 福州 350007)

0 引言

随着量子技术的迅速发展,量子密码[1]已经成为当前量子信息领域的一个重要研究热点。与经典密码不同,量子密码的安全基于量子力学基本原理而非计算复杂度,因此它具有理论上的无条件安全性。近年来,人们充分开发量子力学特性来解决安全问题,如:密钥分发[2-5]、数字签名[6]、网络编码[7]、安全多方计算(SMC)[8-23]等。其中,SMC[8]是密码学领域的一个重要分支,它经常被用来构建电子选举、门限签名以及电子拍卖等复杂安全系统。目前,研究人员正在试图利用量子密码协议来实现经典安全多方计算中一些难以解决甚至无法解决的安全任务,并形成了一些新的研究分支,如:量子保密比较[9-13]、量子私密查询[14-17]、量子安全多方求和(QSMS)[18-23]等。

安全多方求和(SMS)是SMC中的一个重要分支,它可以用来为其他多方计算,特别是数值计算,建立复杂的安全协议。在一个SMC中,有n个参与者P1,P2,···,Pn,且每个参与者Pi都有一个私密数据Mi。它们希望正确地计算求和函数f(M1,M2,···,Mn)而不泄露任何一方的私密数据。函数f的结果可以公开或私下透漏给某个特定的参与者。2007年,Vaccaro等[18]首次在匿名投票和调查的量子协议中提出将经典SMS推广到量子力学领域的QSMS。在这个协议中,每个参与者通过对各自的粒子进行相位旋转操作进行投票。然后,所有的参与者都把他们的粒子发送到计票人手中。同年,Du等[19]提出了基于非正交态的量子保密模加方案,允许累加者把一个数保密地累加在一个未知数上。该方案对于窃取者是渐进安全的,n-1方的共谋攻击不会使得另一方泄露全部信息。随后,研究人员利用不同的量子信息处理技术设计一些各具特色的QSMS协议[20-23],如:量子傅里叶变换、量子隐形传态等。

本文利用纠缠交换特性提出了一种QSMS协议。所提协议通过半可信的第三方在参与者之间分发纠缠的Bell态,利用初态和结果态之间的关系,允许多个相互不信任的各方安全地计算其私密数据的总和,同时,通过对信号粒子进行酉操作来保持其数据的私密性。所提协议不仅可以抵御木马攻击,也可以很好地抵御一些常见的外部攻击和内部攻击。

1 预备知识

一般来说,Bell态[24]的形式可表示为

式中x,y∈{0,1},⊕表示加法模2,|0〉和|1〉为单量子比特的一组计算基。通过对Bell态上的后一个粒子进行4个Pauli操作,就可以实现4个Bell态之间的转化,可描述为

式中:t∈ {0,1},U00=I=|0〉〈0|+|1〉〈1|,U01=Z=|0〉〈0|-|1〉〈1|,U10=X=|0〉〈1|+|1〉〈0|,U11=iY=|0〉〈1|-|1〉〈0|为 4 个 Pauli操作。

纠缠交换[25]是目前量子信息领域中实现信息传输的一种非常重要的途径,它是在不同粒子之间测量交换纠缠的过程。纠缠交换可使从未直接发生相互作用的量子系统产生纠缠,从而达到实现信息传递的目的。假设有两个EPR对(1,2)和(3,4)分别处于Bell态|B(a1,b1)〉12和|B(a2,b2)〉34,其中下标1、2、3、4表示不同粒子。如果对粒子2和3进行Bell测量,得到测量结果|B(x1,y1)〉23,那么粒子1和4就坍缩到Bell态|B(a1⊕a2⊕x1,b1⊕b2⊕y1)〉14。将这种情形推广到n方,可以得到

其中

本文所提出协议就是以Bell态为信息载体,利用上述关系实现安全多方求和任务。

2 量子安全四方求和协议

为了简便起见,首先对量子安全四方求和协议进行描述,然后再将其推广到n方。在四方协议中,假设有4个参与者P1、P2、P3和P4,每个参与者都拥有一个私密数据其中L表示秘密字符串的长度,4个参与者在一个半可信的第三方P0的协助下,通过下述步骤实现安全求和任务。

步骤一:P0制备5个长度为L+R的Bell态链其中上标j=1,2,···,L+R表示Bell态链中粒子的顺序,下标表示粒子,ti=0,1由P0随机确定。将每条链中第k个粒子取出,形成粒子序列Sk,k=1,2,···,10。这样,P0就得到10个有序的粒子序列S1,S2,···,S10。然后,如图1(a)所示,P0在4个参与者之间分发这些粒子序列。具体地,他将粒子序列S2和S3发送给P1,S4和S5发送给P2,S6和S7发送给P3,S8和S9发送给P4,并将S1和S10保留在自己手中。

步骤二:在Pi(i=1,2,3,4)接收到各自的粒子序列后,Pi分别从粒子序列S2i和S2i+1中随机选取R/2个粒子来检测传输是否安全。首先,Pi随机选择基或基对手中的检测粒子进行测量。然后,Pi公布检测粒子的位置,并要求P0公布相应Bell态的初态。最后,Pi要求与之共享Bell态的Pi-1和Pi+1用相同的基测相对应的粒子,并公布测量的结果。Pi检查这些测量结果是否相关。如果错误率超过某一阈值,协议将被终止,并从步骤一重新开始,否则协议会继续。这里,阈值是由参与者们事先协商设定,主要与实际的量子信道噪声情形和协议要求的具体安全级别有关。

步骤三:所有参与者丢弃手中粒子序列Sj中的检测粒子,得到新的粒子序列参与者Pi(i=1,2,3,4)根据自己的私有数据Mi,对粒子序列中的剩余粒子进行编码操作,j=1,2,···,L。

步骤四:Pi(i=1,2,3,4)对手中的粒子序列和中的第j个粒子进行Bell基测量[如图1(b)所示],并记录测量结果与此同时,P0对手中的粒子序列和中的第j个粒子进行Bell基测量,并记录测量结果

步骤五:P0要求4个参与者按照随机的顺序公布他们的测量结果。然后,他利用(4)式很容易计算出

图1 四方协议。(a)P0在四方之间分发粒子序列;(b)Pi(i=1,2,3,4)对序列和的第 j个粒子执行Bell基测量Fig.1 Four-party protocol.(a)P0distributes particle sequences among four participants;(b)Pi(i=1,2,3,4)performs Bell base measurements on the j-th particle of sequence and

3 安全分析

在本节中,将对所提协议的安全性进行讨论。通过对常见的外部攻击和内部攻击的分析,表明所提协议在理论上是安全的。

3.1 外部攻击

外部攻击者的目的是窃取参与者的私密输入。虽然在步骤五中参与者公开了他的测量结果,但这个测量结果与他的编码操作是无关的。这是因为编码操作针对参与者Pi对手中粒子序列中的粒子进行操作,与参与者Pi对手中粒子序列和Bell测量结果无直接关系,即根据这个结果无法获得关于编码操作的任何信息。这就意味着,为了获得秘密,外部攻击者将不得不对传输中的信号粒子进行攻击。然而,这也是不可行的,具体分析如下:外部攻击者的攻击只能发生在P0向Pi传送粒子的过程中,但在Pi接收到粒子后对任意信号粒子序列都会进行步骤二中传输过程的检测。当外部攻击者对传输粒子进行攻击时,就会破坏粒子之间的相关性,必然导致错误而被参与者发现。因此,外部攻击者是无法在不引入错误的情形下窃取私密输入的,协议对外部攻击是安全的。

3.2 半可信第三方P0的攻击

对P0的攻击情形进行分析。由于他是半可信的,不能与其他参与者勾结。为了简单起见,假设P0希望获得P2的私有数据,为了窃取P2的私有数据,P0必须识别P2在他的粒子序列上执行了怎样的操作。由于P0将Bell态发送出去后,粒子就在P2手中,没有被传送回去,所以P0无法获得P2的操作。另外,根据测量结果,P0也无法推得P2的操作。因此,为窃取P2的秘密信息,P0必须对合法信号粒子进行攻击。

在这种情况下,P0常见的攻击策略是制备7组Bell态序列,分别将其中的一组粒子序列代替合法的信号粒子序列传给参与者。如图2所示。然后,当参与者对手中的两个粒子序列进行相应的Bell测量后,P0也对他手中的2个粒子序列进行相应的Bell测量,这样就实现了纠缠交换。当P2公布测量结果后,P0就可以根据他的测量结果以及2个Bell态的初态推得P2的操作,这就意味着P0可以窃取P2的秘密信息。但是,这种攻击将在窃听检测中被发现。因为,P1手中的粒子序列S3中的第j个粒子和P2的粒子序列S4中的第j个粒子并不处于一个真正的Bell态,P0可以对粒子序列对和进行相应的Bell基测量,这就使得粒子序列对(S3,S4)和(S5,S6)坍缩为某一Bell态,并根据测量结果公布一个假消息以此来躲避窃听。然而,在所提协议中粒子初态只能为|B00〉或|B11〉,而粒子序列对(S3,S4)和(S5,S6)将以随机等概率坍缩为4个Bell态之一,故有1/4的概率被检测出来。因此,该种攻击策略也不可行。此外,由于在本攻击中错误率达到25%,故步骤二中的阈值应设置为小于0.25。

图2 半可信第三方攻击Fig.2 The semi-trusted third party’s attack

3.3 不诚实参与者的攻击

在一个n方协议中,由于每个参与者都要获得计算的结果,因此如果有n-1个不诚实的参与者,那么显然这n-1个参与者根据这些信息和自己的输入很容易推得另一个诚实参与者的秘密。同理,如果有n-k个不诚实的参与者共谋攻击,他们显然可以获得剩余k个诚实参与者私密数据的和,因此这些情况是平凡的。

在讨论多个参与者联合攻击的情况时,主要考虑除了这部分信息以外的其他秘密信息。例如,在四方协议中,假设P1和P3是不诚实的,他们显然能获得P2和P4秘密的异或和。协议的关键是防止他们获得P2或P4的秘密,接下来对这种情况进行简要分析。

显然,P1和P3联合窃取P2的秘密比P4的容易,由于P1和P3都是不诚实的参与者,为了窃取P2的信息他们不对自己手中的粒子序列进行Bell基测量,如图3所示。P2作为诚实的参与者,他在步骤三中对粒子序列S5执行酉操作,并对粒子序列S4的第j个粒子和S5的第j个粒子进行Bell基测量,然后公布测量结果随之,P1的粒子序列S3的第j个粒子和P3的粒子序列S6的第j个粒子将坍缩为一个新的Bell态,P1和P3可以对粒子S3序列的第j个粒子和S6序列的第j个粒子进行Bell基测量。在这种情况下,如果两个不诚实的参与者知道粒子序列对(S3,S4)和(S5,S6)的初态,他们就可以根据测量结果和纠缠交换关系式推出P2的私密数据。然而这些粒子的初态始终只有P0知道,即使P1和P3联合攻击,也无法获得P2的私密数据。因此,所提协议可以很好地抵御不诚实参与者的共谋攻击。

图3 一些不诚实参与者的联合攻击。(a)P0在四方之间分发粒子序列;(b)P2对序列S4和S5的第 j个粒子执行Bell基测量Fig.3 The collusion attack of some dishonest participants.(a)P0distributes particle sequences among four participants;(b)P2performs Bell base measurements on the j-th particle of sequence S4and S5

4 多方协议

把协议推广到n方。假设有n个参与者Pi(i=1,2,···,n),每个参与者有一个私密数据Mi=他们在半可信第三方P0的协助下可以安全地计算出的结果,其中:L是每个私有数据字符串的长度。协议步骤如下。

步骤一:P0制备n+1个长度为L+R的Bell态链其中上标j=1,2,···,L+R表示Bell态链中粒子的顺序,下标表示粒子,ti=0,1由P0随机确定。将每条链中第k个粒子取出,形成粒子序列Sk,k=1,2,···,2(n+2)。这样,P0就得到2(n+2)个有序的粒子序列S1,S2,···,S2n+1,S2n+2。然后,P0在n个参与者之间分发这些粒子序列。具体地,他将粒子序列S2i和S2i+1发送给Pi,并将粒子序列S1和S2n+2保留在自己手中(i=1,2,···,n)。

步骤二:在Pi(i=1,2,···,n)接收到各自的粒子序列后,Pi分别从粒子序列S2i和S2i+1中随机选取R/2个粒子来检测传输是否安全。首先,Pi随机选择{|+〉,|-〉}基或{|0〉,|1〉}对手中的检测粒子进行测量;然后,Pi公布检测粒子的位置,并要求P0公布相应Bell态的初态;最后,Pi要求与之共享Bell态的Pi-1和Pi+1用相同的基测相对应的粒子,并公布测量的结果。Pi检查这些测量结果是否相关。如果错误率超过某一阈值,协议将被终止,并从步骤一重新开始,否则协议会继续。

步骤三:所有参与者丢弃手中粒子序列Sj中的检测粒子,得到新的粒子序列参与者Pi根据自己的私密数据Mi,对粒子序列中的第j个粒子进行编码操作,j=1,2,···,L。总之,Pi对手中的粒子序列执行操作。

步骤四:Pi(i=1,2,···,n)对手中的粒子序列和中的第j个粒子进行Bell基测量,记录测量结果与此同时,P0对手中的粒子序列和中的第j个粒子进行Bell基测量,并记录测量结果

步骤五:P0要求n个参与者按照随机的顺序公布他们的测量结果。然后,P0计算

即n个参与者的私有数据串Mi中的第j个私有数据之和并将该结果告诉参与者。这样,n个参与者就可以在不公布私密输入的前提下获得求和结果。

5 结论

提出了一个利用Bell态纠缠交换来实现多方安全求和的量子协议。协议中半可信第三方P0负责制备Bell态并将这些信号粒子发送给每个参与者。然后,根据各自的私密数据,每个参与者对信号粒子进行相应的编码操作,并通过Bell基测量实现纠缠交换。最后,P0利用测量结果和信号粒子的初态推得这些私密数据的异或和。对协议中一些常见内部和外部攻击下的分析表明所提协议在理论上是安全的。同时,由于信号粒子在信道中仅进行一次单向传输,常见的物理攻击(如木马攻击[26,27])对所提协议也是无效的。此外,除检测粒子外,协议利用一组Bell态来计算两个经典比特的异或和,与现有一些QSMS协议[18-23]相比,所提协议取得了更高的效率。另一方面,与这些协议相比,所提出协议仅要求参与者具有单粒子酉操作和Bell基测量的能力,可行性也更高。当然,本协议在执行过程中每个参与者都需要将多个粒子高效地存储在本地,即要求参与者具有量子存储能力,这在目前的实验水平下仍是困难的,因此如何设计一个在现有技术条件下可行的多方安全求和量子协议(如:无需量子存储等)将是下一步研究的主要工作之一。