一種實(shí)用的多數(shù)據(jù)庫(kù)量子信息檢索協(xié)議

賀小云,陳立新,裴昌幸,易運(yùn)暉

(1.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西 西安 710071;2.中國(guó)電子設(shè)備系統(tǒng)工程公司,北京 100039)

一種實(shí)用的多數(shù)據(jù)庫(kù)量子信息檢索協(xié)議

賀小云1,陳立新2,裴昌幸1,易運(yùn)暉1

(1.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西 西安 710071;2.中國(guó)電子設(shè)備系統(tǒng)工程公司,北京 100039)

針對(duì)目前量子私有信息檢索不能適用與云存儲(chǔ)的多數(shù)據(jù)庫(kù)問(wèn)題,基于現(xiàn)在成熟的量子密鑰分發(fā)方法,提出了一種適合在多數(shù)據(jù)庫(kù)環(huán)境下,實(shí)用的量子私有信息檢索協(xié)議。對(duì)于不同大小的數(shù)據(jù)庫(kù),協(xié)議可通過(guò)調(diào)節(jié)參數(shù)θ和k,在保證數(shù)據(jù)庫(kù)安全及用戶(hù)隱私的情況下,完成信息的檢索。性能分析結(jié)果表明,協(xié)議的通信復(fù)雜度低,檢索成功率高、易于實(shí)施。

量子私有信息檢索;量子密鑰分發(fā);多數(shù)據(jù)庫(kù);通信復(fù)雜度

私有信息檢索問(wèn)題(Private Information Retrieval,PIR)是安全多方計(jì)算的一個(gè)重要分支,在數(shù)據(jù)庫(kù)安全查詢(xún)、匿名認(rèn)證、不經(jīng)意傳輸、概率可驗(yàn)證明等領(lǐng)域有著廣闊的前景。PIR的簡(jiǎn)要描述是:服務(wù)器Bob擁有一個(gè)數(shù)據(jù)庫(kù),其中存儲(chǔ)有nbit字符串d1,d2,…,dn,用戶(hù)Alice要查詢(xún)這個(gè)數(shù)據(jù)庫(kù)的某比特?cái)?shù)據(jù)di(1≤i≤N),卻不讓Bob知道i值。此后,Y.Gertner等人于1998年提出對(duì)稱(chēng)私有信息檢索(Symmetrically-Private Information Retrieval,SPIR)協(xié)議[1],在PIR對(duì)用戶(hù)隱私保護(hù)的基礎(chǔ)上,對(duì)服務(wù)器的數(shù)據(jù)隱私也進(jìn)行保護(hù),即既不讓Bob知道i值,也不讓Alice得到di以外的其他任何數(shù)據(jù)庫(kù)信息。

傳統(tǒng)的私有信息檢索協(xié)議在量子計(jì)算和云計(jì)算等新型技術(shù)下較脆弱,于是眾多研究者提出使用量子信息技術(shù)來(lái)解決SPIR問(wèn)題[2-5],即量子私有檢索(Quantum Private Queries,QPQ)技術(shù)。但目前,這些協(xié)議都仍處于理論階段,無(wú)法實(shí)施。2011年,文獻(xiàn)[6]提出了一種QPQ協(xié)議,該方案基于成熟的現(xiàn)有量子密鑰分發(fā)QKD技術(shù),較易實(shí)施。在此基礎(chǔ)上,文獻(xiàn)[7]提出一個(gè)更加靈活和更易實(shí)施的協(xié)議,簡(jiǎn)稱(chēng)高飛協(xié)議。隨后,文獻(xiàn)[8]在二者基礎(chǔ)上已經(jīng)在現(xiàn)實(shí)環(huán)境中成功實(shí)現(xiàn),但受制于現(xiàn)行量子密鑰分發(fā)的速度,只能應(yīng)用于一些小型數(shù)據(jù)庫(kù)的檢索。

隨著大數(shù)據(jù)時(shí)代的到來(lái),PIR技術(shù)在很多現(xiàn)實(shí)情況下將面臨新的問(wèn)題:用戶(hù)檢索的服務(wù)器不是一臺(tái)真實(shí)的物理主機(jī),不僅擁有一個(gè)數(shù)據(jù)庫(kù),而是擁有了很多個(gè)不同類(lèi)型的子數(shù)據(jù)庫(kù)。當(dāng)用戶(hù)需要檢索的其中一個(gè)子數(shù)據(jù)庫(kù)的一個(gè)數(shù)據(jù)時(shí),用戶(hù)不希望服務(wù)器知道他檢索的是哪個(gè)數(shù)據(jù),也不希望服務(wù)器知道他檢索了哪個(gè)子數(shù)據(jù)庫(kù)。針對(duì)這種情況,本文基于高飛協(xié)議提出了一種適合在多數(shù)據(jù)庫(kù)環(huán)境下,實(shí)用的量子私有信息檢索協(xié)議。

1 協(xié)議流程

假設(shè)服務(wù)器Bob擁有m個(gè)長(zhǎng)度均為N的子數(shù)據(jù)庫(kù)(DB1,DB2,…,DBm)。這m個(gè)子數(shù)據(jù)庫(kù)之間互不通信。用戶(hù)Alice要檢索服務(wù)器Bob中第i個(gè)子數(shù)據(jù)庫(kù)DBi的一個(gè)數(shù)據(jù)dij(1≤i≤m,1≤j≤N)。

(1)

(2)

步驟3 Alice通過(guò)經(jīng)典信道向Bob公布所檢測(cè)到的量子態(tài),不考慮丟失的量子。在這個(gè)過(guò)程中,Alice不能有欺騙行為,因?yàn)锳lice還沒(méi)有從所送的量子上得到任何信息,并且他不能從這次欺騙中獲益。因此,這個(gè)協(xié)議是完全容量子丟失的。

步驟5 Alice根據(jù)自己在步驟2的測(cè)量結(jié)果和Bob公布的結(jié)果來(lái)判斷其在第1步的測(cè)量結(jié)果,他能夠以一定的概率p確定Bob所發(fā)的量子。

(3)

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

表1給出了當(dāng)N=14,θ=1,k=2時(shí),Alice檢索一個(gè)子數(shù)據(jù)庫(kù)中檢索號(hào)j=4的實(shí)現(xiàn)過(guò)程。

表1 檢索1個(gè)子數(shù)據(jù)庫(kù)信息的實(shí)現(xiàn)過(guò)程

2 性能分析

2.1 可行性分析

首先對(duì)Alice進(jìn)行分析,在對(duì)其原始密鑰進(jìn)行異或計(jì)算時(shí),至少存在一個(gè)連續(xù)k個(gè)確定的量子比特,這樣才能異或出一個(gè)確定值,協(xié)議才能進(jìn)行下去:將此問(wèn)題進(jìn)行轉(zhuǎn)換,求首次出現(xiàn)連續(xù)k個(gè)確定的量子比特時(shí)的總量子比特?cái)?shù)n′。只有當(dāng)n′

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

(4)

化簡(jiǎn)后可得

(5)

(6)

(7)

顯然,只要合適地對(duì)θ和k取值,使n≥1,協(xié)議就可以進(jìn)行下去。由式(7)可知,可以改變k和θ值,來(lái)得到任意想要的n。對(duì)于n,如果過(guò)大,則每一個(gè)子數(shù)據(jù)庫(kù)泄露給Alice的比特?cái)?shù)就越多,會(huì)造成數(shù)據(jù)庫(kù)信息的過(guò)多泄露。而如果n<1,則會(huì)有很大的概率連一個(gè)確定的比特也得不到,協(xié)議就得重新開(kāi)始。綜合考慮,通常將n取大一些,n≈2。

表2 θ和k的取值方法

2.2 隱私安全性分析

在本協(xié)議中,由于n≈2,故會(huì)造成每個(gè)子數(shù)據(jù)庫(kù)信息的少量泄露,這也是為了提高協(xié)議的成功率及降低通信復(fù)雜度所付出代價(jià)。Alice的測(cè)量結(jié)果是靠量子非正交態(tài)測(cè)不準(zhǔn)和量子態(tài)不可克隆基本物理原理來(lái)保證的,所以Bob不可能在發(fā)送正確數(shù)據(jù)的同時(shí)還可以知道Alice的查詢(xún)索引[7]。

2.3 復(fù)雜度分析

關(guān)于協(xié)議的通信復(fù)雜度。完成一次檢索共需要發(fā)送mN個(gè)量子比特,故通信復(fù)雜度達(dá)到了O(mN)。

再看協(xié)議所需的計(jì)算復(fù)雜度。Alice方面,測(cè)量單個(gè)子數(shù)據(jù)庫(kù)的量子需要計(jì)算量為N,在密鑰異或階段所需計(jì)算量為kN。Bob方面,一個(gè)子數(shù)據(jù)庫(kù)在密鑰稀釋階段所需計(jì)算量為kN,最后數(shù)據(jù)庫(kù)加密階段計(jì)算量為N,故總共需要計(jì)算量約為2(k+1)N。m個(gè)子數(shù)據(jù)庫(kù)的計(jì)算量共約為2(k+1)mN,而這些計(jì)算都是一些簡(jiǎn)單的異或運(yùn)算,容易實(shí)現(xiàn)。

2.4 靈活性分析

3 結(jié)束語(yǔ)

本文基于成熟的QKD技術(shù),提出了一種實(shí)用的多數(shù)據(jù)庫(kù)QPQ協(xié)議。性能分析表明,協(xié)議可根據(jù)數(shù)據(jù)庫(kù)的大小,靈活地去調(diào)節(jié)輔助參數(shù)θ和k,來(lái)保證信息檢索的成功率。同時(shí)協(xié)議通信復(fù)雜度也只有O(mN);故本協(xié)議復(fù)雜度低,易實(shí)現(xiàn),實(shí)用性強(qiáng)。但在該協(xié)議中,每個(gè)子數(shù)據(jù)庫(kù)會(huì)泄露少量的信息,因此,如何減少數(shù)據(jù)庫(kù)信息的泄露是需要改進(jìn)協(xié)議的研究方向。

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61372076);中央高?；究蒲匈M(fèi)專(zhuān)項(xiàng)基金資助項(xiàng)目(K5051301021);高等學(xué)校創(chuàng)新引智計(jì)劃基金資助項(xiàng)目(B08038)

賀小云(1977—),男,工程師。研究方向:量子通信。E-mail:thxy_7498@qq.com。裴昌幸(1945—),男,教授,博士生導(dǎo)師。研究方向:量子通信,網(wǎng)絡(luò)測(cè)量,網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn),通信抗干擾等。

10.16180/j.cnki.issn1007-7820.2015.04.001

TP311

A

1007-7820(2015)04-001-04