王育齊，佘 堃

1.電子科技大學(xué) 信息與軟件工程學(xué)院，成都 610054

2.閩南師范大學(xué) 計算機(jī)學(xué)院，福建 漳州 363000

通用的量子同態(tài)加密框架*

王育齊1,2+，佘 堃1

1.電子科技大學(xué) 信息與軟件工程學(xué)院，成都 610054

2.閩南師范大學(xué) 計算機(jī)學(xué)院，福建 漳州 363000

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

研究了量子同態(tài)加密，提出了一種通用的構(gòu)造量子同態(tài)加密算子的方法，進(jìn)而建立了構(gòu)造量子同態(tài)加密方案的一種通用框架；通過二值和三值量子態(tài)的酉變換，利用該框架構(gòu)造了相應(yīng)的量子同態(tài)加密方案，與現(xiàn)有文獻(xiàn)的構(gòu)造方案相比，利用該框架構(gòu)造的量子同態(tài)加密方案更具有普遍性；通過安全性分析，該框架的安全性是基于加密算法的安全性和密鑰的安全性。由于該框架采用了對稱量子加密算法，導(dǎo)致構(gòu)造量子同態(tài)算子時需要加密密鑰,從而該框架是一種弱的對稱量子同態(tài)加密框架。最后，該框架被推廣到了量子公鑰加密的情形。

量子同態(tài)加密；量子同態(tài)算子；量子代理計算；對稱量子加密；量子密碼

1 引言

在一個分布式開放環(huán)境中，假定用戶擁有一些私密的量子態(tài)數(shù)據(jù)，比如在線購物記錄、信用卡消費(fèi)記錄等。局限于用戶的計算能力（比如昂貴的量子計算機(jī)），用戶能否將自己的計算任務(wù)安全地委托給第三方（擁有量子計算機(jī)）進(jìn)行？回答是肯定的，盲量子計算（blind quantum computation，BQC）[1-10]和量子同態(tài)加密（quantum homomorphic encryption，QHE）[11-18]就可以很好地完成用戶委托的量子計算。本文將采用QHE的方式實(shí)現(xiàn)用戶的委托計算，進(jìn)而推導(dǎo)出通用的QHE框架。

首先，Rohde等人[11]基于量子漫步（quantumwalks），提出了第一個受限的QHE方案；Liang[12]首次給出了QHE和QFHE的定義，并且基于量子一次一密（quantum one-time pad，QOTP），構(gòu)造了信息理論安全的對稱QHE方案；隨后，基于通用量子線路（universal quantum circuit，UQC），Liang又提出了一個量子全同態(tài)加密（quantum full homomorphic encryption，QFHE）方案[13]。在該方案中，評估函數(shù)獨(dú)立于加密密鑰，而解密密鑰則是通過一個迭代過程，從加密密鑰中計算出來的；最近，Liang等人[14]基于量子容錯結(jié)構(gòu)（quantum fault-tolerant construction），提出了兩個QFHE方案，其中一個是使用了量子糾錯碼和輔助量子態(tài)的對稱QFHE方案，另外一個則是非對稱的QFHE，它需要一個交互過程協(xié)助完成。

Tan等人[15]利用算子子群的中心化子，提出了一個私鑰的QHE方案，該方案可以在加密的量子數(shù)據(jù)上執(zhí)行一大類的量子計算任務(wù)，而且是信息理論安全的；Ouyang等人[16]針對任意經(jīng)典和量子的線路，只要這些線路包含不超過一固定數(shù)目的non-Clifford門，他們構(gòu)造了基于這些線路的QHE方案；Broadbent等人[17]基于低復(fù)雜度的T-Gates構(gòu)成的線路，提出了兩個QHE方案；最近，Wang等人[18]基于三值量子門，結(jié)合三值量子門的擬合，提出了對稱的三值QHE方案，該方案采用了對稱加密方式。

以上這些研究都是基于某些特定的量子邏輯門，構(gòu)造了相應(yīng)的QHE方案。本文結(jié)合QHE的基本定義和以上的研究成果，提出了構(gòu)造量子同態(tài)算子（quantum homomorphic operator，QHO）的一般性方法，進(jìn)而建立了設(shè)計QHE方案的通用框架。通過二值和三值的兩個例子，證明了該框架的正確性，與現(xiàn)有文獻(xiàn)相比，方案更具有普適性。通過安全性分析，本文框架是一個弱的對稱QHE框架。“弱”是指QHE中的加密算法，在三值量子態(tài)中還沒有對應(yīng)的信息理論安全的加密算法。

2 量子同態(tài)加密

一個QHE方案由四部分構(gòu)成[12]：密鑰產(chǎn)生算法、加密算法、解密算法和評估算法。和一般的量子加密算法相比，QHE多了一個評估算法。該算法的作用是構(gòu)造相應(yīng)的量子同態(tài)算子，并在加密數(shù)據(jù)上執(zhí)行這些同態(tài)算子。當(dāng)用戶對其輸出執(zhí)行解密操作時，將得到相應(yīng)操作在明文態(tài)上執(zhí)行的結(jié)果。

對于一個QHE方案來說，該四部分是相互獨(dú)立的，對其進(jìn)行替換（主要是加解密算法），不影響QHE的執(zhí)行。因此設(shè)計一個QHE方案，主要有兩個問題要解決：（1）設(shè)計加解密算法；（2）設(shè)計可以構(gòu)造同態(tài)算子的評估函數(shù)。重點(diǎn)在于第二個問題，即根據(jù)用戶指定的操作，如何構(gòu)造一個在用戶加密數(shù)據(jù)上可以執(zhí)行的同態(tài)算子，是設(shè)計QHE方案的關(guān)鍵性問題。

同態(tài)算子是根據(jù)用戶想要在明文執(zhí)行的操作，由評估函數(shù)構(gòu)造出來的，可以在用戶加密數(shù)據(jù)上執(zhí)行，而且執(zhí)行過程不需要解密過程，從而確保了用戶數(shù)據(jù)的私密性；當(dāng)用戶對評估函數(shù)的輸出結(jié)果進(jìn)行解密時，將得到自己想要在明文上執(zhí)行操作的結(jié)果，確保了委托計算的正確性；根據(jù)加密方式，若為量子私鑰加密（即對稱量子加密），則假定代理方是誠信的，因?yàn)樵u估函數(shù)的執(zhí)行需要加密密鑰（即解密密鑰），所以在這種情況下稱其為弱的QHE。若為量子公鑰加密（即非對稱量子加密），則評估函數(shù)是獨(dú)立于解密密鑰的。相對于前者，后者的適用范圍更廣，且數(shù)據(jù)私密性保護(hù)得更好。

3 QHE框架

3.1 框架描述

假定ρc和σm是密文和明文的量子態(tài)表示形式，KeyGenA是密鑰產(chǎn)生算法，EncryptA是加密算法，DecryptA是解密算法，EualuateA是評估算法，UΔ是一組可允許執(zhí)行的量子操作集合，存在一個U∈UΔ，密鑰 k∈{KeyGenΔ},則有 ρc=EncryptA(σm,k)和 σm= DecryptA(ρc,k)。EvaluateA的描述如下：根據(jù)用戶指定的酉變換U和密鑰k，評估函數(shù)計算出一個在用戶加密數(shù)據(jù)上可執(zhí)行的同態(tài)算子U′，在這個計算過程中沒有執(zhí)行DecryptA算法，而且假定了EvaluateA的執(zhí)行方（也叫代理）是誠信的。

在量子邏輯線路中，所有的邏輯門都是可逆的，這一點(diǎn)不同于經(jīng)典邏輯門。因此，對于評估函數(shù)的輸出結(jié)果，結(jié)合對稱加密和量子邏輯門可逆性的特點(diǎn)，將QHE方案表述為：

該式說明，同態(tài)算子U′作用在量子密文態(tài)ρc上的結(jié)果（記為U′ρc），等價于對原始操作U作用在量子明文態(tài)σm上的結(jié)果（記為Uσm）進(jìn)行加密。所以說，用戶只要對評估函數(shù)的輸出進(jìn)行解密，即可得到原始操作U作用在量子明文態(tài)σm上的結(jié)果，即：

而且從式（1）還可以推導(dǎo)出關(guān)于同態(tài)算子U′的公式，即：

對于式（3），在同態(tài)算子U′的計算過程中，有如下幾點(diǎn)說明：（1）代理方需要知道用戶的加密密鑰；（2）沒有調(diào)用解密過程DecryptA；（3）假定代理方是誠信的；（4）加密算子都是酉矩陣，注意矩陣運(yùn)算規(guī)則?；谇叭c(diǎn)，在量子同態(tài)算子的構(gòu)造過程中，用戶數(shù)據(jù)的私密性得到了很好的保護(hù)，而且代理方會正確執(zhí)行用戶的委托計算，滿足QHE的定義（請參照文獻(xiàn)[12,19-20]）。

通過式（3），可以根據(jù)用戶指定的量子操作（也叫酉變換，該變換作用于量子明文態(tài)），構(gòu)造出作用于量子密文態(tài)的同態(tài)算子（也是一種酉變換），使得用戶只需解壓評估函數(shù)的輸出態(tài)，就可以得到指定操作在量子明文態(tài)上的結(jié)果。評估函數(shù)不僅實(shí)現(xiàn)了用戶委托的量子計算，而且完成了針對用戶指定量子酉變換的QHE方案的設(shè)計。

綜上所述，把式（3）稱為構(gòu)造量子同態(tài)操作的一般性方法（即評估函數(shù)的設(shè)計），進(jìn)而建立起設(shè)計QHE方案的通用框架。當(dāng)然，該框架可以推廣至量子公鑰加密體系，如下列3個等式所示：

其中，pk和sk分別代表量子公鑰加密體系中的公鑰和私鑰。從式（6）可以得到，推廣后的非對稱的QHE框架中，計算量子同態(tài)算子的過程只需要加密密鑰而不需要解密密鑰，而且是獨(dú)立于解密過程的。它不再需要假定代理方是誠信的，擴(kuò)大了QHE方案的適用范圍。相比較于式（3）的對稱QHE框架，式（6）的非對稱QHE框架，具有更高的安全性和更廣闊的適用范圍。

3.2 兩個實(shí)例

依據(jù)該框架（參照式（3）），以二值和三值量子態(tài)為例，來說明該框架在二值和三值情況下，由該框架推導(dǎo)出的QHE方案與現(xiàn)有文獻(xiàn)提出的是等價的。

4 安全性分析

對于一個QHE方案來說，它的安全性可以從兩個方面進(jìn)行分析。首先是加密算法的安全性。在該框架中，由于采用了對稱加密算法，導(dǎo)致評估函數(shù)在計算相應(yīng)的量子同態(tài)操作時，一個是要假定代理方是誠信的，另外還需要加密密鑰，這就導(dǎo)致數(shù)據(jù)有泄密的可能性（因?yàn)榧咏饷苊荑€是一樣的）。就對稱加密算法本身來說，二值情況下，文獻(xiàn)[21]提供一個信息理論安全的量子一次一密方案。但是在三值情況下，目前還沒有一個信息理論安全的對稱量子加密方案。當(dāng)該模型推廣至量子公鑰加密體系下時，代理方是否誠信和可能的數(shù)據(jù)泄密就不存在了，這無疑會提高QHE方案的安全性和適用范圍。

最后，分析該框架中的密鑰安全性。首先，該框架中的加解密密鑰都是只使用一次的，類似于一次一密方案。密鑰串的獲取可以通過文獻(xiàn)[22]中介紹的基于重發(fā)機(jī)制的量子密鑰分發(fā)協(xié)議得到，而且分發(fā)過程是無條件安全的。其次，基于量子測不準(zhǔn)原理和量子不可克隆原理，任何強(qiáng)行測量未知量子態(tài)的做法，都只能得到一些隨機(jī)的量子比特串，而非私密信息。最后，只要密鑰的擁有者不泄露密鑰的任何私密信息的話，任何竊聽者都將無法獲得有效的私密信息。另外，由評估函數(shù)構(gòu)造的量子同態(tài)算子（只有代理方知道）作用于用戶加密數(shù)據(jù)，相當(dāng)于二次加密，這無疑增加了竊聽者獲取有效信息的難度。

綜上所述，本文構(gòu)造的QHE框架在二值量子態(tài)下是信息理論安全的，但在三值量子態(tài)下，卻是弱安全性的。主要原因是在三值情況下缺乏信息理論安全的對稱量子加密方案。但當(dāng)將其推廣至量子公鑰加密體系下后，該框架將能夠獲得信息理論安全的QHE方案。

5 結(jié)束語

QHE方案可以實(shí)現(xiàn)委托的量子計算，主要是指代理方可以構(gòu)造出基于用戶加密密鑰和指定操作的同態(tài)算子，使其作用在用戶加密數(shù)據(jù)上。當(dāng)用戶對評估函數(shù)的輸出結(jié)果進(jìn)行解密時，用戶將得到原始操作在明文態(tài)上執(zhí)行的效果。這個過程中沒有執(zhí)行數(shù)據(jù)解密操作，保護(hù)了數(shù)據(jù)的私密性，實(shí)現(xiàn)了用戶的委托計算。本文通過構(gòu)造基于用戶加密密鑰和指定操作（一種酉變換）的量子同態(tài)算子的一般性方法，提出了一種設(shè)計對稱QHE方案的通用框架，并將其推廣到量子公鑰加密的情況。通過二值和三值量子態(tài)酉變換，構(gòu)造了相應(yīng)的同態(tài)操作，驗(yàn)證了對稱QHE框架的正確性。通過對加密算法本身和密鑰源的安全性進(jìn)行分析，該框架是一種弱的對稱QHE框架。但將其推廣后，則是一種信息理論安全的非對稱QHE框架。尋找量子公鑰加密算法和優(yōu)化評估函數(shù)，設(shè)計高效安全的QHE或QFHE方案，將是下一階段研究的主要目標(biāo)。

[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.

附中文參考文獻(xiàn)：

[22]王育齊,佘堃.基于重發(fā)機(jī)制的量子密鑰分發(fā)協(xié)議[J].計算機(jī)工程與設(shè)計,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—），男，甘肅西和人，電子科技大學(xué)信息與軟件工程學(xué)院博士研究生，閩南師范大學(xué)計算機(jī)學(xué)院講師，主要研究領(lǐng)域?yàn)榱孔有畔⑻幚恚孔用艽a。

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年于電子科技大學(xué)獲得博士學(xué)位，現(xiàn)為電子科技大學(xué)信息與軟件工程學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)樾畔踩?，云計算，量子密碼。

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(國家自然科學(xué)基金);the Program of Education Department of Fujian Province under Grant No.JA15321(福建省教育廳項(xiàng)目);the Key Technology Support Program of Sichuan Province under Grant No.2015GZ0102(四川省科技支撐計劃).

Received 2016-05,Accepted 2016-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.014.html