一种实用的多数据库量子信息检索协议

贺小云,陈立新,裴昌幸,易运晖

(1.西安电子科技大学 综合业务网理论及关键技术国家重点实验室,陕西 西安 710071;2.中国电子设备系统工程公司,北京 100039)

一种实用的多数据库量子信息检索协议

贺小云1,陈立新2,裴昌幸1,易运晖1

(1.西安电子科技大学 综合业务网理论及关键技术国家重点实验室,陕西 西安 710071;2.中国电子设备系统工程公司,北京 100039)

针对目前量子私有信息检索不能适用与云存储的多数据库问题,基于现在成熟的量子密钥分发方法,提出了一种适合在多数据库环境下,实用的量子私有信息检索协议。对于不同大小的数据库,协议可通过调节参数θ和k,在保证数据库安全及用户隐私的情况下,完成信息的检索。性能分析结果表明,协议的通信复杂度低,检索成功率高、易于实施。

量子私有信息检索;量子密钥分发;多数据库;通信复杂度

私有信息检索问题(Private Information Retrieval,PIR)是安全多方计算的一个重要分支,在数据库安全查询、匿名认证、不经意传输、概率可验证明等领域有着广阔的前景。PIR的简要描述是:服务器Bob拥有一个数据库,其中存储有nbit字符串d1,d2,…,dn,用户Alice要查询这个数据库的某比特数据di(1≤i≤N),却不让Bob知道i值。此后,Y.Gertner等人于1998年提出对称私有信息检索(Symmetrically-Private Information Retrieval,SPIR)协议[1],在PIR对用户隐私保护的基础上,对服务器的数据隐私也进行保护,即既不让Bob知道i值,也不让Alice得到di以外的其他任何数据库信息。

传统的私有信息检索协议在量子计算和云计算等新型技术下较脆弱,于是众多研究者提出使用量子信息技术来解决SPIR问题[2-5],即量子私有检索(Quantum Private Queries,QPQ)技术。但目前,这些协议都仍处于理论阶段,无法实施。2011年,文献[6]提出了一种QPQ协议,该方案基于成熟的现有量子密钥分发QKD技术,较易实施。在此基础上,文献[7]提出一个更加灵活和更易实施的协议,简称高飞协议。随后,文献[8]在二者基础上已经在现实环境中成功实现,但受制于现行量子密钥分发的速度,只能应用于一些小型数据库的检索。

随着大数据时代的到来,PIR技术在很多现实情况下将面临新的问题:用户检索的服务器不是一台真实的物理主机,不仅拥有一个数据库,而是拥有了很多个不同类型的子数据库。当用户需要检索的其中一个子数据库的一个数据时,用户不希望服务器知道他检索的是哪个数据,也不希望服务器知道他检索了哪个子数据库。针对这种情况,本文基于高飞协议提出了一种适合在多数据库环境下,实用的量子私有信息检索协议。

1 协议流程

假设服务器Bob拥有m个长度均为N的子数据库(DB1,DB2,…,DBm)。这m个子数据库之间互不通信。用户Alice要检索服务器Bob中第i个子数据库DBi的一个数据dij(1≤i≤m,1≤j≤N)。

(1)

(2)

步骤3 Alice通过经典信道向Bob公布所检测到的量子态,不考虑丢失的量子。在这个过程中,Alice不能有欺骗行为,因为Alice还没有从所送的量子上得到任何信息,并且他不能从这次欺骗中获益。因此,这个协议是完全容量子丢失的。

步骤5 Alice根据自己在步骤2的测量结果和Bob公布的结果来判断其在第1步的测量结果,他能够以一定的概率p确定Bob所发的量子。

(3)

式中,i=1,2,…,N;kN+x=kx;1≤x≤N。

表1给出了当N=14,θ=1,k=2时,Alice检索一个子数据库中检索号j=4的实现过程。

表1 检索1个子数据库信息的实现过程

2 性能分析

2.1 可行性分析

首先对Alice进行分析,在对其原始密钥进行异或计算时,至少存在一个连续k个确定的量子比特,这样才能异或出一个确定值,协议才能进行下去:将此问题进行转换,求首次出现连续k个确定的量子比特时的总量子比特数n′。只有当n′

uk=p(uk-1+1)+(1-p)(uk-1+1+uk)

(4)

化简后可得

(5)

(6)

(7)

显然,只要合适地对θ和k取值,使n≥1,协议就可以进行下去。由式(7)可知,可以改变k和θ值,来得到任意想要的n。对于n,如果过大,则每一个子数据库泄露给Alice的比特数就越多,会造成数据库信息的过多泄露。而如果n<1,则会有很大的概率连一个确定的比特也得不到,协议就得重新开始。综合考虑,通常将n取大一些,n≈2。

表2 θ和k的取值方法

2.2 隐私安全性分析

在本协议中,由于n≈2,故会造成每个子数据库信息的少量泄露,这也是为了提高协议的成功率及降低通信复杂度所付出代价。Alice的测量结果是靠量子非正交态测不准和量子态不可克隆基本物理原理来保证的,所以Bob不可能在发送正确数据的同时还可以知道Alice的查询索引[7]。

2.3 复杂度分析

关于协议的通信复杂度。完成一次检索共需要发送mN个量子比特,故通信复杂度达到了O(mN)。

再看协议所需的计算复杂度。Alice方面,测量单个子数据库的量子需要计算量为N,在密钥异或阶段所需计算量为kN。Bob方面,一个子数据库在密钥稀释阶段所需计算量为kN,最后数据库加密阶段计算量为N,故总共需要计算量约为2(k+1)N。m个子数据库的计算量共约为2(k+1)mN,而这些计算都是一些简单的异或运算,容易实现。

2.4 灵活性分析

3 结束语

本文基于成熟的QKD技术,提出了一种实用的多数据库QPQ协议。性能分析表明,协议可根据数据库的大小,灵活地去调节辅助参数θ和k,来保证信息检索的成功率。同时协议通信复杂度也只有O(mN);故本协议复杂度低,易实现,实用性强。但在该协议中,每个子数据库会泄露少量的信息,因此,如何减少数据库信息的泄露是需要改进协议的研究方向。

[1]GertnerY,IshaiY,EyalK,etal.Protectingdataprivacyinprivateinformationretrievalschemes[C].NewYork:13thAnnualACMSytnposiumonTheoryofComputing,ACM,1998:151-160.

[2]GiovannettiV,LloydS,MacconeL.Quantumprivatequeries[J].PhysicalReviewLetter,2008,100(23):230-234.

[3]GiovannettiV,LloydS,MacconeL.Quantumprivatequeries:securityanalysis[J].IEEETransactionsonInformationTheory,2010,56(7):3465-3477.

[4]LukaszOlejnik.Securequantumprivateinformationretrievalusingphase-encodedqueries[J].PhysicalReviewA,2011,84(2):2313-2316.

[5]DeMartiniF,GiovannettiV,LloydS,etal.Experimentalquantumprivatequerieswithlinearoptics[J].PhysicalReviewA,2009,80(1):0302-0305.

[6]JakobiM,SimonC,GisinN,etal.Practicalprivatedatabasequeriesbasedonaquantumkeydistributionprotocol[J].PhysicalReviewA,2011,83(2):2301-2306.

[7]GaoFei,LiuBin,WenQiaoyan.Flexiblequantumprivatequeriesbasedonquantumkeydistribution[J].OpticsExpress,2012,20(16):17411-17420.

[8]ChanPhilip,Lucio-MartinezItzel,MoXiaofan,etal.Performingprivatedatabasequeriesinareal-worldenvironmentusingaquantumprotocol[J].SciRepet,2014,10(4):5233-5246.

[9]YangYG,SunSJ,XuP,etal.FlexibleprotocolforquantumprivatequerybasedonB92protocol[J].QuantumInformationProcess,2014(13):805-813.

[10]YuFang,QiuDaowen.Coding-basedquantumprivatedatabasequeryusingentanglement[J].QuantumInformation&Computation,2014,14(1):91-106.

A Practical Multi-Database Quantum Private Queries Protocol

HE Xiaoyun,CHEN Lixin,PEI Changxin,YI Yunhui

(1.State Key Laboratory of Integrated Service Networks,Xidian University,Xi’an 710071,China;2.China Electronic Systems Engineering Corporation,Beijing 100039,china)

This paper,based on the QKD technology which is mature now,proposes a practical QPQ protocol for multi-database retrieval optimized for current multi-databases in cloudy storage.For different sizes of the database,by adjusting the parametersθandk,the information can be retrieved,while the safety of database and privacy of the user are ensured.Performance analyses indicate that the protocol has a low communication complexity and a high success ratio in information retrieval,and is easy to implement.

quantum private queries;quantum key distribution;multi-database;communication complexity

2014- 09- 16

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

贺小云(1977—),男,工程师。研究方向:量子通信。E-mail:thxy_7498@qq.com。裴昌幸(1945—),男,教授,博士生导师。研究方向:量子通信,网络测量,网络拓扑发现,通信抗干扰等。

10.16180/j.cnki.issn1007-7820.2015.04.001

TP311

A

1007-7820(2015)04-001-04