偏振旋转的量子私有信息检索方案

易运晖 朱畅华 裴昌幸 权东晓

(西安电子科技大学综合业务网理论与关键技术国家重点实验室 西安 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.