一种低复杂度的量子私有信息检索协议

贺小云,裴昌幸,易运晖

(西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071)

一种低复杂度的量子私有信息检索协议

贺小云,裴昌幸,易运晖

(西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071)

私有信息检索是安全多方计算中重要的隐私保护问题,基于经典密码学的协议在量子计算和云计算等新型技术下十分脆弱,而现有的量子私有信息检索协议的复杂度高,在面对大型数据库时效率低下.基于目前成熟的量子密钥分发技术,提出了一种结合了密钥稀释和辅助参数两种方法的量子私有信息检索协议.协议中量子信道中只发送N个量子产生初始密钥,然后对初始密钥中连续K个比特进行按位相加去稀释初始密钥,产生最终密钥去加密数据库,并可通过灵活的选择辅助参数θ和k来保证双方隐私的安全性和提高检索成功率.可行性和性能分析结果表明,协议易于实施,一次检索成功率高,通信复杂度达到了O(N).

量子私有信息检索;量子密钥分发;通信复杂度;数据库安全;用户隐私

在大数据时代,安全多方计算是计算机科学中的热门研究领域,是密码学的新方向.Chor等[1]于1995年提出的私有信息检索问题(Private Information Retrieval,PIR)就是安全多方计算的一个分支,在安全多方计算的数据库安全查询、匿名认证、不经意传输、概率可验证明等领域有着广阔的前景.私有信息检索问题描述的是:服务器Bob拥有一个数据库,其中有N个数据{d1,d2,…,dN},用户Alice要查询这个数据库的某条数据di(1≤i≤N),而Bob却不知道i的值.后来,Gertner等[2]于1998年提出对称私有信息检索(Symmetrically Private Information Retrieval,SPIR)协议,对服务器的数据隐私也进行保护,即Alice除了di得不到任何其他数据库信息.

量子信息技术作为信息学与物理学相互融合产生的新兴交叉学科,在运算速度、通信效率、安全性等方面均有优于或远远优于传统信息技术的表现.传统的私有信息检索协议在量子计算和云计算等新型技术下十分脆弱,现如今出现多个用量子信息技术来解决对称私有信息检索问题的协议[3-6],即量子私有检索(Quantum Private Queries,QPQ)协议.其中比较有代表性的是文献[3,5]提出的协议,两者分别采用量子比特编码和相位编码的方法,但是在应用于规模较大的数据库时,协议中的量子计算的规模将会非常高,实现起来非常困难.

2011年,Jakobi等[7]提出了一种基于量子密钥分发(Quantum Key Distribution,QKD)的量子私有信息检索协议(简称J协议).该协议提供了很好的数据库安全性和用户隐私性,抗量子丢失,并可以避免常见的第三者窃听和攻击.由于协议基于量子密钥分发,故可以很容易使用成熟的现有的量子密钥分发技术来实现.但在J协议中,实现一次N比特数据库检索,Bob最少要通过量子通道向Alice传送kN个量子比特.在检索大数据库时,例如N=108,k=13,采用较为典型的量子密钥分发的速度1 Mbit/s[8]发送,则完成一次一个比特的检索需要大约21 min,所付出的通信成本显然就太高了.因此,降低通信复杂度仍是一个亟待解决的问题.

Gao等[9]在J协议基础上提出一个更加灵活和易于实施的协议(简称G协议).G协议引进一个可以调节的参数θ,通过减少θ的值来降低k,从而降低通信复杂度.同样在面对大数据库时,如N=108,要达到一个最低的通信复杂度,即k=1,此时参数θ≈0.000 14,实现起来难度非常大.即使取一个较易实现的θ(θ= π/10),此时k=5,完成一次检索仍然需要大约8 min,付出的通信成本依然很高,并且会大幅降低Alice的隐私性[9].

为了进一步减小通信成本,笔者基于G协议提出了一种通信复杂度更低的量子私有信息检索协议.

1 协议流程

假设用户Alice要从服务器Bob中检索数据,Bob的数据库M中的数据长度为N,Alice检索的索引为i,协议描述如下:

步骤1 Bob准备一个量子序列,每个量子随机地处于状态|0〉,|1〉,|0′〉和|1′〉这4个态之一.量子态|0〉和|1〉表示0,而量子态|0′〉和|1′〉表示1.然后发给Alice,这里

其中,θ∈(0,π/2).

步骤2 Alice随机选用基B={|0〉,|1〉}或者基B={|0′〉,|1′〉}来测量收到的量子.显然,这次测量不会让他推导出Bob所发量子比特的值.

步骤3 Alice随后向Bob公布所检测到的量子态,而抛弃掉丢失的量子.显然Alice不能有欺骗行为,因为Alice还没有从所发送的量子上得到任何信息,并且他不能从这次欺骗中获益.因此,这个协议是容量子丢失的.

步骤4 对于Alice每次测量到的量子态,Bob公布0或1,这里0代表这个量子开始时处于态|0〉或者|0′〉,而1代表量子态是|1〉或者|1′〉.

步骤5 Alice根据他的测量结果和Bob公布的结果来判断他在第1步的测量结果,他可以一定的概率p确定Bob所发的量子.例如,如果Bob公布值是0,而他在步骤2测量结果为|1〉,他只有用基B测量才可以排除|0〉,推断出最开始所发的量子态为|0′〉,其值为1.因此,对于Bob的公布,Alice测量到正确结果的概率p=sin2θ2,不确定的概率为1-p.所有测量确定的和不确定的结果都保存下来.通过这种方式, Alice和Bob共享一个初始密钥字符串Kr.Bob知道Kr中所有的值,而Alice只知道一部分(整个的sin2θ2).

步骤6 Bob只向Alice发送N个量子,然后停止发送.让这N个量子作为初始密钥Kr={k1,k2,…,kN}.Bob知道Kr中所有的值,而Alice确定其中大约Np个比特.然后对初始密钥Kr进行稀释,使Alice拥有确定的比特数减少为一个或几个.双方进行的运算为

其中,i=1,2,…,N;kN+x=kx;1≤x≤N.

经过初始密钥Kr的稀释,形成了一个新的长度为N的密匙K={k′1,k′2,…,k′N}.如果Alice此时没得到一个正确的比特,则协议重新开始.不过由随后的讨论可知,这种情况发生的概率非常小.

步骤7 Alice现在准确地知道密钥K中最少一个比特,假定为第j位元素kj,而他想检索数据库M中的第i位Mi.Alice为了能正确地译码,他向Bob公布数字s=j-i,Bob得到s后,对K移s位后得到新的密匙K′.用K′对M进行加密,可以得到加密后的数据库M′=M⊕K′.将M′公布给Alice,Alice通过计算Mi=M′j⊕K′j,就可以得到他想查询的数据Mi.

当θ=π/4,k=2,N=20时,Alice检索数据库中检索号i=2的实现过程见表1.

表1 一次量子私有信息检索协议的检索实现过程

2 可行性分析

在步骤6中,Alice在对初始密钥进行稀释时,必须确保初始密钥至少存在一个连续k个确定的量子比特,这样才能异或出一个确定值,协议才能进行下去.

将此问题进行转换,去求首次出现连续k个确定的量子比特时的总量子比特数n′.很明显,只有当n′＜N时,协议才是可行的.故假定有事件X,当X=1时,代表测量准确,发生的概率为p;当X=0时,代表测不准,发生的概率为1-p.计算当首次出现X连续k次为1时,总发生次数的数学期望uk.考虑如下情形:首次出现连续k-1次1,此时总次数的期望为uk-1.再测一次,结果有且只有以下两种:

(A) 出现1,则满足条件,所用次数的数学期望为uk-1+1.

(B) 出现0,则立即回到初始状态,相当于又要从零开始出现k次连续1,因此总次数的数学期望为uk-1+1+uk.

A、B两种情况的概率分别为p,1-p.因此,有

化简后可得

显然,此为一递推数列.u1=1/p,可求得通项公式

其中,t=1/p,p=sin2θ/2.由式(6)知,uk是由θ和k共同来决定的.图1给出了当θ=π/6,π/5和π/4时,由式(6)求得的uk随k的变化曲线示意图.可以看出,k值越大,uk越大;在k值相同时,θ小的uk要大一些.

显然,只要合适地对θ和k取值,使uk满足N＞uk,协议就可以进行下去.相应地,Alice在步骤6结束后,所能得到最终密钥K中确定的比特数n约等于Nuk.将式(6)代入,可得

其中,t=1/p,p=sin2θ/2.在N和θ一定的条件下,k的取值如果过大,使N＜uk,则会有很大的概率连一个确定的比特也得不到,协议就得重新开始;而k的取值如果太小,则Alice能确定最终密钥K中的比特数n又会太多,会造成数据库信息的过多泄露.一个理想的k值应使Alice测量得到正确原始密钥K中一个或者很少几个比特.表2给出了理想情况下,当θ为π/6,π/5和π/4时,在不同的数据库大小N下,k的取值和对应的n的关系.可以看出,在相同的数据库下,θ越大,需要做的异或次数k就会增加.

为了保证一次检索的成功率,碰到n只有1个多比特的时候,可适当地调整θ和k去增加n.例如表2中,当θ=π/4,N=105,k=8时,n=1.1,故此时可取θ=0.74,k=7,对应的n=2.4.通过以上对θ和k取值方法的讨论,可以看出本协议在步骤6结束后,由于Alice在最终密钥中得不到一个确定量子比特,使协议重新开始的概率很小.

图1 不同的θ取值下,uk随k的变化曲线

表2 在理想情况下,不同数据库大小N下,k和n的取值

3 性能分析

可知概率增加了.图3就是正常测量概率和最优非歧义态区分测量后,Alice测量正确结果的概率的对比图.当θ较小时,p和pUSD相差不多;随着θ增大,两者的差越来越大.因此,合适地选取θ,可以保证数据库的隐私.

表3就是θ为π/6和π/4时,Alice正常测量和最优非歧义态区分测量确定比特数对比.可以看出,当θ较小

3.1 灵活性分析

在G协议和本协议中,对于任意的数据库,可以通过调节θ和k来获得一个任意想要的Alice测量得到正确原始密钥的比特数n(n≪N).但在G协议中,k是直接影响通信复杂度的.在检索大型数据库时,要保持一个好的通信复杂度,即要k值小,则必须采用一个很小的θ,实现起来将会十分困难.在本协议中,k已经不影响通信复杂度了,所以就不必去为了降低量子通信复杂度而采用一个非常小的θ,增加实现难度.图2给出了当N=104,n≈3和N=106,n≈5时,由式(7)得到的k和θ的关系曲线.所以与G协议相比,本协议更加灵活,特别在检索大型数据库时,效率更高.

3.2隐私安全性分析

3.2.1 数据库的安全性

图2 不同的数据库N和n时,k和θ的关系曲线

如果Alice是非诚实用户,他将收到的所有量子比特都存储下来,就能够在步骤4中Bob公布完后进行有效的测量.然后采用非歧义态区分(Unambiguous State Discrimination,USD)测量,由文献[9]的分析可知,采用最优非歧义态区分测量后,Alice测量正确结果的概率pUSD=1-cosθ,由时,p和pUSD相差很小,例如当θ=π/6时,p=0.125, pUSD=0.134,使用最优非歧义态区分测量确定的最终密钥的比特数nUSD增加不多.而θ越大,即θ=π/4时,p=0.25, pUSD=0.29,p和pUSD相差变大,使用最优非歧义态区分测量增加的确定比特数nUSD也越来越多.故从加强数据库安全这个角度出发,应该选取较小的θ.

此外,笔者给出的协议为了提高协议的成功率,当Alice测量的确定的比特数n只有1个多比特时,调整θ和k,增加n,造成数据库信息泄露量增加很少.这也是为了提高协议成功率所付出的代价.

图3 正常测量和最优非歧义态区分测量的概率比较

表3 正常测量和非歧义态区分测量确定比特数对比

笔者提出的协议主要是产生密钥的方法与G协议不同,但同样能达到数据库安全性的要求.

3.2.2 用户的隐私

本协议中Alice的测量结果是靠量子非正交态测不准和量子态不可克隆基本物理原理来保证的,所以Bob不可能在发送正确数据的同时还知道Alice的查询索引,这个原因与文献[7]中的一样.

对于参数θ,Bob猜出Alice的检索地址的概率pc=cos2(θ/2)[9].参数θ越小,pc越大,Bob越容易猜出Alice的检索地址.特别地,当检索的数据库比较小时,如果θ也取得很小,像N=50,θ=0.6,此时k只能等于1.很明显,Alice进行检索时,步骤7中最终密钥无须进行移位,所以Bob就很容易地知道Alice的检索地址.故从加强用户隐私性这个角度去看,应该选取大一些的θ.

当数据库比较小时,可以将θ增大,加强Alice的隐私性,相应地泄露给Alice的数据库比特数也增多.而数据库很大时,这时可以适当减小θ来提高数据库的安全性.故从数据库的安全性和用户的隐私两个方面综合考虑,通常在θ=π/4附近随机取值.

3.3 复杂度分析

关于协议的通信复杂度.在G协议中,Bob至少需要发送k N个量子比特作为密钥,并且k随着数据库N增大而增大,故综合可知,执行一次检索,通信复杂度大约为O(N log N)[10].而对于笔者所提协议,可以看到总共只需要发送N个量子比特,故通信复杂度达到了O(N).

再看协议所需的计算复杂度.在G协议中,在Alice方面,测量量子需要计算量为kN,在密钥稀释阶段所需计算量为kN,在解密阶段计算量为N.在Bob方面,在密钥稀释阶段所需计算量为kN,最后数据库加密阶段计算量为N,总共需要计算量大约等于(3k+2)N.笔者提出的协议中,Alice测量量子需要计算量为N,故最后计算量大约等于(2k+3)N,约减小了(k-1)N.当检索的数据库规模N越大时,节约的数据处理时间越多.

4 总 结

以上提出的量子私有信息检索协议在进行密钥稀释时,通过对初始密钥中连续的k个比特进行异或,使量子信道发送的量子长度只有N,从而使通信复杂度达到最优的O(N);在检索大小不同的数据库时,通过合适地调节辅助参数θ和k,既提高了成功率,又可满足安全性的要求.故本协议复杂度低,灵活性好,一次检索成功率高,易于实现.

[1]Chor B,Goldreich O,Kushilevitz E,et al.Private Information Retrieval[C]//Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science.Los Alamitos:IEEE,1995:41-50.

[2]Gertner Y,Ishai Y,Kushilevitz E,et al.Protecting Data Privacy In Private Information Retrieval Schemes[C]// Proceedings of 13th Annual ACM Sytnposium on Theory of Computing.New York:ACM,1998:151-160.

[3]Giovannetti V,Lloyd S,Maccone L.Quantum Private Queries[J].Physical Review Letter,2008,100(23):230502.

[4]Giovannetti V,Lloyd S,Maccone L.Quantum Private Queries:Security Analysis[J].IEEE Transactions on Information Theory,2010,56(7):3465-3477.

[5]Olejnik L.Secure Quantum Private Information Retrieval Using Phase-encoded Queries[J].Physical Review A,2011, 84(2):022313-022316.

[6]De Martini F,Giovannetti V,Lloyd S,et al.Experimental Quantum Private Queries with Linear Optics[J].Physical Review A,2009,80(1):010302-010305.

[7]Jakobi M,Simon C,Gisin N,et al.Practical Private Database Queries Based on a Quantum Key Distribution Protocol [J].Physical Review A,2011,83(2):2301-2306.

[8]Dixon A R,Yuan Z L,Dynes J F,et al.Continuous Operation of High Bit Rate Quantum Key Distribution[J].Applied Physics Letters,2010,96(16):1102-1104.

[9]Gao F,Liu B,Wen Q Y.Flexible Quantum Private Queries Based on Quantum Key Distribution[J].Optics Express, 2012,20(16):17411-17420.

[10]Brassard G.Quantum Communication Complexity[J].Foundations of Physics,2003,33(11):1593-1616.

(编辑:郭 华)

Low complexity quantum private queries protocol

HE Xiaoyun,PEI Changxing,YI Yunhui
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

Private information retrieval(PIR)is an important privacy protection issue of secure multi-party computation,but the PIR protocols based on classical cryptography are vulnerable because of new technologies,such as quantum computing and cloud computing.The quantum private queries(QPQ) protocols available,however,has a high complexity and is inefficient in the face of large database.This paper,based on the QKD technology which is mature now,proposes a novel QPQ protocol utilizing the key dilution and auxiliary parameter.Only N quits are required to be sent in the quantum channel to generate the raw key,then the straight k bits in the raw key are added bitwise to dilute the raw key,and a final key is consequently obtained to encrypt the database.By flexible adjusting of auxiliary parametersθand k,privacy is secured and the query success ratio is improved.Feasibility and performance analyses indicate that the protocol has a high success ratio in first-trial query and is easy to implement,and that the communication complexity of O(N)is achieved.

quantum private queries;quantum key distribution;communication complexity;database security;user privacy

TP918

A

1001-2400(2015)05-0033-05

2014-05-12< class="emphasis_bold">网络出版时间:

时间:2014-12-23

国家自然科学基金资助项目(61372076);中央高校基本科研业务费专项资金资助项目(K5051301021,K5051301022);高等学校创新引智计划资助项目(B08038)

贺小云(1977-),男,西安电子科技大学博士研究生,E-mail:thxy@msn.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.006.html

10.3969/j.issn.1001-2400.2015.05.006