APP下载

通用的量子同态加密框架*

2016-11-22王育齐

计算机与生活 2016年11期
关键词:同态加密算法算子

王育齐,佘 堃

1.电子科技大学 信息与软件工程学院,成都 610054

2.闽南师范大学 计算机学院,福建 漳州 363000

通用的量子同态加密框架*

王育齐1,2+,佘 堃1

1.电子科技大学 信息与软件工程学院,成都 610054

2.闽南师范大学 计算机学院,福建 漳州 363000

WANG Yuqi,SHE Kun.Universal quantum homomorphic encryption framework.Journal of Frontiers of Computer Science and Technology,2016,10(11):1571-1576.

研究了量子同态加密,提出了一种通用的构造量子同态加密算子的方法,进而建立了构造量子同态加密方案的一种通用框架;通过二值和三值量子态的酉变换,利用该框架构造了相应的量子同态加密方案,与现有文献的构造方案相比,利用该框架构造的量子同态加密方案更具有普遍性;通过安全性分析,该框架的安全性是基于加密算法的安全性和密钥的安全性。由于该框架采用了对称量子加密算法,导致构造量子同态算子时需要加密密钥,从而该框架是一种弱的对称量子同态加密框架。最后,该框架被推广到了量子公钥加密的情形。

量子同态加密;量子同态算子;量子代理计算;对称量子加密;量子密码

1 引言

在一个分布式开放环境中,假定用户拥有一些私密的量子态数据,比如在线购物记录、信用卡消费记录等。局限于用户的计算能力(比如昂贵的量子计算机),用户能否将自己的计算任务安全地委托给第三方(拥有量子计算机)进行?回答是肯定的,盲量子计算(blind quantum computation,BQC)[1-10]和量子同态加密(quantum homomorphic encryption,QHE)[11-18]就可以很好地完成用户委托的量子计算。本文将采用QHE的方式实现用户的委托计算,进而推导出通用的QHE框架。

首先,Rohde等人[11]基于量子漫步(quantumwalks),提出了第一个受限的QHE方案;Liang[12]首次给出了QHE和QFHE的定义,并且基于量子一次一密(quantum one-time pad,QOTP),构造了信息理论安全的对称QHE方案;随后,基于通用量子线路(universal quantum circuit,UQC),Liang又提出了一个量子全同态加密(quantum full homomorphic encryption,QFHE)方案[13]。在该方案中,评估函数独立于加密密钥,而解密密钥则是通过一个迭代过程,从加密密钥中计算出来的;最近,Liang等人[14]基于量子容错结构(quantum fault-tolerant construction),提出了两个QFHE方案,其中一个是使用了量子纠错码和辅助量子态的对称QFHE方案,另外一个则是非对称的QFHE,它需要一个交互过程协助完成。

Tan等人[15]利用算子子群的中心化子,提出了一个私钥的QHE方案,该方案可以在加密的量子数据上执行一大类的量子计算任务,而且是信息理论安全的;Ouyang等人[16]针对任意经典和量子的线路,只要这些线路包含不超过一固定数目的non-Clifford门,他们构造了基于这些线路的QHE方案;Broadbent等人[17]基于低复杂度的T-Gates构成的线路,提出了两个QHE方案;最近,Wang等人[18]基于三值量子门,结合三值量子门的拟合,提出了对称的三值QHE方案,该方案采用了对称加密方式。

以上这些研究都是基于某些特定的量子逻辑门,构造了相应的QHE方案。本文结合QHE的基本定义和以上的研究成果,提出了构造量子同态算子(quantum homomorphic operator,QHO)的一般性方法,进而建立了设计QHE方案的通用框架。通过二值和三值的两个例子,证明了该框架的正确性,与现有文献相比,方案更具有普适性。通过安全性分析,本文框架是一个弱的对称QHE框架。“弱”是指QHE中的加密算法,在三值量子态中还没有对应的信息理论安全的加密算法。

2 量子同态加密

一个QHE方案由四部分构成[12]:密钥产生算法、加密算法、解密算法和评估算法。和一般的量子加密算法相比,QHE多了一个评估算法。该算法的作用是构造相应的量子同态算子,并在加密数据上执行这些同态算子。当用户对其输出执行解密操作时,将得到相应操作在明文态上执行的结果。

对于一个QHE方案来说,该四部分是相互独立的,对其进行替换(主要是加解密算法),不影响QHE的执行。因此设计一个QHE方案,主要有两个问题要解决:(1)设计加解密算法;(2)设计可以构造同态算子的评估函数。重点在于第二个问题,即根据用户指定的操作,如何构造一个在用户加密数据上可以执行的同态算子,是设计QHE方案的关键性问题。

同态算子是根据用户想要在明文执行的操作,由评估函数构造出来的,可以在用户加密数据上执行,而且执行过程不需要解密过程,从而确保了用户数据的私密性;当用户对评估函数的输出结果进行解密时,将得到自己想要在明文上执行操作的结果,确保了委托计算的正确性;根据加密方式,若为量子私钥加密(即对称量子加密),则假定代理方是诚信的,因为评估函数的执行需要加密密钥(即解密密钥),所以在这种情况下称其为弱的QHE。若为量子公钥加密(即非对称量子加密),则评估函数是独立于解密密钥的。相对于前者,后者的适用范围更广,且数据私密性保护得更好。

3 QHE框架

3.1 框架描述

假定ρc和σm是密文和明文的量子态表示形式,KeyGenA是密钥产生算法,EncryptA是加密算法,DecryptA是解密算法,EualuateA是评估算法,UΔ是一组可允许执行的量子操作集合,存在一个U∈UΔ,密钥 k∈{KeyGenΔ},则有 ρc=EncryptA(σm,k)和 σm= DecryptA(ρc,k)。EvaluateA的描述如下:根据用户指定的酉变换U和密钥k,评估函数计算出一个在用户加密数据上可执行的同态算子U′,在这个计算过程中没有执行DecryptA算法,而且假定了EvaluateA的执行方(也叫代理)是诚信的。

在量子逻辑线路中,所有的逻辑门都是可逆的,这一点不同于经典逻辑门。因此,对于评估函数的输出结果,结合对称加密和量子逻辑门可逆性的特点,将QHE方案表述为:

该式说明,同态算子U′作用在量子密文态ρc上的结果(记为U′ρc),等价于对原始操作U作用在量子明文态σm上的结果(记为Uσm)进行加密。所以说,用户只要对评估函数的输出进行解密,即可得到原始操作U作用在量子明文态σm上的结果,即:

而且从式(1)还可以推导出关于同态算子U′的公式,即:

对于式(3),在同态算子U′的计算过程中,有如下几点说明:(1)代理方需要知道用户的加密密钥;(2)没有调用解密过程DecryptA;(3)假定代理方是诚信的;(4)加密算子都是酉矩阵,注意矩阵运算规则。基于前三点,在量子同态算子的构造过程中,用户数据的私密性得到了很好的保护,而且代理方会正确执行用户的委托计算,满足QHE的定义(请参照文献[12,19-20])。

通过式(3),可以根据用户指定的量子操作(也叫酉变换,该变换作用于量子明文态),构造出作用于量子密文态的同态算子(也是一种酉变换),使得用户只需解压评估函数的输出态,就可以得到指定操作在量子明文态上的结果。评估函数不仅实现了用户委托的量子计算,而且完成了针对用户指定量子酉变换的QHE方案的设计。

综上所述,把式(3)称为构造量子同态操作的一般性方法(即评估函数的设计),进而建立起设计QHE方案的通用框架。当然,该框架可以推广至量子公钥加密体系,如下列3个等式所示:

其中,pk和sk分别代表量子公钥加密体系中的公钥和私钥。从式(6)可以得到,推广后的非对称的QHE框架中,计算量子同态算子的过程只需要加密密钥而不需要解密密钥,而且是独立于解密过程的。它不再需要假定代理方是诚信的,扩大了QHE方案的适用范围。相比较于式(3)的对称QHE框架,式(6)的非对称QHE框架,具有更高的安全性和更广阔的适用范围。

3.2 两个实例

依据该框架(参照式(3)),以二值和三值量子态为例,来说明该框架在二值和三值情况下,由该框架推导出的QHE方案与现有文献提出的是等价的。

4 安全性分析

对于一个QHE方案来说,它的安全性可以从两个方面进行分析。首先是加密算法的安全性。在该框架中,由于采用了对称加密算法,导致评估函数在计算相应的量子同态操作时,一个是要假定代理方是诚信的,另外还需要加密密钥,这就导致数据有泄密的可能性(因为加解密密钥是一样的)。就对称加密算法本身来说,二值情况下,文献[21]提供一个信息理论安全的量子一次一密方案。但是在三值情况下,目前还没有一个信息理论安全的对称量子加密方案。当该模型推广至量子公钥加密体系下时,代理方是否诚信和可能的数据泄密就不存在了,这无疑会提高QHE方案的安全性和适用范围。

最后,分析该框架中的密钥安全性。首先,该框架中的加解密密钥都是只使用一次的,类似于一次一密方案。密钥串的获取可以通过文献[22]中介绍的基于重发机制的量子密钥分发协议得到,而且分发过程是无条件安全的。其次,基于量子测不准原理和量子不可克隆原理,任何强行测量未知量子态的做法,都只能得到一些随机的量子比特串,而非私密信息。最后,只要密钥的拥有者不泄露密钥的任何私密信息的话,任何窃听者都将无法获得有效的私密信息。另外,由评估函数构造的量子同态算子(只有代理方知道)作用于用户加密数据,相当于二次加密,这无疑增加了窃听者获取有效信息的难度。

综上所述,本文构造的QHE框架在二值量子态下是信息理论安全的,但在三值量子态下,却是弱安全性的。主要原因是在三值情况下缺乏信息理论安全的对称量子加密方案。但当将其推广至量子公钥加密体系下后,该框架将能够获得信息理论安全的QHE方案。

5 结束语

QHE方案可以实现委托的量子计算,主要是指代理方可以构造出基于用户加密密钥和指定操作的同态算子,使其作用在用户加密数据上。当用户对评估函数的输出结果进行解密时,用户将得到原始操作在明文态上执行的效果。这个过程中没有执行数据解密操作,保护了数据的私密性,实现了用户的委托计算。本文通过构造基于用户加密密钥和指定操作(一种酉变换)的量子同态算子的一般性方法,提出了一种设计对称QHE方案的通用框架,并将其推广到量子公钥加密的情况。通过二值和三值量子态酉变换,构造了相应的同态操作,验证了对称QHE框架的正确性。通过对加密算法本身和密钥源的安全性进行分析,该框架是一种弱的对称QHE框架。但将其推广后,则是一种信息理论安全的非对称QHE框架。寻找量子公钥加密算法和优化评估函数,设计高效安全的QHE或QFHE方案,将是下一阶段研究的主要目标。

[1]Barz S,Kashefi E,Broadbent A,et al.Demonstration of blind quantum computing[J].Science,2012,335(6066):303-308.

[2]Barz S,Fitzsimons J F,Kashefi E,et al.Experimental verification of quantum computation[J].Nature Physics,2013,9 (11):727-731.

[3]Giovannetti V,Maccone L,Morimae T,et al.Efficient universal blind quantum computation[J].Physical Review Letters,2013,111(23):230501.

[4]Mantri A,Pérez-Delgado C A,Fitzsimons J F.Optimal blind quantum computation[J].Physical Review Letters,2013, 111(23):230502.

[5]Fitzsimons J F,Kashe E.Unconditionally verifiable blind computation[EB/OL].[2016-04-15].http://arXiv.org/abs/1203. 5217.

[6]Morimae T,Fujii K.Blind quantum computation protocol in which Alice only makes measurements[J].Physical ReviewA,2013,87:050301.

[7]Fisher K A G,Broadbent A,Shalm L K,et al.Quantum computing on encrypted data[J].Nature Communications,2014, 5:3074.

[8]BroadbentA,Fitzsimons J,Kashefi E.Universal blind quantum computation[C]//Proceeding of the 50th Annual IEEE Symposium on Foundations of Computer Science,Atlanta, USA,Oct 25-27,2009.Piscataway,USA:IEEE,2009:517-526.

[9]Arrighi P,Salvail L.Blind quantum computation[J].International Journal of Quantum Information,2006,4(5):883-898.

[10]Sueki T,Koshiba T,Morimae T.Ancilla-driven universal blind quantum computation[J].Physical Review A,2013, 87:060301.

[11]Rohde P P,Fitzsimons J F,Gilchrist A.Quantum walks with encrypted data[J].Physical Review Letters,2012,109:150501.

[12]Liang Min.Symmetric quantum fully homomorphic encryption with perfect security[J].Quantum Information Processing, 2013,12(12):3675-3687.

[13]Liang Min.Quantum fully homomorphic encryption scheme based on universal quantum circuit[J].Quantum Information Processing,2014,14(8):2749-2759.

[14]Liang Min,Yang Li.Quantum fully homomorphic encryption scheme based on quantum fault-tolerant construction [EB/OL].[2016-04-15].http://arXiv.org/abs/1503.04061v1.

[15]Tan S H,Kettlewell J A,Ouyang Y K,et al.A quantum approach to homomorphic encryption[J].Scientific Reports, 2016,6:33467.

[16]Ouyang Y K,Tan S H,Fitzsimons J F.Quantum homomorphic encryption from quantum codes[EB/OL].[2016-04-15]. http://arXiv.org/abs/1508.00938v2.

[17]Broadbent A,Jeffery S.Quantum homomorphic encryption for circuits of low t-gate complexity[C]//LNCS 9216:Proceedings of the 35th Annual Cryptology Conference,Santa Barbara,USA,Aug 16-20,2015.Berlin,Heidelberg:Springer,2015:609-629.

[18]Wang Yuqi,She Kun,Luo Qinbing,et al.Symmetric weak ternary quantum homomorphic encryption schemes[J].Modern Physics Letters B,2016,30(7):1650076.

[19]Gentry C.Computing arbitrary functions of encrypted data [J].Communications of theACM,2010,53(3):97-105.

[20]Gentry C,Halevi S.Implementing gentryƳs fully-homomorphic encryption scheme[C]//LNCS 6632:Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tallinn,Estonia,May 15-19,2011.Berlin,Heidelberg:Springer,2011:129-148.

[21]Boykin P O,Roychowdhury V.Optimal encryption of quantum bits[J].Physical ReviewA,2003,67:042317.

[22]Wang Yuqi,She Kun.Quantum key distribution protocol based on retransmission mechanism[J].Computer Engineering and Design,2015,36(11):2938-2942.

附中文参考文献:

[22]王育齐,佘堃.基于重发机制的量子密钥分发协议[J].计算机工程与设计,2015,36(11):2938-2942.

WANG Yuqi was born in 1976.He is a Ph.D.candidate at School of Information and Software Engineering,University of Electronic Science and Technology of China,and a lecturer at College of Computer,Minnan Normal University. His research interests include quantum information processing and quantum cryptogram.

王育齐(1976—),男,甘肃西和人,电子科技大学信息与软件工程学院博士研究生,闽南师范大学计算机学院讲师,主要研究领域为量子信息处理,量子密码。

SHE Kun was born in 1967.He received the Ph.D.degree from University of Electronic Science and Technology of China in 2006.Now he is a professor and Ph.D.supervisor at School of Information and Software Engineering, University of Electronic Science and Technology of China.His research interests include information security, cloud computing and quantum cryptogram.

佘堃(1967—),男,四川成都人,2006年于电子科技大学获得博士学位,现为电子科技大学信息与软件工程学院教授、博士生导师,主要研究领域为信息安全,云计算,量子密码。

Universal Quantum Homomorphic Encryption Frameworkƽ

WANG Yuqi1,2+,SHE Kun1
1.School of Information and Software Engineering,University of Electronic Science and Technology of China, Chengdu 610054,China
2.College of Computer,Minnan Normal University,Zhangzhou,Fujian 363000,China
+Corresponding author:E-mail:paiter_w@126.com

Through studying quantum homomorphic encryption,this paper proposes a general construction method for quantum homomorphic operator,thus sets up a universal construction framework for quantum homomorphic encryption scheme.Compared with existing quantum homomorphic encryption schemes,the schemes constructed by the universal construction framework according to the binary and ternary quantum unitary transformations,are more feasible. This paper analyzes the security of the universal framework from two respects.One is the security of quantum encryption scheme.The other is the security of the secret key.In the universal construction framework,the symmetric quantum encryption scheme is used and the evaluation algorithm is dependent on the secret key in the process of constructing the corresponding quantum homomorphic operator.As a result,the universal construction framework is a kind of weak symmetric quantum homomorphic encryption framework.Finally,it is generalized to the case of the quantum public key encryption.

quantum homomorphic encryption;quantum homomorphic operator;quantum delegated computation; symmetric quantum encryption;quantum cryptography

10.3778/j.issn.1673-9418.1606032

A

TP393.04

*The National Natural Science Foundation of China under Grant Nos.61272175,61572109(国家自然科学基金);the Program of Education Department of Fujian Province under Grant No.JA15321(福建省教育厅项目);the Key Technology Support Program of Sichuan Province under Grant No.2015GZ0102(四川省科技支撑计划).

Received 2016-05,Accepted 2016-07.

CNKI网络优先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.014.html

猜你喜欢

同态加密算法算子
与由分数阶Laplace算子生成的热半群相关的微分变换算子的有界性
拟微分算子在Hp(ω)上的有界性
关于半模同态的分解*
各向异性次Laplace算子和拟p-次Laplace算子的Picone恒等式及其应用
拉回和推出的若干注记
一类Markov模算子半群与相应的算子值Dirichlet型刻画
一种基于LWE的同态加密方案
HES:一种更小公钥的同态加密算法
基于小波变换和混沌映射的图像加密算法
对称加密算法RC5的架构设计与电路实现