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

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

一種低復(fù)雜度的量子私有信息檢索協(xié)議

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

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

私有信息檢索是安全多方計(jì)算中重要的隱私保護(hù)問(wèn)題,基于經(jīng)典密碼學(xué)的協(xié)議在量子計(jì)算和云計(jì)算等新型技術(shù)下十分脆弱,而現(xiàn)有的量子私有信息檢索協(xié)議的復(fù)雜度高,在面對(duì)大型數(shù)據(jù)庫(kù)時(shí)效率低下.基于目前成熟的量子密鑰分發(fā)技術(shù),提出了一種結(jié)合了密鑰稀釋和輔助參數(shù)兩種方法的量子私有信息檢索協(xié)議.協(xié)議中量子信道中只發(fā)送N個(gè)量子產(chǎn)生初始密鑰,然后對(duì)初始密鑰中連續(xù)K個(gè)比特進(jìn)行按位相加去稀釋初始密鑰,產(chǎn)生最終密鑰去加密數(shù)據(jù)庫(kù),并可通過(guò)靈活的選擇輔助參數(shù)θ和k來(lái)保證雙方隱私的安全性和提高檢索成功率.可行性和性能分析結(jié)果表明,協(xié)議易于實(shí)施,一次檢索成功率高,通信復(fù)雜度達(dá)到了O(N).

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

在大數(shù)據(jù)時(shí)代,安全多方計(jì)算是計(jì)算機(jī)科學(xué)中的熱門研究領(lǐng)域,是密碼學(xué)的新方向.Chor等[1]于1995年提出的私有信息檢索問(wèn)題(Private Information Retrieval,PIR)就是安全多方計(jì)算的一個(gè)分支,在安全多方計(jì)算的數(shù)據(jù)庫(kù)安全查詢、匿名認(rèn)證、不經(jīng)意傳輸、概率可驗(yàn)證明等領(lǐng)域有著廣闊的前景.私有信息檢索問(wèn)題描述的是:服務(wù)器Bob擁有一個(gè)數(shù)據(jù)庫(kù),其中有N個(gè)數(shù)據(jù){d1,d2,…,dN},用戶Alice要查詢這個(gè)數(shù)據(jù)庫(kù)的某條數(shù)據(jù)di(1≤i≤N),而B(niǎo)ob卻不知道i的值.后來(lái),Gertner等[2]于1998年提出對(duì)稱私有信息檢索(Symmetrically Private Information Retrieval,SPIR)協(xié)議,對(duì)服務(wù)器的數(shù)據(jù)隱私也進(jìn)行保護(hù),即Alice除了di得不到任何其他數(shù)據(jù)庫(kù)信息.

量子信息技術(shù)作為信息學(xué)與物理學(xué)相互融合產(chǎn)生的新興交叉學(xué)科,在運(yùn)算速度、通信效率、安全性等方面均有優(yōu)于或遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)信息技術(shù)的表現(xiàn).傳統(tǒng)的私有信息檢索協(xié)議在量子計(jì)算和云計(jì)算等新型技術(shù)下十分脆弱,現(xiàn)如今出現(xiàn)多個(gè)用量子信息技術(shù)來(lái)解決對(duì)稱私有信息檢索問(wèn)題的協(xié)議[3-6],即量子私有檢索(Quantum Private Queries,QPQ)協(xié)議.其中比較有代表性的是文獻(xiàn)[3,5]提出的協(xié)議,兩者分別采用量子比特編碼和相位編碼的方法,但是在應(yīng)用于規(guī)模較大的數(shù)據(jù)庫(kù)時(shí),協(xié)議中的量子計(jì)算的規(guī)模將會(huì)非常高,實(shí)現(xiàn)起來(lái)非常困難.

2011年,Jakobi等[7]提出了一種基于量子密鑰分發(fā)(Quantum Key Distribution,QKD)的量子私有信息檢索協(xié)議(簡(jiǎn)稱J協(xié)議).該協(xié)議提供了很好的數(shù)據(jù)庫(kù)安全性和用戶隱私性,抗量子丟失,并可以避免常見(jiàn)的第三者竊聽(tīng)和攻擊.由于協(xié)議基于量子密鑰分發(fā),故可以很容易使用成熟的現(xiàn)有的量子密鑰分發(fā)技術(shù)來(lái)實(shí)現(xiàn).但在J協(xié)議中,實(shí)現(xiàn)一次N比特?cái)?shù)據(jù)庫(kù)檢索,Bob最少要通過(guò)量子通道向Alice傳送kN個(gè)量子比特.在檢索大數(shù)據(jù)庫(kù)時(shí),例如N=108,k=13,采用較為典型的量子密鑰分發(fā)的速度1 Mbit/s[8]發(fā)送,則完成一次一個(gè)比特的檢索需要大約21 min,所付出的通信成本顯然就太高了.因此,降低通信復(fù)雜度仍是一個(gè)亟待解決的問(wèn)題.

Gao等[9]在J協(xié)議基礎(chǔ)上提出一個(gè)更加靈活和易于實(shí)施的協(xié)議(簡(jiǎn)稱G協(xié)議).G協(xié)議引進(jìn)一個(gè)可以調(diào)節(jié)的參數(shù)θ,通過(guò)減少θ的值來(lái)降低k,從而降低通信復(fù)雜度.同樣在面對(duì)大數(shù)據(jù)庫(kù)時(shí),如N=108,要達(dá)到一個(gè)最低的通信復(fù)雜度,即k=1,此時(shí)參數(shù)θ≈0.000 14,實(shí)現(xiàn)起來(lái)難度非常大.即使取一個(gè)較易實(shí)現(xiàn)的θ(θ= π/10),此時(shí)k=5,完成一次檢索仍然需要大約8 min,付出的通信成本依然很高,并且會(huì)大幅降低Alice的隱私性[9].

為了進(jìn)一步減小通信成本,筆者基于G協(xié)議提出了一種通信復(fù)雜度更低的量子私有信息檢索協(xié)議.

1 協(xié)議流程

假設(shè)用戶Alice要從服務(wù)器Bob中檢索數(shù)據(jù),Bob的數(shù)據(jù)庫(kù)M中的數(shù)據(jù)長(zhǎng)度為N,Alice檢索的索引為i,協(xié)議描述如下:

步驟1 Bob準(zhǔn)備一個(gè)量子序列,每個(gè)量子隨機(jī)地處于狀態(tài)|0〉,|1〉,|0′〉和|1′〉這4個(gè)態(tài)之一.量子態(tài)|0〉和|1〉表示0,而量子態(tài)|0′〉和|1′〉表示1.然后發(fā)給Alice,這里

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

步驟2 Alice隨機(jī)選用基B={|0〉,|1〉}或者基B={|0′〉,|1′〉}來(lái)測(cè)量收到的量子.顯然,這次測(cè)量不會(huì)讓他推導(dǎo)出Bob所發(fā)量子比特的值.

步驟3 Alice隨后向Bob公布所檢測(cè)到的量子態(tài),而拋棄掉丟失的量子.顯然Alice不能有欺騙行為,因?yàn)锳lice還沒(méi)有從所發(fā)送的量子上得到任何信息,并且他不能從這次欺騙中獲益.因此,這個(gè)協(xié)議是容量子丟失的.

步驟4 對(duì)于Alice每次測(cè)量到的量子態(tài),Bob公布0或1,這里0代表這個(gè)量子開(kāi)始時(shí)處于態(tài)|0〉或者|0′〉,而1代表量子態(tài)是|1〉或者|1′〉.

步驟5 Alice根據(jù)他的測(cè)量結(jié)果和Bob公布的結(jié)果來(lái)判斷他在第1步的測(cè)量結(jié)果,他可以一定的概率p確定Bob所發(fā)的量子.例如,如果Bob公布值是0,而他在步驟2測(cè)量結(jié)果為|1〉,他只有用基B測(cè)量才可以排除|0〉,推斷出最開(kāi)始所發(fā)的量子態(tài)為|0′〉,其值為1.因此,對(duì)于Bob的公布,Alice測(cè)量到正確結(jié)果的概率p=sin2θ2,不確定的概率為1-p.所有測(cè)量確定的和不確定的結(jié)果都保存下來(lái).通過(guò)這種方式, Alice和Bob共享一個(gè)初始密鑰字符串Kr.Bob知道Kr中所有的值,而Alice只知道一部分(整個(gè)的sin2θ2).

步驟6 Bob只向Alice發(fā)送N個(gè)量子,然后停止發(fā)送.讓這N個(gè)量子作為初始密鑰Kr={k1,k2,…,kN}.Bob知道Kr中所有的值,而Alice確定其中大約Np個(gè)比特.然后對(duì)初始密鑰Kr進(jìn)行稀釋,使Alice擁有確定的比特?cái)?shù)減少為一個(gè)或幾個(gè).雙方進(jìn)行的運(yùn)算為

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

經(jīng)過(guò)初始密鑰Kr的稀釋,形成了一個(gè)新的長(zhǎng)度為N的密匙K={k′1,k′2,…,k′N}.如果Alice此時(shí)沒(méi)得到一個(gè)正確的比特,則協(xié)議重新開(kāi)始.不過(guò)由隨后的討論可知,這種情況發(fā)生的概率非常小.

步驟7 Alice現(xiàn)在準(zhǔn)確地知道密鑰K中最少一個(gè)比特,假定為第j位元素kj,而他想檢索數(shù)據(jù)庫(kù)M中的第i位Mi.Alice為了能正確地譯碼,他向Bob公布數(shù)字s=j-i,Bob得到s后,對(duì)K移s位后得到新的密匙K′.用K′對(duì)M進(jìn)行加密,可以得到加密后的數(shù)據(jù)庫(kù)M′=M⊕K′.將M′公布給Alice,Alice通過(guò)計(jì)算Mi=M′j⊕K′j,就可以得到他想查詢的數(shù)據(jù)Mi.

當(dāng)θ=π/4,k=2,N=20時(shí),Alice檢索數(shù)據(jù)庫(kù)中檢索號(hào)i=2的實(shí)現(xiàn)過(guò)程見(jiàn)表1.

表1 一次量子私有信息檢索協(xié)議的檢索實(shí)現(xiàn)過(guò)程

2 可行性分析

在步驟6中,Alice在對(duì)初始密鑰進(jìn)行稀釋時(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′＜N時(shí),協(xié)議才是可行的.故假定有事件X,當(dāng)X=1時(shí),代表測(cè)量準(zhǔn)確,發(fā)生的概率為p;當(dāng)X=0時(shí),代表測(cè)不準(zhǔn),發(fā)生的概率為1-p.計(jì)算當(dāng)首次出現(xiàn)X連續(xù)k次為1時(shí),總發(fā)生次數(shù)的數(shù)學(xué)期望uk.考慮如下情形:首次出現(xiàn)連續(xù)k-1次1,此時(shí)總次數(shù)的期望為uk-1.再測(cè)一次,結(jié)果有且只有以下兩種:

(A) 出現(xiàn)1,則滿足條件,所用次數(shù)的數(shù)學(xué)期望為uk-1+1.

(B) 出現(xiàn)0,則立即回到初始狀態(tài),相當(dāng)于又要從零開(kāi)始出現(xiàn)k次連續(xù)1,因此總次數(shù)的數(shù)學(xué)期望為uk-1+1+uk.

A、B兩種情況的概率分別為p,1-p.因此,有

化簡(jiǎn)后可得

顯然,此為一遞推數(shù)列.u1=1/p,可求得通項(xiàng)公式

其中,t=1/p,p=sin2θ/2.由式(6)知,uk是由θ和k共同來(lái)決定的.圖1給出了當(dāng)θ=π/6,π/5和π/4時(shí),由式(6)求得的uk隨k的變化曲線示意圖.可以看出,k值越大,uk越大;在k值相同時(shí),θ小的uk要大一些.

顯然,只要合適地對(duì)θ和k取值,使uk滿足N＞uk,協(xié)議就可以進(jìn)行下去.相應(yīng)地,Alice在步驟6結(jié)束后,所能得到最終密鑰K中確定的比特?cái)?shù)n約等于Nuk.將式(6)代入,可得

其中,t=1/p,p=sin2θ/2.在N和θ一定的條件下,k的取值如果過(guò)大,使N＜uk,則會(huì)有很大的概率連一個(gè)確定的比特也得不到,協(xié)議就得重新開(kāi)始;而k的取值如果太小,則Alice能確定最終密鑰K中的比特?cái)?shù)n又會(huì)太多,會(huì)造成數(shù)據(jù)庫(kù)信息的過(guò)多泄露.一個(gè)理想的k值應(yīng)使Alice測(cè)量得到正確原始密鑰K中一個(gè)或者很少幾個(gè)比特.表2給出了理想情況下,當(dāng)θ為π/6,π/5和π/4時(shí),在不同的數(shù)據(jù)庫(kù)大小N下,k的取值和對(duì)應(yīng)的n的關(guān)系.可以看出,在相同的數(shù)據(jù)庫(kù)下,θ越大,需要做的異或次數(shù)k就會(huì)增加.

為了保證一次檢索的成功率,碰到n只有1個(gè)多比特的時(shí)候,可適當(dāng)?shù)卣{(diào)整θ和k去增加n.例如表2中,當(dāng)θ=π/4,N=105,k=8時(shí),n=1.1,故此時(shí)可取θ=0.74,k=7,對(duì)應(yīng)的n=2.4.通過(guò)以上對(duì)θ和k取值方法的討論,可以看出本協(xié)議在步驟6結(jié)束后,由于Alice在最終密鑰中得不到一個(gè)確定量子比特,使協(xié)議重新開(kāi)始的概率很小.

圖1 不同的θ取值下,uk隨k的變化曲線

表2 在理想情況下,不同數(shù)據(jù)庫(kù)大小N下,k和n的取值

3 性能分析

可知概率增加了.圖3就是正常測(cè)量概率和最優(yōu)非歧義態(tài)區(qū)分測(cè)量后,Alice測(cè)量正確結(jié)果的概率的對(duì)比圖.當(dāng)θ較小時(shí),p和pUSD相差不多;隨著θ增大,兩者的差越來(lái)越大.因此,合適地選取θ,可以保證數(shù)據(jù)庫(kù)的隱私.

表3就是θ為π/6和π/4時(shí),Alice正常測(cè)量和最優(yōu)非歧義態(tài)區(qū)分測(cè)量確定比特?cái)?shù)對(duì)比.可以看出,當(dāng)θ較小

3.1 靈活性分析

在G協(xié)議和本協(xié)議中,對(duì)于任意的數(shù)據(jù)庫(kù),可以通過(guò)調(diào)節(jié)θ和k來(lái)獲得一個(gè)任意想要的Alice測(cè)量得到正確原始密鑰的比特?cái)?shù)n(n?N).但在G協(xié)議中,k是直接影響通信復(fù)雜度的.在檢索大型數(shù)據(jù)庫(kù)時(shí),要保持一個(gè)好的通信復(fù)雜度,即要k值小,則必須采用一個(gè)很小的θ,實(shí)現(xiàn)起來(lái)將會(huì)十分困難.在本協(xié)議中,k已經(jīng)不影響通信復(fù)雜度了,所以就不必去為了降低量子通信復(fù)雜度而采用一個(gè)非常小的θ,增加實(shí)現(xiàn)難度.圖2給出了當(dāng)N=104,n≈3和N=106,n≈5時(shí),由式(7)得到的k和θ的關(guān)系曲線.所以與G協(xié)議相比,本協(xié)議更加靈活,特別在檢索大型數(shù)據(jù)庫(kù)時(shí),效率更高.

3.2隱私安全性分析

3.2.1 數(shù)據(jù)庫(kù)的安全性

圖2 不同的數(shù)據(jù)庫(kù)N和n時(shí),k和θ的關(guān)系曲線

如果Alice是非誠(chéng)實(shí)用戶,他將收到的所有量子比特都存儲(chǔ)下來(lái),就能夠在步驟4中Bob公布完后進(jìn)行有效的測(cè)量.然后采用非歧義態(tài)區(qū)分(Unambiguous State Discrimination,USD)測(cè)量,由文獻(xiàn)[9]的分析可知,采用最優(yōu)非歧義態(tài)區(qū)分測(cè)量后,Alice測(cè)量正確結(jié)果的概率pUSD=1-cosθ,由時(shí),p和pUSD相差很小,例如當(dāng)θ=π/6時(shí),p=0.125, pUSD=0.134,使用最優(yōu)非歧義態(tài)區(qū)分測(cè)量確定的最終密鑰的比特?cái)?shù)nUSD增加不多.而θ越大,即θ=π/4時(shí),p=0.25, pUSD=0.29,p和pUSD相差變大,使用最優(yōu)非歧義態(tài)區(qū)分測(cè)量增加的確定比特?cái)?shù)nUSD也越來(lái)越多.故從加強(qiáng)數(shù)據(jù)庫(kù)安全這個(gè)角度出發(fā),應(yīng)該選取較小的θ.

此外,筆者給出的協(xié)議為了提高協(xié)議的成功率,當(dāng)Alice測(cè)量的確定的比特?cái)?shù)n只有1個(gè)多比特時(shí),調(diào)整θ和k,增加n,造成數(shù)據(jù)庫(kù)信息泄露量增加很少.這也是為了提高協(xié)議成功率所付出的代價(jià).

圖3 正常測(cè)量和最優(yōu)非歧義態(tài)區(qū)分測(cè)量的概率比較

表3 正常測(cè)量和非歧義態(tài)區(qū)分測(cè)量確定比特?cái)?shù)對(duì)比

筆者提出的協(xié)議主要是產(chǎn)生密鑰的方法與G協(xié)議不同,但同樣能達(dá)到數(shù)據(jù)庫(kù)安全性的要求.

3.2.2 用戶的隱私

本協(xié)議中Alice的測(cè)量結(jié)果是靠量子非正交態(tài)測(cè)不準(zhǔn)和量子態(tài)不可克隆基本物理原理來(lái)保證的,所以Bob不可能在發(fā)送正確數(shù)據(jù)的同時(shí)還知道Alice的查詢索引,這個(gè)原因與文獻(xiàn)[7]中的一樣.

對(duì)于參數(shù)θ,Bob猜出Alice的檢索地址的概率pc=cos2(θ/2)[9].參數(shù)θ越小,pc越大,Bob越容易猜出Alice的檢索地址.特別地,當(dāng)檢索的數(shù)據(jù)庫(kù)比較小時(shí),如果θ也取得很小,像N=50,θ=0.6,此時(shí)k只能等于1.很明顯,Alice進(jìn)行檢索時(shí),步驟7中最終密鑰無(wú)須進(jìn)行移位,所以Bob就很容易地知道Alice的檢索地址.故從加強(qiáng)用戶隱私性這個(gè)角度去看,應(yīng)該選取大一些的θ.

當(dāng)數(shù)據(jù)庫(kù)比較小時(shí),可以將θ增大,加強(qiáng)Alice的隱私性,相應(yīng)地泄露給Alice的數(shù)據(jù)庫(kù)比特?cái)?shù)也增多.而數(shù)據(jù)庫(kù)很大時(shí),這時(shí)可以適當(dāng)減小θ來(lái)提高數(shù)據(jù)庫(kù)的安全性.故從數(shù)據(jù)庫(kù)的安全性和用戶的隱私兩個(gè)方面綜合考慮,通常在θ=π/4附近隨機(jī)取值.

3.3 復(fù)雜度分析

關(guān)于協(xié)議的通信復(fù)雜度.在G協(xié)議中,Bob至少需要發(fā)送k N個(gè)量子比特作為密鑰,并且k隨著數(shù)據(jù)庫(kù)N增大而增大,故綜合可知,執(zhí)行一次檢索,通信復(fù)雜度大約為O(N log N)[10].而對(duì)于筆者所提協(xié)議,可以看到總共只需要發(fā)送N個(gè)量子比特,故通信復(fù)雜度達(dá)到了O(N).

再看協(xié)議所需的計(jì)算復(fù)雜度.在G協(xié)議中,在Alice方面,測(cè)量量子需要計(jì)算量為kN,在密鑰稀釋階段所需計(jì)算量為kN,在解密階段計(jì)算量為N.在Bob方面,在密鑰稀釋階段所需計(jì)算量為kN,最后數(shù)據(jù)庫(kù)加密階段計(jì)算量為N,總共需要計(jì)算量大約等于(3k+2)N.筆者提出的協(xié)議中,Alice測(cè)量量子需要計(jì)算量為N,故最后計(jì)算量大約等于(2k+3)N,約減小了(k-1)N.當(dāng)檢索的數(shù)據(jù)庫(kù)規(guī)模N越大時(shí),節(jié)約的數(shù)據(jù)處理時(shí)間越多.

4 總 結(jié)

以上提出的量子私有信息檢索協(xié)議在進(jìn)行密鑰稀釋時(shí),通過(guò)對(duì)初始密鑰中連續(xù)的k個(gè)比特進(jìn)行異或,使量子信道發(fā)送的量子長(zhǎng)度只有N,從而使通信復(fù)雜度達(dá)到最優(yōu)的O(N);在檢索大小不同的數(shù)據(jù)庫(kù)時(shí),通過(guò)合適地調(diào)節(jié)輔助參數(shù)θ和k,既提高了成功率,又可滿足安全性的要求.故本協(xié)議復(fù)雜度低,靈活性好,一次檢索成功率高,易于實(shí)現(xiàn).

[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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-12-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(61372076);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(K5051301021,K5051301022);高等學(xué)校創(chuàng)新引智計(jì)劃資助項(xiàng)目(B08038)

賀小云(1977-),男,西安電子科技大學(xué)博士研究生,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