偏振旋轉(zhuǎn)的量子私有信息檢索方案

易運(yùn)暉 朱暢華 裴昌幸 權(quán)東曉

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

1 引言

隨著互聯(lián)網(wǎng)的發(fā)展，互聯(lián)網(wǎng)中用戶信息的安全性逐步受到重視。特別是在商業(yè)競(jìng)爭(zhēng)、金融和軍事等特殊場(chǎng)合下，用戶隱私的安全性要求更加嚴(yán)格。私有信息檢索(Private Information Retrieval, PIR)是文獻(xiàn)[1]于1995年提出的問(wèn)題，目的是保護(hù)用戶檢索數(shù)據(jù)庫(kù)中數(shù)據(jù)時(shí)自身的信息不泄露。PIR是安全多方計(jì)算的一個(gè)分支，在安全多方計(jì)算的數(shù)據(jù)庫(kù)安全查詢、匿名認(rèn)證等領(lǐng)域有著廣闊的前景。

私有信息檢索模型中，服務(wù)器Bob擁有Nbit數(shù)據(jù)：q1,q2,… ,qN，用戶Alice從Bob的數(shù)據(jù)庫(kù)中檢索索引為i( 1 ≤i≤N)的數(shù)據(jù)qi時(shí)，需要保護(hù)Alice的隱私，也就是使服務(wù)器Bob無(wú)法得知i。為保護(hù)用戶隱私，最直接但無(wú)意義的解決方案就是Bob把數(shù)據(jù)q1,q2,… ,qN都傳給Alice，由Alice自己完成檢索。但這個(gè)方案使數(shù)據(jù)庫(kù)Bob的隱私?jīng)]有任何安全性，這一般是不允許的。1998年，Gertner等人[2]提出了對(duì)稱私有信息檢索(Symmetrically Private Information Retrieval, SPIR)協(xié)議，在保護(hù)用戶隱私的基礎(chǔ)上，同時(shí)保護(hù)數(shù)據(jù)庫(kù)內(nèi)容的隱私安全，并證明了PIR可以在一定條件下轉(zhuǎn)化為k個(gè)服務(wù)器的SPIR。信息論安全的私有信息檢索可以在計(jì)算能力不受限制的條件下有效地保護(hù)隱私，但是此類模型通常需要多個(gè)互不通信的數(shù)據(jù)庫(kù)副本，不僅空間復(fù)雜度高，而且現(xiàn)實(shí)中為保證數(shù)據(jù)庫(kù)副本的一致，致使這種假設(shè)通常很難成立。因此，只需要一個(gè)服務(wù)器的計(jì)算安全的私有信息檢索成為研究熱點(diǎn)[3-5]。

量子信息學(xué)是近20年發(fā)展起來(lái)，由量子力學(xué)、信息科學(xué)和計(jì)算機(jī)科學(xué)相結(jié)合的新型交叉學(xué)科。目前已有的計(jì)算安全的私有信息檢索大都基于公鑰密碼學(xué)或一些附加的計(jì)算困難性假設(shè)，而這些基礎(chǔ)在量子計(jì)算機(jī)制下變得非常脆弱，其安全性受到挑戰(zhàn)。2004年，文獻(xiàn)[6]將量子信息處理應(yīng)用到PIR中，提出了量子對(duì)稱私有信息檢索(QSPIR)技術(shù)，其后文獻(xiàn)[7,8]對(duì)多種量子私有信息檢索技術(shù)進(jìn)行了研究。與傳統(tǒng)SPIR相比，QSPIR都是無(wú)條件也就是信息論安全的，但相關(guān)的研究一般都基于半誠(chéng)實(shí)模型，且還未見(jiàn)具體實(shí)施方案。本文利用目前比較成熟的單光子態(tài)，結(jié)合量子密鑰分發(fā)[9](Quantum Key Distribution, QKD)和量子安全直傳[10,11](Quantum Secure Direct Communication, QSDC)試驗(yàn)平臺(tái)，設(shè)計(jì)了“非誠(chéng)實(shí)合作模型”下的QSPIR協(xié)議及其實(shí)現(xiàn)方案，在安全性、魯棒性、抗竊聽(tīng)等方面均優(yōu)于經(jīng)典環(huán)境中的各類SPIR方案。

2 整體方案

設(shè)單光子原始量子態(tài)φ=a0 +b1，信道中單光子偏振角度的旋轉(zhuǎn)角度為δ，通過(guò)信道后量子態(tài)為φ'，則有

設(shè)對(duì)φ'測(cè)量結(jié)果正確的概率為P，則

既當(dāng)對(duì)發(fā)送方的單光子偏振角度旋轉(zhuǎn)δ后，接收方能夠以 cos2δ的概率正確收到發(fā)送方的信息[12]，而發(fā)送方不知道接收方正確收到的是哪些數(shù)據(jù)。本文利用上述特點(diǎn)以及量子不可克隆、測(cè)不準(zhǔn)原理(不確定性)等特點(diǎn)，設(shè)計(jì)了基于單光子的QSPIR協(xié)議。實(shí)驗(yàn)方案如圖1所示，服務(wù)器和計(jì)算機(jī)通過(guò)量子信道和經(jīng)典信道2個(gè)信道完成信息檢索。量子信道中，用戶Alice控制發(fā)端電路產(chǎn)生相應(yīng)的光脈沖，光脈沖經(jīng)過(guò)偏振濾鏡和衰減器后形成單光子，Alice通過(guò)電控偏振控制器PC1進(jìn)行偏振編碼，再通過(guò)電控偏振控制器PC2對(duì)編碼后的單光子進(jìn)行偏振旋轉(zhuǎn)。攜帶著信息的光子通過(guò)量子信道傳輸?shù)竭_(dá)接收端，經(jīng)電控偏振控制器PC3再次偏振旋轉(zhuǎn)后，通過(guò)偏振分束器(PBS)送入單光子探測(cè)器(SPD)，這樣服務(wù)器Bob在同步脈沖的控制下就完成了量子信息的接收。同時(shí)，為了保證接收端的嚴(yán)格同步，使SPD的探測(cè)窗口在單光子到來(lái)時(shí)刻同步打開，服務(wù)器通過(guò)激光源發(fā)出的同步光脈沖信號(hào)經(jīng)稀疏波分復(fù)用器(CWDM)復(fù)用到光纖信道上，用于控制接收方的開啟門。此外，服務(wù)器Bob和用戶Alice通過(guò)經(jīng)典信道完成余信息的交互。

圖1 QPIR系統(tǒng)原理框圖

3 協(xié)議流程

假設(shè)用戶Alice要從服務(wù)器Bob中檢索數(shù)據(jù)，數(shù)據(jù)庫(kù)中數(shù)據(jù)數(shù)為N, Alice檢索的索引為i，則偏振旋轉(zhuǎn)量子對(duì)稱私有信息檢索(PR-QSPIR)協(xié)議的執(zhí)行步驟如下：

(1)Alice提交檢索申請(qǐng)后，Bob任意選擇一個(gè)角度θ0作為基本的角度并向 Alice公布，雙方都可以得到含M個(gè)偏振旋轉(zhuǎn)角度的集合θ,θ= {θm=θ0+(m- 1 )[π/(2M)]|m= 1 ,2,3,… ,M}。

(2) Alice準(zhǔn)備隨機(jī)序列{an}和{bn}, Bob準(zhǔn)備隨機(jī)序列{cn}。這3個(gè)序列長(zhǎng)度均為L(zhǎng)(L＞N)，其中C=L-N為信道檢測(cè)所需的比特?cái)?shù)。{an}序列中元素取值為0或1; {bn}為Alice端偏振旋轉(zhuǎn)角度隨機(jī)序列；{cn}為Bob端偏振旋轉(zhuǎn)角度隨機(jī)序列，其中bn,cn∈θ。

(3) Alice對(duì)信息序列{an}按照0對(duì)應(yīng)于H, 1對(duì)應(yīng)于V的規(guī)則進(jìn)行編碼，也就是控制PC1為0°或者90°；同時(shí)按照{(diào)bn}控制PC2的偏振旋轉(zhuǎn)角度，亦即對(duì)光子進(jìn)行R(bn)變換。

(4) Bob根據(jù)同步對(duì)收到光子進(jìn)行編號(hào)。為驗(yàn)證信道的安全性，Bob從接收的光子中隨機(jī)選取L-N個(gè)比特作為校驗(yàn)序列，通知Alice自己已經(jīng)收到校驗(yàn)序列光子的序號(hào)并要求 Alice公布對(duì)應(yīng)的{an}和{bn}，并對(duì)光子進(jìn)行偏振控制和測(cè)量，得到測(cè)量結(jié)果{dn}，然后根據(jù){an}和{dn}計(jì)算誤碼率驗(yàn)證信道的安全性；如果信道不安全則放棄此次檢索。在確認(rèn)信道安全后，Bob檢測(cè) Alice是否誠(chéng)實(shí)，也就是檢測(cè)Alice公布序列的隨機(jī)性，如果偏差太大，則認(rèn)為Alice不誠(chéng)實(shí)，放棄此次檢索。

N=6,C=4,M=2時(shí)，Alice需要檢索檢索號(hào)i=1的協(xié)議實(shí)現(xiàn)過(guò)程見(jiàn)表 1。Alice最后可以確定{an} ⊕ {kn}的第1個(gè)比特為0，但其它位都不確定，這樣就可以從Bob發(fā)送過(guò)來(lái)的{qn}中取得自己所需的比特q1，但并不知道其它比特是否正確。同時(shí)，Bob沒(méi)有得到Alice索引的任何信息。

4 性能分析

目前，多數(shù)PIR 模型中假設(shè)用戶Alice和服務(wù)器Bob是誠(chéng)實(shí)的，都會(huì)嚴(yán)格正確地執(zhí)行協(xié)議，但在協(xié)議完成后雙方會(huì)試圖從中間結(jié)果中獲取額外的隱私消息，也就是常說(shuō)的半誠(chéng)實(shí)模型。

本文中在半誠(chéng)實(shí)模型的基礎(chǔ)上，構(gòu)造了更為真實(shí)的“非誠(chéng)實(shí)合作”模型。也就是說(shuō)Alice, Bob都可能試圖不遵守協(xié)議來(lái)獲取更多的信息，但不阻止協(xié)議的執(zhí)行，主要假設(shè)如下：

(1) Alice和Bob都試圖合作完成本次檢索，因此不用假的數(shù)據(jù)欺騙對(duì)方，也就是說(shuō)Alice提交的索引和Bob給出的數(shù)據(jù)都是真實(shí)的。

(2) Alice和Bob都足夠聰明，可能試圖在不影響協(xié)議執(zhí)行的情況下，改變中間的數(shù)據(jù)來(lái)獲得對(duì)方的隱私，但不采取會(huì)影響協(xié)議執(zhí)行的舉動(dòng)。比如，其中一方若不采取{θn} 做為偏振旋轉(zhuǎn)角度的集合則會(huì)導(dǎo)致檢索到錯(cuò)誤的數(shù)據(jù)，因此雙方都不會(huì)采取這種行為。

(3)Alice和Bob都足夠理智，不以放棄自己的隱私為目的獲取對(duì)方的數(shù)據(jù)。

4.1 隱私安全分析

由于用戶 Alice隨機(jī)產(chǎn)生且不公布有效的{an}和{bn}，而且Bob的測(cè)量結(jié)果是由量子力學(xué)測(cè)不準(zhǔn)原理保證的，因此Bob不能多次測(cè)量或者從測(cè)量結(jié)果{dn}中得到用戶索引的任何信息。同時(shí)，Alice傳遞的j-i是 Alice根據(jù) Bob公布的{cn}計(jì)算出的{bn-cn}而得到的，由于不能得到{bn}，所以Bob也不能從中得到索引i的任何信息。因此，即使Bob是非誠(chéng)實(shí)的，在步驟(6)欺騙Alice產(chǎn)生更多的數(shù)據(jù)，也無(wú)法得到索引的信息，用戶Alice的隱私是嚴(yán)格保密的。

表1 PR-QSPIR協(xié)議的實(shí)現(xiàn)過(guò)程

由于最終的數(shù)據(jù)庫(kù)擾碼{kn}是Bob測(cè)量后的結(jié)果，因此Bob為保證隱私不被泄露，一定會(huì)保證的隨機(jī)性；同時(shí)，校驗(yàn)序列是Bob隨機(jī)抽取且要求Alice公布的，所以如果Alice的隨機(jī)性太偏離要求的概率分布，Bob也會(huì)發(fā)現(xiàn) Alice的不誠(chéng)實(shí)，導(dǎo)致檢索失敗，因此 Alice的序列隨機(jī)性不會(huì)太偏離要求。這樣即使Alice采用對(duì)自己有利的{an}和{bn}，由于量子測(cè)不準(zhǔn)的原理，也只能提高互信息量，而不能獲得Bob的測(cè)量結(jié)果，也就是無(wú)法獲得{kn}，這樣Bob的數(shù)據(jù)是具有私密性的。

分析協(xié)議可知，Alice可以由{an},{bn}和{cn}分析{dn}，特別是當(dāng){bn}和{cn}對(duì)應(yīng)項(xiàng)相同時(shí)，Alice一定能夠知道{dn}的相應(yīng)數(shù)據(jù)。所以，本協(xié)議中Bob的隱私并不是完全安全的，會(huì)有少量信息泄露。下面我們分析Alice能夠得到的最大信息量。

這樣Alice和Bob的互信息量為

由于Alice隨機(jī)選擇0,1，所以

而信道轉(zhuǎn)移概率

因此，

圖2是I(A,B)隨M變化的曲線，由圖中可以看出當(dāng)M＞20以后，互信息量變化就很小，因此當(dāng)N較小時(shí)，應(yīng)使N·I(A,B)大于1，保證平均每次檢索都有1個(gè)比特可以匹配；當(dāng)N較大時(shí)不妨取M為20，這時(shí)I(A,B) ≈ 0 .123, Alice所能得到Bob的最大信息量約為N/8，此時(shí)可以采用密性放大來(lái)保護(hù)Bob的隱私。

圖2 I( A, B)和M的關(guān)系

因此，對(duì)于數(shù)據(jù)庫(kù)Bob來(lái)說(shuō)這種方案的隱私雖然不是嚴(yán)格保密的(Alice存在知道多個(gè)比特的可能性)，但具有好的隱私安全性。

4.2 第三方竊聽(tīng)安全性分析

根據(jù)量子力學(xué)的原理，Eve不可能在不影響非正交的兩個(gè)量子態(tài)的基礎(chǔ)上，分辨兩個(gè)量子態(tài)，從而使Alice和Bob在檢測(cè)過(guò)程中發(fā)現(xiàn)錯(cuò)誤，導(dǎo)致竊聽(tīng)被發(fā)現(xiàn)。假如竊聽(tīng)者Eve使用探針與Alice的量子態(tài)相互作用完成測(cè)量或者Eve采取替換光子的方法，則必然不可避免地要干擾光子狀態(tài)，必然會(huì)在檢測(cè)過(guò)程中發(fā)現(xiàn)錯(cuò)誤，從而被發(fā)現(xiàn)。拒絕服務(wù)攻擊是指Eve只是對(duì)光子進(jìn)行隨機(jī)的操作來(lái)破壞傳輸?shù)男畔?，則也必然會(huì)擾亂光子的狀態(tài)，通過(guò)檢測(cè)過(guò)程也是可以發(fā)現(xiàn)的。因此在數(shù)據(jù)傳送前，Eve的竊聽(tīng)都會(huì)被發(fā)現(xiàn)，這樣Eve不能獲取任何一方的有效數(shù)據(jù)。

4.3 復(fù)雜度分析

整個(gè)協(xié)議在量子密鑰分發(fā)協(xié)議(QKD)的基礎(chǔ)上改動(dòng)很小，其通信復(fù)雜度和量子密鑰分發(fā)協(xié)議相同。因此本協(xié)議在結(jié)合了私有信息檢索和量子密鑰的基礎(chǔ)上，通信復(fù)雜度基本保持不變。

為計(jì)算協(xié)議所需計(jì)算量C，不妨取L=2N。按照協(xié)議流程，計(jì)算量主要是在(4), (7), (8), (9)幾個(gè)步驟，其中第(4)步進(jìn)行校驗(yàn)所需運(yùn)算量為L(zhǎng)-N=N；第(7)步進(jìn)行比較所需運(yùn)算量為N+1；第(8)步加密所需運(yùn)算量為N；第(9)步解密所需運(yùn)算量為N。

則有C=N+ (N+1) +N+N= 4N+1。

因此協(xié)議的運(yùn)算復(fù)雜度為O(N)，比目前的私有信息檢索協(xié)議復(fù)雜度高。但本文協(xié)議不需要復(fù)雜的運(yùn)算，只需要簡(jiǎn)單的異或運(yùn)算(判決相等也可以用異或?qū)崿F(xiàn))，可以直接硬件實(shí)現(xiàn)。

5 結(jié)論

(1)本文基于量子單光子提出 PR-QSPIR實(shí)驗(yàn)方案，協(xié)議是無(wú)條件安全或者說(shuō)是信息論安全；方案不需要量子存儲(chǔ)器，便于硬件實(shí)現(xiàn)。(2)本文提出了非誠(chéng)實(shí)合作模型，設(shè)計(jì)了PR- QSPIR協(xié)議，能夠有效檢測(cè)和防止雙方的不誠(chéng)實(shí)舉s動(dòng)。(3)采用量子態(tài)作為有效的檢測(cè)機(jī)制，具有更高的安全性和更強(qiáng)的魯棒性。

[1]Benny C, Oded G, Eyal K,et al.. Private information retrieval[C]. IEEE 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, USA, October 23, 1995:41-50.

[2]Gertner Y, Ishai Y, Eyal K,et al.. Protecting data privacy in private information retrieval schemes[C]. 13th Annual ACM Symposium on Theory of Computing, Dallas, TX, USA, May 23-26, 1998: 151-160.

[3]Ryan H, Femi O, and Ian G. Practical PIR for electronic commerce[C]. 18th ACM Conference on Computer and Communications Security, Chicago, IL, USA, October 17,2011: 677-689.

[4]Zhong Hong, Yi Lei, Yu Zhao,et al.. Fully-homomorphic encryption based SPIR[C]. 2011 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), Wuhan, China, Sept. 23-25, 2011:3-6.

[5]Toru N, Shunsuke I, Daisuke I,et al.. Anonymous authentication systems based on private information retrieval[C]. 1st International Conference on Networked Digital Technologies, Ostrava, Czech Republic, July 28, 2009:53-58.

[6]Iordanis K and Wolf D. Quantum symmetrically-private information retrieval[J].Information Processing Letter, 2004,90(5): 109-114.

[7]Vittorio G, Seth L, Cone M,et al.. Quantum private queries:security analysis[J].IEEE Transactions on Information Theory, 2010, 56(7): 3465-3477.

[8]Lukasz O. Secure quantum private information retrieval using phase-encoded queries[J].Physical Review A-Atomic,Molecular, and Optical Physics, 2011, 84(8): 022313-022316.

[9]權(quán)東曉, 裴昌幸, 劉丹, 等. 基于單光子的單向量子安全通信協(xié)議[J]. 物理學(xué)報(bào), 2010, 59(4): 2493-2497.

Quan Dong-xiao, Pei Chang-xing, Liu Dan,et al.. One-way quantum secure direct communication protocol based on single photons[J].Acta Physics Sinica,2010, 59(4):2493-2497.

[10]趙生妹, 李苗苗, 鄭寶玉. 一種基于量子糾錯(cuò)編碼的量子密鑰分配協(xié)議[J]. 電子與信息學(xué)報(bào), 2009, 31(4): 954-957.

Zhao Sheng-mei, Li Miao-miao, and Zheng Bao-yu. A novel quantum key distribution protocol based on quantum error correction code[J].Journal of Electronics&Information Technology,2009, 31(4): 954-957.

[11]Liu Dan, Pei Chang-xing, Quan Dong-xiao,et al.. A new quantum secure direct communication scheme with authentication[J].Chinese Physics Letter, 2010, 27(5):050306.

[12]劉丹, 裴昌幸, 權(quán)東曉. 測(cè)量基對(duì) BB84協(xié)議安全性影響[J].電子與信息學(xué)報(bào), 2011, 33(1): 228-230.

Liu Dan, Pei Chang-xing, and Quan Dong-xiao.Measurement bases impact on the security of BB84 protocol[J].Journal of Electronics&Information Technology,2011, 33(1): 228-230.