d 維量子同態(tài)加密算法的設(shè)計與仿真

宋秀麗，周道洋，曹耘凡

1.重慶郵電大學(xué) 網(wǎng)絡(luò)空間安全與信息法學(xué)院，重慶400065

2.重慶郵電大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，重慶400065

1 引言

隨著量子通信和量子計算的發(fā)展，人們對高維度量子存儲和計算能力的需求也在日益增長。鑒于客戶端存儲和計算能力有限，將數(shù)據(jù)存儲和計算任務(wù)委托給存儲能力大計算能力強的第三方服務(wù)器將成為一種趨勢，但是用戶數(shù)據(jù)安全是迫切需要解決的關(guān)鍵問題之一。在量子云環(huán)境中，假設(shè)客戶端需要完成一個超過他能力范圍的評估計算任務(wù)。客戶端首先對量子態(tài)明文進行加密，生成量子態(tài)密文，然后將量子態(tài)密文發(fā)送到服務(wù)器。服務(wù)器在不知道客戶端的加密密鑰的情況下對量子態(tài)密文執(zhí)行客戶端所需的評估計算，并將計算結(jié)果發(fā)送回客戶端。客戶端對其進行解密，解密結(jié)果正是客戶端對明文量子態(tài)所期望的評估計算。幸運的是，這種需求可以使用量子同態(tài)加密來實現(xiàn)。為了保證客戶數(shù)據(jù)的機密性，客戶數(shù)據(jù)的計算任務(wù)在加密后執(zhí)行。

經(jīng)典的同態(tài)加密最初是由Rivest等人[1]在1978年提出的。從那以后，人們提出了許多同態(tài)加密算法[2-6]。此外，一些同態(tài)加密算法已廣泛應(yīng)用于密碼學(xué)領(lǐng)域，如電子投票系統(tǒng)[7-8]、機密信息檢索協(xié)議[9-11]等。然而，隨著量子技術(shù)的發(fā)展，在量子計算機指數(shù)增長的強大計算能力下，這些基于數(shù)學(xué)困難的同態(tài)加密算法不足以保證量子云平臺中計算數(shù)據(jù)的機密性。

為了克服經(jīng)典同態(tài)加密算法的局限性，基于量子力學(xué)的基本原理提出了許多量子同態(tài)加密算法。文獻[12]基于通用量子線路提出了一種量子同態(tài)加密方案，該方案評估函數(shù)獨立于密鑰，但是該方案并沒有定義自己的評估酉算子而是借助于通用量子線路實現(xiàn)了同態(tài)變換；文獻[13]基于三值量子門提出了三值量子同態(tài)加密方案，但該方案局限于三維希爾伯特空間的討論；文獻[14]提出一種基于任意經(jīng)典和量子電路的量子同態(tài)加密，然而其量子電路不能超過一固定數(shù)目的non-Clifford門；文獻[15]介紹了基于編碼理論的同態(tài)加密方案的通用構(gòu)造原理，由于結(jié)構(gòu)原因只允許有限數(shù)量的加密；文獻[16]基于二維基本門算子構(gòu)造量子同態(tài)加密方案，同時給出了基于完全混合態(tài)分析的信息理論安全分析，然而其提出的評估算法不獨立于密鑰。文獻[17]基于低復(fù)雜度的T-Gates構(gòu)成的線路，提出了兩個量子同態(tài)加密方案；文獻[18]利用二維旋轉(zhuǎn)變換算子構(gòu)造一種量子同態(tài)加密方法，并在此基礎(chǔ)上加入搜索功能，擴展量子同態(tài)加密的應(yīng)用；文獻[19]基于量子容錯結(jié)構(gòu)提出兩種量子同態(tài)加密方案，這兩種方案需要額外的輔助量子態(tài)和者服務(wù)器與客戶端之間的交互。這些方案允許在不解密的情況下計算量子數(shù)據(jù)，確保了量子計算環(huán)境下數(shù)據(jù)的機密性。但是，這些量子同態(tài)加密的研究只關(guān)注于二維或三維希爾伯特空間，難以滿足量子態(tài)在自由空間擴展的需求。

為了滿足量子通信自由空間的發(fā)展，本文構(gòu)造了d( d ＞3) 維量子同態(tài)加密算法來克服低維量子空間的局限，給出了一種d 維酉算子的定義，并證明了任意兩個生成的酉算子的可交換性?；谟纤阕拥目山粨Q性，提出了兩種d 維量子同態(tài)加密算法。一種是單粒子上的量子同態(tài)加密算法，另一種是多粒子上的量子同態(tài)加密算法。所提出的量子同態(tài)加密算法與其他類似的量子同態(tài)加密算法[17-19]設(shè)計過程一樣簡單，同時d 維酉算子不會增加量子線路的額外復(fù)雜性。維度的擴展使得所提出的量子同態(tài)加密算法比其他類似的量子同態(tài)加密算法具有更好的通用性[12-16]。通過安全性分析，本文構(gòu)建的量子同態(tài)加密算法其輸出具有完全混合態(tài)特性，攻擊者在沒有事先探知明文信息分布的情況下無法獲取有關(guān)量子態(tài)輸出的任何有價值信息，這保證了本文算法的安全性。同時本文算法的評估子算法不依賴客戶端密鑰，獨立于客戶端，進一步增強了客戶端明文量子信息的安全性。

2 預(yù)備知識

為了能夠?qū)λ惴ǜ忧逦年U述，將介紹量子同態(tài)加密模型和d 維酉算子的定義。

定義1 量子同態(tài)加密包含以下四個子算法。

（1）密鑰生成子算法：由密鑰生成子算法KeyGenΔ隨機生成一個密鑰key。

（2）加密子算法：加密子算法EncryptΔ根據(jù)密鑰生成子算法產(chǎn)生的密鑰key，對量子明文態(tài)σ 進行加密操作，生成量子密文態(tài)ρ=EncryptΔ( key,σ )。

（3）評估子算法：評估子算法算法EvaluateΔ對量子態(tài)密文執(zhí)行相應(yīng)的評估計算ρ′=EvaluateΔ( C,ρ) ，其中C ∈FΔ，F(xiàn)Δ表示允許的量子操作集合。

（4）解密子算法：解密子算法DecryptΔ根據(jù)密鑰生成子算法生成的解密密鑰key 解密ρ′，得到對量子明文態(tài)的直接計算結(jié)果σ′=DecryptΔ( key ,ρ′)。

定義2 在d 維量子系統(tǒng)中，d 維酉算子定義如下：

另外，在d 維量子系統(tǒng)中，d 維加密解密酉算子X、Z 門定義如下：

為了對算法的安全性進行更好地分析，本文給出了算法的安全性定義，完全混合態(tài)[16，18，20]保證了算法的安全性。

定義3（安全性）如果對所有的輸入態(tài)φ，其輸出態(tài)φc是完全混合態(tài)，那么算法是安全的。其中輸入態(tài)φ與完全混合態(tài)φc關(guān)系如下：

其中φ 是所有可能輸入態(tài)的密度算法，Ua,b(a,b ∈(0,1,…,d-1))是在輸入態(tài)與輸出態(tài)之間所有的酉變換。

3 量子同態(tài)加密算法

根據(jù)定義1量子同態(tài)加密的定義，本文構(gòu)造了一個通用的量子同態(tài)加密模型，如圖1所示?？蛻舳死妹荑€生成子算法生成一個加密密鑰和解密密鑰，利用加密子算法對量子態(tài)明文進行加密生成量子態(tài)密文，然后通過量子安全信道將量子態(tài)密文發(fā)送給服務(wù)器。服務(wù)器收到量子態(tài)密文后，執(zhí)行評估子算法，并將計算結(jié)果發(fā)送回客戶端?？蛻舳私饷芊?wù)器發(fā)回評估操作結(jié)果得到評估計算的結(jié)果，該結(jié)果就是客戶端所期望計算結(jié)果。在圖1中，客戶端上通過密鑰生成子算法KeyGen△生成密鑰key，然后對量子明文狀態(tài)σ 進行加密生成密文態(tài)ρ。①表示客戶端將加密的量子態(tài)密文發(fā)送給服務(wù)器，獲取客戶端發(fā)送的數(shù)據(jù)后，服務(wù)器對該數(shù)據(jù)執(zhí)行評估子算法，并將輸出結(jié)果發(fā)送回客戶端。②表示服務(wù)器將評估計算結(jié)果發(fā)回給客戶端。最后客戶端解密由服務(wù)器計算的量子態(tài)密文數(shù)據(jù)，以獲得評估算子對量子態(tài)明文的直接計算結(jié)果C(σ)。

圖1 通用量子同態(tài)加密模型

3.1 d 維單粒子量子同態(tài)加密算法

根據(jù)定義1，本文提出一個d 維單粒子量子同態(tài)加密算法，包括以下四個子算法：

（1）密鑰生成子算法：在該算法中，客戶端根據(jù)需要將經(jīng)典明文信息編碼成量子態(tài)明文σ，然后通過密鑰生成子算法KeyGenΔ隨機生成兩個密鑰k,j ∈{0,1,…,d-1}，并保存。

（2）加密子算法：加密子算法算法EncryptΔ根據(jù)加密密鑰k,j，對量子態(tài)明文進行加密操作，生成量子態(tài)密文ρ=EncryptΔ( k,j,σ )=XkZjσ，最后，客戶端將加密的量子態(tài)密文通過量子安全信道發(fā)送給遠(yuǎn)端服務(wù)器。

（3）評估子算法：服務(wù)器在接收到客戶端發(fā)送過來的量子態(tài)密文之后，服務(wù)器根據(jù)其計算需求生成評估操作參數(shù)α、β，對接收到的量子態(tài)密文執(zhí)行評估操作ρ′=EvaluateΔ( α,β,ρ)=Uα,β·ρ，并將結(jié)果通過量子安全信道發(fā)送到客戶端。

（4）解密子算法：客戶端在接收到服務(wù)器發(fā)送回來的評估計算結(jié)果之后，使用解密子算法DecryptΔ根據(jù)其在密鑰生成階段保存的密鑰k,j 對其進行解密操作，

上述算法的量子線路圖如圖2所示。

圖2 單粒子算法量子線路圖

如圖2單粒子算法量子線路圖，在加密子算法中客戶端對輸入的量子態(tài)明文σ 使用密鑰生成子算法生成的密鑰k,j 進行加密，并將加密結(jié)果發(fā)送到服務(wù)器執(zhí)行評估計算Uα,β，最后將評估結(jié)果發(fā)回客戶端執(zhí)行解密操作最終得到對量子態(tài)明文σ 的直接計算結(jié)果Uα,βσ。評估算子Uα,β即為圖1中的允許的量子操作C。

在算法中巧妙的運用了d 維酉算子的可交換性，將評估操作算子與加密算子做等價乘法交換，完成同態(tài)加密。為了證明此算法的正確性，首先證明d 維酉算子的可交換性。

定理1 設(shè)Uα,β、Up,q是兩個任意d 維酉算子，其中α,β,p,q ∈{0 ,1 ,…,d-1}，它們具有可交換性。

證明兩算子的積表示為：

從等式（5）可以得出Uα,β·Up,q=Uα+p,β+q，因此Uα,β與Up,q之間的交換性更直觀地表示為：

因為Uα,β、Up,q是從等式（1）中隨機選擇的，所以任何兩個d 維酉算子都是可交換的。

根據(jù)定理1，下面將繼續(xù)對d 維單粒子量子同態(tài)加密算法的評估子算法和解密子算的正確性進行證明。

正確性1 根據(jù)定理1任意d 維酉算子的可交換性，下面證明評估子算法的正確性，當(dāng)評估算子作用在量子態(tài)密文ρ 上時，存在如下等式：

證明根據(jù)定理1任意兩個d 維酉算子之間的交換性質(zhì)，有：

因此當(dāng)評估算子作用在量子態(tài)密文ρ 上時，等同于將評估算子直接作用于量子態(tài)明文再加密，至此證明了評估子算法的正確性。

正確性2 解密子算法σ′=DecryptΔ( k,j,ρ′)=Uα,βσ是正確的。

證明根據(jù)定理1任意d 維酉算子的可交換性和正確性1 評估子算法同態(tài)變換結(jié)果，當(dāng)解密子算法DecryptΔ對評估子算法計算之后的量子態(tài)ρ′執(zhí)行解密操作時，有如下等式所示：

從等式（9）得知解密子算法是正確的。

以上定理1 任意d 維酉算子的可交換性、正確性1評估子算法同態(tài)變換結(jié)果和正確性2 解密子算法解密結(jié)果充分地證明了提出的d 維單粒子量子同態(tài)加密算法是正確的。為了具體說明算法的執(zhí)行過程，舉例如下。

例1 設(shè)維度d=7，量子態(tài)明文為，密鑰生成子算法生成的密鑰為k=2,j=5，評估參數(shù)α=1,β=6。經(jīng)過加密操作之后，量子態(tài)密文為：=對量子態(tài)密文操作之后結(jié)果為，最后使用解密子算法對評估結(jié)果解密操作之后得到結(jié)果，此解密結(jié)果與評估算子對量子態(tài)明文的直接計算結(jié)果完全一致，即。，使用評估算子

3.2 d 維多粒子量子同態(tài)加密算法

上一節(jié)給出了一種d 維單粒子上的量子同態(tài)加密算法，用來處理一個粒子上的同態(tài)計算。當(dāng)需要同時處理多個粒子時，就需要一種多粒子的量子同態(tài)加密算法。本節(jié)將構(gòu)造一種d 維多粒子量子同態(tài)加密算法，本方案包括以下四個子算法。

（1）密鑰生成子算法：密鑰生成子算法KeyGenΔ隨機產(chǎn)生2n 隨機密鑰，ki,ji∈{0 ,1 ,…,d-1} ，其中i=1,2,…,n，客戶端將經(jīng)典明文信息編碼成量子態(tài)明文σ1?σ2?…?σn。

（2）加密子算法：客戶端根據(jù)加密密鑰通過加密子算法EncryptΔ對量子態(tài)明文進行加密操作，生成量子態(tài)密文，并將量子態(tài)密文通過量子安全信道發(fā)送到遠(yuǎn)程服務(wù)器，請求其執(zhí)行評估計算任務(wù)。

（3）評估子算法：服務(wù)器收到量子態(tài)密文之后，首先生成評估操作參數(shù)αi,βi(i=0,1,…,n)，然后使用評估操作子算法EvaluateΔ對量子態(tài)密文進行評估計算，得到計算結(jié)果，并將計算結(jié)果通過量子安全信道發(fā)送回客戶端。

（4）解密子算法：客戶端得到服務(wù)器返回結(jié)果之后，通過解密子算法DecryptΔ使用解密密鑰ki,ji∈{0 ,1 ,…,d-1}，對其進行解密運算，σ′=DecryptΔ(k,j,ρ′)=，該結(jié)果就是對量子態(tài)明文的直接評估計算結(jié)果。

上述算法的量子線路圖如圖3 多粒子算法量子線路圖所示，客戶端在加密子算法中使用密鑰生成子算法產(chǎn)生的n 對密鑰ki,ji( i= 1,2,…,n )對n 個量子態(tài)明文σ1?…?σn執(zhí)行加密操作，并將加密結(jié)果發(fā)送到服務(wù)器分別執(zhí)行評估計算，最后將評估計算結(jié)果發(fā)回客戶端執(zhí)行解密操作，最終得到對n 個量子態(tài)明文的直接計算結(jié)果。評估算子即為圖1中的允許的量子操作C。

圖3 多粒子算法量子線路圖

接下來是對多粒子d 維量子同態(tài)加密算法的評估子算法和解密子算法正確性證明。

正確性3 評估操作過程ρ′=EvaluateΔ( αi, βi,ρ)=是正確的。

證明根據(jù)定理1任意d 維酉算子的可交換性和正確性1 單粒子評估子算法同態(tài)變換結(jié)果，當(dāng)評估算子作用在量子態(tài)密文ρ 上時，有：

結(jié)果等同于將評估算子直接作用于量子態(tài)明文再加密，所以評估操作過程是正確的。

正確性4 解密子算法DecryptΔ的過程σ′=DecryptΔ(ki,是正確的。

證明根據(jù)定理1任意d 維酉算子的可交換性和正確性3多粒子評估子算法同態(tài)變換結(jié)果，當(dāng)解密子算法對評估操作結(jié)果執(zhí)行解密運算時有：

解密結(jié)果正是評估算子對量子態(tài)明文的計算，所以根據(jù)等式（11）解密過程也是正確的。

經(jīng)過上述正確性證明，本文充分地說明了所提的第二個d 維多粒子量子同態(tài)加密算法的正確性。同理，為了更加清楚地闡述本方案的細(xì)節(jié)，舉例如下。

例2設(shè)粒子數(shù)n=3，維度d=7，量子態(tài)明文為σ1=，密鑰k1=1,j1=1,k2=2,j2=2,k3=3,j3=3，評估操作參數(shù)α1=4,β1=4,α2=5,β2=5,α3=6,β3=6，加密操作之后的量子態(tài)密文為，由評估子算法計算之后的結(jié)果，經(jīng)過解密子算法運算之后的結(jié)果為，此解密結(jié)果與評估操作算子作用于量子態(tài)明文的結(jié)果完全一致，即。

至此本文已經(jīng)完整的描述了關(guān)于d 維量子同態(tài)加密的算法，給出各自的正確性證明，并舉例驗證說明，證明了所提出的方案的正確性。正如所說，等式（6）和等式（9）的變換表明，定義的d 維酉算子的可交換性在兩個d 維量子同態(tài)加密算法中起著重要作用。接下來，將致力于討論算法的安全問題。

4 安全性分析

本章將對兩個d 維量子同態(tài)加密算法的安全性進行分析。

4.1 d 維單粒子量子同態(tài)加密算法安全性分析

更進一步，根據(jù)等式（12），在攻擊者面前，評估子算法的輸出同樣也是完全混合態(tài)，如等式（13）所示：

從等式（12）和等式（13）可以看出d 維單粒子量子同態(tài)加密算法的加密子算法和評估子算法輸出都是完全混合態(tài)，這意味著攻擊者無法通過混合態(tài)獲得客戶端或者服務(wù)器發(fā)送消息的任何有價值信息，因此d 維單粒子量子同態(tài)加密算法方案是安全的。

4.2 d 維多粒子量子同態(tài)加密算法安全性分析

同理，根據(jù)等式（12），面對攻擊者，d 維多粒子量子同態(tài)算法的加密子算法輸出態(tài)是d 維單粒子量子同態(tài)加密算法的加密輸出的張量積，也是完全混合狀態(tài)，如等式（14）所示：

此外，根據(jù)等式（13）和（14），d 維多粒子方案評估算法的輸出也是完全混合狀態(tài)，如等式（15）所示：

因此，d 維多粒子量子同態(tài)加密算法也是安全的。上述證明充分說明了在量子同態(tài)加密算法過程中所有可能的信息暴露點的輸出量子態(tài)均具有完全混合態(tài)性質(zhì)，這使得客戶端信息在傳送過程中即使被攻擊者截獲或者探測到，其仍然不能通過分析得到關(guān)于明文的任何有用信息。因此，本章所提出的d 維單粒子量子同態(tài)加密算法和d 維多粒子量子同態(tài)加密算法均是安全的。

5 仿真實驗

在本章中，將仿真實現(xiàn)本文所提出的兩個d 維量子同態(tài)加密算法，本仿真實現(xiàn)在經(jīng)典計算機上面按照量子力學(xué)規(guī)律通過C/C++語言對其運算邏輯進行仿真，并不涉及物理層面的實現(xiàn)。仿真實現(xiàn)模擬了算法從初始的密鑰生成階段產(chǎn)生密鑰及明文到通過加密算子加密，以及模擬同態(tài)計算及最后的解密過程。仿真過程主要模擬了方案在不同維度下，取不同量子態(tài)明文和不同的加密參數(shù)和評估參數(shù)對算法進行仿真，所有的仿真計算結(jié)果將顯示在表1 和表2 中。在仿真中，關(guān)于量子態(tài)維度的具體取值，實驗選擇了10、100、1 000和10 000附近的素數(shù)。

5.1 d 維單粒子量子同態(tài)加密算法仿真結(jié)果

在表1中，第一列中每一組數(shù)據(jù)記錄了當(dāng)前的維度d，加密密鑰k、j，評估參數(shù)α、β 及明文態(tài)σ。實驗中為了同態(tài)加密算法的安全性，密鑰和評估參數(shù)均是隨機產(chǎn)生。第二列表示的是每一組對應(yīng)數(shù)據(jù)下d 維單粒子量子同態(tài)加密算法的經(jīng)過解密子算法解密之后的結(jié)果。第三列表示每一組對應(yīng)數(shù)據(jù)中評估操作Uα,β對明文態(tài)σ 的直接計算結(jié)果。所有結(jié)果都精確到小數(shù)點后面的六位。

算法執(zhí)行結(jié)束時的解密結(jié)果和評估操作對明文直接計算結(jié)果列于表1 中。DecryptΔ( k,j,ρ′ )和Uα,β(σ )之間的歐式距離為0，這與該方案的計算結(jié)果高度一致。即使在高維度的情況下，它們的歐式距離仍然為0，計算結(jié)果與算法定義是一致的，表明該方案是正確的。

5.2 d 維多粒子量子同態(tài)加密方案仿真結(jié)果

表2 中，顯示的是d 維3 粒子的量子同態(tài)加密算法的仿真實驗結(jié)果。同一維度下，有3 個粒子，每個粒子有對應(yīng)的密鑰和評估參數(shù)及量子態(tài)明文。第一列表示量子空間的維度d，第二列表示每三個粒子一組對應(yīng)的參數(shù)，第三列表示解密子算法運行之后的結(jié)果，第四列表示每組評估算子對明文數(shù)據(jù)的直接計算結(jié)果。所有結(jié)果精確到小數(shù)點后六位。

當(dāng)每組3 粒子算法執(zhí)行結(jié)束之后，其解密結(jié)果DecryptΔ( ki,ji,ρ′i)和評估算子對明文的直接計算結(jié)果Uαi,βi( σi)之間的歐氏距離均為0。這與d 維多粒子量子同態(tài)加密算法的預(yù)期結(jié)果完全一致，這驗證了算法的推導(dǎo)是正確的。

6 結(jié)束語

本文提出的兩個d 維量子同態(tài)加密算法突破了兩維和三維低維度的限制，滿足量子通信自由空間的發(fā)展趨勢，具有較強的通用性。

本文首先定義了d 維酉算子，并引用量子同態(tài)加密的定義，同時，給出了定義的d 維酉算子的可交換性證明，這對于量子同態(tài)加密算法的構(gòu)建至關(guān)重要。其次，提出了兩個d 維量子同態(tài)加密算法，包括d 維單粒子與多粒子量子同態(tài)加密算法。提出的兩個算法完全獨立于密鑰，密鑰不需要從發(fā)送方傳輸?shù)浇邮辗?，與現(xiàn)有的量子同態(tài)加密算法相比，本文算法具有更強的安全性。最后，證明了兩個算法的加密子算法輸出結(jié)果和評估子算法輸出結(jié)果均具有完全混合態(tài)的性質(zhì)，這意味著攻擊者在沒有事先探知量子態(tài)明文信息分布的情況下無法獲取子算法輸出的任何有價值信息，這進一步加強了本文所提出算法的安全性。

表1 d 維單粒子算法仿真結(jié)果

表2 d 維多粒子算法仿真結(jié)果

隨著量子通信和量子計算的發(fā)展，未來人們對量子環(huán)境下的委托計算需求也將日益增長，本文所提的高維度量子同態(tài)加密算法對解決這種需求也將有一定價值。