偏振旋轉的量子私有信息檢索方案

易運暉 朱暢華 裴昌幸 權東曉

(西安電子科技大學綜合業務網理論與關鍵技術國家重點實驗室 西安 710071)

1 引言

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

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

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

2 整體方案

設單光子原始量子態φ=a0 +b1，信道中單光子偏振角度的旋轉角度為δ，通過信道后量子態為φ'，則有

設對φ'測量結果正確的概率為P，則

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

圖1 QPIR系統原理框圖

3 協議流程

假設用戶Alice要從服務器Bob中檢索數據，數據庫中數據數為N, Alice檢索的索引為i，則偏振旋轉量子對稱私有信息檢索(PR-QSPIR)協議的執行步驟如下：

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

(2) Alice準備隨機序列{an}和{bn}, Bob準備隨機序列{cn}。這3個序列長度均為L(L＞N)，其中C=L-N為信道檢測所需的比特數。{an}序列中元素取值為0或1; {bn}為Alice端偏振旋轉角度隨機序列；{cn}為Bob端偏振旋轉角度隨機序列，其中bn,cn∈θ。

(3) Alice對信息序列{an}按照0對應于H, 1對應于V的規則進行編碼，也就是控制PC1為0°或者90°；同時按照{bn}控制PC2的偏振旋轉角度，亦即對光子進行R(bn)變換。

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

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

4 性能分析

目前，多數PIR 模型中假設用戶Alice和服務器Bob是誠實的，都會嚴格正確地執行協議，但在協議完成后雙方會試圖從中間結果中獲取額外的隱私消息，也就是常說的半誠實模型。

本文中在半誠實模型的基礎上，構造了更為真實的“非誠實合作”模型。也就是說Alice, Bob都可能試圖不遵守協議來獲取更多的信息，但不阻止協議的執行，主要假設如下：

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

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

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

4.1 隱私安全分析

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

表1 PR-QSPIR協議的實現過程

由于最終的數據庫擾碼{kn}是Bob測量后的結果，因此Bob為保證隱私不被泄露，一定會保證的隨機性；同時，校驗序列是Bob隨機抽取且要求Alice公布的，所以如果Alice的隨機性太偏離要求的概率分布，Bob也會發現 Alice的不誠實，導致檢索失敗，因此 Alice的序列隨機性不會太偏離要求。這樣即使Alice采用對自己有利的{an}和{bn}，由于量子測不準的原理，也只能提高互信息量，而不能獲得Bob的測量結果，也就是無法獲得{kn}，這樣Bob的數據是具有私密性的。

分析協議可知，Alice可以由{an},{bn}和{cn}分析{dn}，特別是當{bn}和{cn}對應項相同時，Alice一定能夠知道{dn}的相應數據。所以，本協議中Bob的隱私并不是完全安全的，會有少量信息泄露。下面我們分析Alice能夠得到的最大信息量。

這樣Alice和Bob的互信息量為

由于Alice隨機選擇0,1，所以

而信道轉移概率

因此，

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

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

因此，對于數據庫Bob來說這種方案的隱私雖然不是嚴格保密的(Alice存在知道多個比特的可能性)，但具有好的隱私安全性。

4.2 第三方竊聽安全性分析

根據量子力學的原理，Eve不可能在不影響非正交的兩個量子態的基礎上，分辨兩個量子態，從而使Alice和Bob在檢測過程中發現錯誤，導致竊聽被發現。假如竊聽者Eve使用探針與Alice的量子態相互作用完成測量或者Eve采取替換光子的方法，則必然不可避免地要干擾光子狀態，必然會在檢測過程中發現錯誤，從而被發現。拒絕服務攻擊是指Eve只是對光子進行隨機的操作來破壞傳輸的信息，則也必然會擾亂光子的狀態，通過檢測過程也是可以發現的。因此在數據傳送前，Eve的竊聽都會被發現，這樣Eve不能獲取任何一方的有效數據。

4.3 復雜度分析

整個協議在量子密鑰分發協議(QKD)的基礎上改動很小，其通信復雜度和量子密鑰分發協議相同。因此本協議在結合了私有信息檢索和量子密鑰的基礎上，通信復雜度基本保持不變。

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

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

因此協議的運算復雜度為O(N)，比目前的私有信息檢索協議復雜度高。但本文協議不需要復雜的運算，只需要簡單的異或運算(判決相等也可以用異或實現)，可以直接硬件實現。

5 結論

(1)本文基于量子單光子提出 PR-QSPIR實驗方案，協議是無條件安全或者說是信息論安全；方案不需要量子存儲器，便于硬件實現。(2)本文提出了非誠實合作模型，設計了PR- QSPIR協議，能夠有效檢測和防止雙方的不誠實舉s動。(3)采用量子態作為有效的檢測機制，具有更高的安全性和更強的魯棒性。

[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]權東曉, 裴昌幸, 劉丹, 等. 基于單光子的單向量子安全通信協議[J]. 物理學報, 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]趙生妹, 李苗苗, 鄭寶玉. 一種基于量子糾錯編碼的量子密鑰分配協議[J]. 電子與信息學報, 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]劉丹, 裴昌幸, 權東曉. 測量基對 BB84協議安全性影響[J].電子與信息學報, 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.