身份基矩陣層級全同態加密方案*

陳 虹，黃 潔，陳紅霖，王閏婷，肖成龍，郭鵬飛，金海波

遼寧工程技術大學軟件學院，遼寧葫蘆島 125105

1 引言

格密碼學的興起歸功于Ajtai[1]，1996年，他證明了格上的困難問題具有最糟糕困難安全性，這一理論說明了格在平均情況困難問題方案的安全性可以由最壞情況問題的安全性來保障。1997年，Ajtai和Dwork[2]首次提出了基于格上最近向量問題（closest vector problem，CVP）的加密方案，此后基于格的密碼體制相繼出現。

初期的格密碼方案存在密鑰尺寸過大、缺乏嚴格的安全性證明等缺陷，無法滿足實際應用的需求。直到2005年，Regev[3]提出了基于LWE（learning with errors）困難問題的單比特公鑰密碼算法，大幅縮小了密文和密鑰的尺寸，同時將安全性規約到格上最壞情況困難問題的難解性——在量子規約下與最壞條件下的最短向量問題（shortest vector problem，SVP）的變體一樣困難。2008年，Gentry等人[4]調換了Regev方案中密鑰生成算法與加密算法，提出了Regev方案的對偶加密方案。單比特加密會浪費過多的存儲空間，為此Kawachi等人[5]、Peikert等人[6]相繼對Regev的方案進行改進，提出了多比特加密方案。2017年，Li等人[7]提出了消息空間為的多比特加密方案。2019年，李明祥等人[8]利用Peikert等人的密文包裝技術，設計了基于LWE的矩陣加密方案與身份矩陣加密方案，其消息空間為。全同態加密（fully homomorphic encryption，FHE）是指對加密后的數據進行加法或乘法運算后解密，其結果與直接對明文進行相同運算的結果相同的加密方案。隨著云計算的高速發展，如何保證用戶隱私數據的安全性成為了關鍵問題之一。全同態加密是云上用戶數據安全性問題的有效解決方案。如圖1所示，在應用了全同態加密方案的云計算環境下，云服務器只保存、處理用戶的密文數據，并將運算結果以密文形式反饋給用戶，由用戶自行解密。由于在云端數據一直以密文方式存儲，即便是服務器的管理人員也無法輕易竊取用戶數據。也就是說，除數據擁有著自身外，其他人對該密文具有相等的破解難度。因此通過全同態加密技術，用戶可以放心地將數據交給云服務器處理，而不必擔心個人隱私數據泄露，有著重要的應用價值。

Fig.1 Working model of fully homomorphic encryption scheme圖1 全同態加密方案工作模型

基于格的全同態加密研究興起于2009年，Gentry等人[4]首先提出了基于理想格的全同態加密方案，并構建了全同態方案的構架，即先構造一個只能執行少量次數的部分同態加密方案，然后“壓縮”解密電路，最后利用Bootstrapping技術實現全同態加密。基于這一藍圖，提出了許多全同態加密方案[9-10]，但Bootstrapping過程要消耗大量計算資源，因此方案效率并不高。在2012年，Brakerski等人[11]提出了不需要Bootstrapping技術的加密方案，他們利用密鑰轉換技術和模轉換技術對密文降維、降噪，得到了可以實現多項式級同態計算的層級全同態加密方案。這一方案擺脫了復雜的Bootstrapping過程，計算效率更高。并且進行多項式級別深度的全同態運算，足夠滿足實際應用的需要。本文將采用Brakerski等人的思路，構造一個層級全同態加密方案。

基于身份的加密方案，簡化了用戶公鑰的管理，常應用于資源有限的環境中。近年來，基于身份的全同態加密方案成為研究熱點[12-14]，但它們都是針對單比特的全同態加密方案，無法快速處理大量的數據，特別是在對圖片、視頻等數據進行加密時，由于一次計算只能處理一個比特的數據，時間成本很高。而基于矩陣的全同態加密算法，每次計算都能加密一個明文矩陣，通過將圖片、視頻等數據矩陣化，能一次性加密大量數據，大大減少了加密耗時。2015年，Hiromasa等人[15]提出了第一個基于矩陣全同態加密方案，方案支持矩陣加法和矩陣乘法的同態操作。2018年，Wang等人[16]針對Hiromasa的方案提出改進，將密文矩陣由(減小到r×(n+r)。本文優化了文獻[8]的矩陣加密方案，得到一個身份基矩陣加密方案（identity-based encryption，IBE），改進方案的明文空間為{0,1}l×l，但允許的噪聲上限更小。然后基于Wang的矩陣全同態加密方案，優化了其中的密鑰轉換過程，使得對任意維度的公鑰矩陣均能實現轉換，最終得到一個基于身份的矩陣層級全同態加密方案（identity-based fully homomorphic encryption，IBFHE）。方案能同時加密l2個比特的明文，并支持矩陣同態加法、同態乘法以及同態哈達瑪積運算，同時減小了噪聲增長速度。

2 相關理論

2.1 符號說明

記實數集為R，自然數集為N，整數集為Z 。對任意的整數q，Zq為模q整數環，其取值范圍為。對一個正整數n，[n]表示{1,2,…,n}。lb(?)表示以2為底的對數，「·?、?·」、「·」分別表示向上取整、向下取整以及四舍五入運算。

本文中向量以小寫的加粗字母表示，如u，其第i個元素表示為ui。矩陣以大寫的加粗字母表示，如A，矩陣內的元素用其對應的小寫字母表示，如aij。用(?)T表示矩陣的轉置。對矩陣A=(a1,a2,…,an)，其p階范數，并記。On×m表示n×m維的零矩陣，表示矩陣X、Y的垂直連接，(X|Y)表示水平連接。記矩陣的乘法為A?B，記矩陣的哈達瑪積為A°B。

用negl(n)表示可忽略函數，對于一個隨機分布{Xn}n∈N，如果滿足，則稱該分布為B-有界分布。

2.2 格理論

定義1（格）設B={B1,B2,…,Bm}∈Rn×m為一組線性無關的向量，由B構成的格Λ(B)定義為這些線性無關向量的整系數線性組合。即：

其中，B為格Λ(B)的一組基。

定義2（滿秩整數格）對向量和矩陣A∈，滿秩整數格定義為：

定義3（離散高斯分布）假設L為一個m維格，對任意向量c∈Rm和σ∈R＞0，有以下定義：

ρσ,c(x)=表示Rm上以c為中心，參數為σ的離散高斯分布。

ρσ,c(L)=∑x∈L ρσ,c(x)表示格L上各分量的離散高斯分布的和。

DL,σ,c表示格L上以c為中心，參數為σ的離散高斯分布。

引理1[17]對固定常數δ，存在一個概率多項式時間算法GenBasis(1n,1m,q)，對poly(n)有界的m≥δnlbq，算法輸出，滿足：

（1）A在統計上接近均勻分布；

（2）S是Λ⊥(A)的一組基，并且

引理2[9,14]設矩陣TA為Λ⊥(A)的基，則存在一個概率多項式時間算法SampleLeft(A,B,TA,U,σ)，輸入以及高斯參數算法輸出矩陣，且Wi的分布統計接近，其中F=(A|B)。

2.3 LWE

LWE實例：對安全參數λ，令n=n(λ)表示維度，整數q=q(λ)≥2，向量，X=X(λ)為Z上的噪聲分布。均勻隨機選擇和噪聲向量ei←X 。計算bi=ais+ei，輸出。LWE困難問題包含以下兩種形式：

定義4（LWE搜索問題）給定m個相互獨立的(ai,bi)，要求解出秘密向量s，記為search-LWEn,m,q,X。

定義5（LWE判斷問題）LWE的判斷問題是以不可忽略的概率區分以下兩個集合：第一個集合里的元素均由LWE實例產生；第二個集合由m個×Zq上的一致均勻抽樣元素構成，記為DLWEn,m,q,X。

在基于LWE的密碼方案中，大多是基于LWE判斷問題的。文獻[18-19]說明了格上近似最短向量問題可以規約到DLWEn,m,q,X上，即若能解決LWE判斷問題，就能解決近似最短向量問題。具體定理如下：

定理1[18-19]令q=q(n)∈N且，其中qi兩兩互素，存在一個B-有界分布X滿足，如果存在一個有效算法能解決LWEn,q,X問題，那么：

（1）存在一個有效的量子算法，能解決任意n維格上的判定性近似最短向量問題和近似最短獨立向量問題

2.4 矩陣運算

（1）直積以及其變體：對兩個矩陣A∈Zm×n和B∈Zs×t，直積(A?B)和其變體(A?′B)分別表示如下：

其中，Bi表示矩陣B的第i列。

定理2[16]對任意矩陣A、B∈Zm×n以及S∈Zn×m，以下等式恒成立：

3 身份基矩陣加密方案

身份基加密方案由IBE.Setup()、IBE.Extract()、IBE.Enc()、IBE.Dec()四個步驟組成。其中IBE.Setup()過程負責系統參數的建立，包括系統主密鑰和主公鑰；IBE.Extract()過程基于系統主密鑰和主公鑰，針對不同的用戶身份，抽樣并計算對應的公鑰與私鑰；IBE.Enc()和IBE.Dec()過程分別為對明文的加密和解密。詳細方案如下。

3.1 基本方案

定義6（FRD（full rank development）編碼）[8]令任意素數q與正整數n，如果函數對任意，矩陣是滿秩的且h是可計算的，則稱函數h為FRD編碼。

本文通過對文獻[8]的改進，設計了一個身份基矩陣加密方案，將明文空間由原方案的M∈[p-1]l×l,p＜q縮減至M∈{0,1}l×l，但在同等情況下(p=2)，原方案噪聲上界B滿足而本文方案為B＜q/2n。因此相同情況下，本文方案容忍的噪聲上界更高，具體方案如下：

（1）IBE.Setup(1λ,1l)。設λ為安全參數，l為明文維數。設定模數q為大于2的素數，隨機選取整數n，以及Z上的誤差分布X=X(λ)，令其最大誤差滿足BX≤q/2n，設m=O((n+l)lbq)與高斯參數σ。調用GenBasis(1n,1m,q) 算法生成和Λ⊥(A0) 的基，且滿足。隨機選擇矩陣設公開參數params={n,m,l,q,A0,A1,B,U} 以及msk=，其中n、m為矩陣維數，l為明文維數，A0為主公鑰，A1、B、U為隨機矩陣。

（2）IBE.Extract(params,msk,id,1t) 。對任意身份id∈，計算它的FRD編碼H=h(id)∈。調用SampleLeft(A0,A1+H×B,TA,U,σ) 得到W∈Z2m×l。令F=(A0|A1+H×B)，由引理2，有F×W=Umodq。設用戶私鑰為skid=S=，從誤差分布中隨機抽取E←Xn×l，令用戶公鑰為pkid=P=(U+2E|F)∈，則滿足P×S=2Emodq。

（3）IBE.Enc(P,M)。輸入消息矩陣M∈{0,1}l×l，隨機選擇R←{0,1}n×l，計算輸出密文C=RT×P+(M|Ol×2m)modq。

（4）IBE.Dec(S,C)。給定密文，計算輸出消息M=(C×S)modqmod 2。

3.2 正確性與安全性

本文設計的IBE方案是正確的且具有IND-sIDCPA安全。

（1）正確性

引理3對于消息矩陣M←{0,1}l×l以及隨機選取的噪聲矩陣，q為任意一個大于2的素數。解密運算M′=2E+Mmodqmod 2，滿足M′=M的前提條件是2||E||∞≤q。

證明若方案正確解密，則2Emodqmod 2=0 。當2||E||∞＞q時，矩陣中至少存在一個元素2e大于q，由于q是素數，因此2emodqmod 2=1，該值會改變對應位置M′的值，導致解密失敗，因此2||E||∞≤q。□

對該身份基矩陣加密方案，解密過程滿足：

由引理3可知，當2RTE上各個元素均小于q時，方案總能正確解密。已知||E||∞≤BX,R←{0,1}n×l，故：

因此當BX≤q/2n時，可由C正確解密得到消息M∈{0,1}l×l，即該方案是正確的。

（2）安全性

定理3本文中的身份基矩陣加密方案的破解難度與解決廣義LWEn,q,X問題等同。只要廣義LWEn,q,X問題是困難的，那么本文方案是IND-sID-CPA安全的。

已知文獻[8]中的方案是IND-sID-CPA安全的，本文方案中修改了公鑰的產生方式，由于E是隨機抽取自誤差分布的小噪聲，因此本文方案公鑰P=(U+2E|F)與文獻[8]的公鑰P=(U|F)對敵手而言是不可區分的；對于id≠id*，有，當h(id)≠h(id*)時，產生的私鑰在統計上是不可區分的；密文C在密文空間中是隨機均勻的，因此敵手的攻擊優勢為零。故只要廣義LWEn,q,X問題是困難的，則本文方案是IND-sID-CPA安全的。

4 身份基矩陣層級全同態加密方案

層級全同態加密即經過深度為L的計算電路后，方案能正確解密，但對L+1次同態運算后的密文，無法正確解密。本章使用3.1節的身份基矩陣加密方案，構造一個身份基矩陣層級全同態加密方案。方案實現一次全同態運算的流程如下：

（1）通過IBE.Setup算法產生L組參數以及主公鑰和主私鑰。

（2）通過IBE.Extract算法產生L組密鑰和對應的公鑰，并計算乘法密鑰和哈達瑪積密鑰（見4.1節），以及分別對應的轉置密鑰（見4.2節SwitchKeyGen算法）。

（3）執行矩陣加法、乘法或哈達瑪積的同態操作（見4.1節），矩陣同態加法不改變密文尺寸，可以用原私鑰正常解密。若執行了乘法或哈達瑪積運算，則轉到下一個步驟。

（4）對由步驟（3）得到的高維密文矩陣，使用密鑰轉換技術（見4.2節SwitchKey算法），獲得能由指定密鑰解密的低維密文，同時不改變明文的值。

（5）使用模轉換技術（見4.3節Scale算法），將模數由q轉換為一個較小的p。經過模轉換技術能將噪聲縮減為原來的p/q，以支持執行更多次的同態運算。

本文方案中將密鑰轉換技術和模轉換技術聯合組成一個Refresh算法，每次執行乘法和哈達瑪積運算后，通過調用Refresh算法輸出的新密文可以繼續進行同態運算。具體方案見4.4節。

4.1 矩陣同態運算

（1）同態加法：輸入兩個密鑰為S的密文C1、C2，輸出同態密文Cadd=(C1+C2)modq。此時滿足CaddS=(C1+C2)S=M1+M2+2E′modq。故同態加法正確解密。

（2）同態乘法：輸入兩個密鑰為S的密文C1、C2，同態乘法可表示為[C1SC2S]q=M1M2+2E′modq。根據定理2，令C*=(C1?C2)sr，S*=(S?′S)sc，有[C1SC2S]q=C*S*modq。

（3）同態哈達瑪積：輸入兩個密鑰為S的密文C1、C2，同態哈達瑪積可表示為[(C1S)°(C2S)]q=M1°M2+2E′modq，根據定理2，令C*=(C1?C2)er，S*=(S?S)ec，有[(C1S)°(C2S)]q=C*S*modq。

在進行同態乘法和同態哈達瑪積運算后，提高了密文和密鑰的維度，需要借助密鑰轉換技術，在不影響正常解密的前提下，對密文和密鑰降維。

4.2 矩陣密鑰轉換技術

采用密鑰轉換技術對4.1節中的C*、S*進行降維，使經過同態運算的密文能繼續進行同態運算。矩陣密鑰轉換技術用到了以下兩個算法[20]：

（1）Powersof2(A)：輸入一個矩陣，算法以列為單位進行操作，輸出矩陣的第i列為：

（2）BitDecomp(B)：輸入一個矩陣，算法以行為單位進行操作，輸出矩陣的第i行為：

矩陣密鑰轉換算法包括兩個過程：第一個算法以一個大尺寸的舊密鑰，一個正常尺寸的新密鑰以及它所對應的公鑰為輸入，輸出一個置換密鑰；第二個算法以大尺寸的舊密文以及置換密鑰為輸入，輸出一個正常尺寸的新密文，且這個新密文能被新密鑰正確解密。本文方案基于文獻[16]，但引入了一個中間矩陣Z，構造一個改進密鑰轉換算法，這樣有效減小了中間過程引入的噪聲。具體過程如下：

設CaSa解密產生的噪聲為2Ea。由引理3可知，只要2||E′+Ea||≤q，則新密文Cb可以被新密鑰Sb正確解密。

4.3 矩陣模轉換技術

通過4.2節中的密鑰轉換技術，降低了密文維度，但密文中的噪聲沒有縮減。通常，經過一次同態乘運算后，噪聲會呈指數增長。模轉換技術的思想是把模q的密文轉換為較小的p，在這一過程中噪聲會縮減為原來的p/q，并且不影響正常解密。具體算法如下：

Scale(C,q,p)：輸入矩陣和整數q＞p＞2，輸出矩陣C′=「p/q」C，滿足C′=Cmod 2。

引理4[16]設q、p為兩個奇數(q＞p)，C∈,C′=Scale(C,q,p)。對任意滿足條件||[CS]q||∞＜q/2-(q/p)||S||1的S，有[C′S]p=[CS]qmod 2，且||[C′S]p||∞＜p/q||[CS]q||∞+||S||1。

在每次進行同態運算后，調用密鑰轉換技術和模轉換技術，將密文維數降低到普通值，同時縮減噪聲，以支持下一次同態運算。

4.4 本文方案

基于3.1節設計的IBE方案，結合文獻[16]，構造一個層級身份基全同態加密方案。方案實現了同態加法運算（IBFHE.Add）、同態乘法運算（IBFHE.Mult）以及同態哈達瑪積運算（IBFHE.PMult）。在同態運算后，通過刷新操作（IBFHE.Refresh）獲得以新密鑰加密的新密文。具體方案如下：

（1）IBFHE.Setup(1λ,1L,1l) ：輸入安全參數λ，計算電路最大深度L以及明文矩陣維數l。令配置參數μ=μ(λ,L)=?(lbλ+lbL)，隨機產生整數n，令m=O((n+l)lbq)，高斯參數為σ。對k=L到0：

（2）IBFHE.Extract(params,id)：根據IBFHE.Setup中公開的參數以及電路深度L，采用IBE.Extract算法產生對應深度的公鑰、私鑰，并計算此時的乘法和哈達瑪積的轉置密鑰。對k=L到0：

（3）IBFHE.Enc(params,pk,M)：輸入明文矩陣M∈{0,1}l×l，運行C←IBE.Enc(PL,M)，得到密文矩陣C。

（4）IBFHE.Dec(params,sk,C)：對使用Sk加密的密文矩陣C，通過計算M←IBE.Dec(Sk,C)，恢復明文M。

（5）IBFHE.Add(C1,C2)：輸入兩個同層次密文C1、C2（當層次不同時，調用IBFHE.Refresh刷新較高層次的密文，下同），計算并輸出同態加法運算結果Cadd=C1+C2。此時對應的私鑰不變。

②模置換過程：運行C**=Scale(C*,qk,qk-1),得到模為qk-1的密文C**。

4.5 噪聲分析與安全性

（1）加解密的噪聲

設密文C的密鑰為Sk，公鑰為Pk，滿足PkSk=2Ekmodqk，其中則。由引理3，當1+2nBX≤qk/2時，方案總能正確解密。

（2）同態運算的噪聲

設C1、C2是密鑰為Sk的兩個密文，其噪聲分別記為，設兩者的噪聲上界均為B。對于同態加法運算，輸出密文最大噪聲為2B。對于同態乘法運算，對于同態哈達瑪積運算，。由引理3，如果這些噪聲小于qk/2，那么后續能正確解密。

（3）IBFHE.Refresh算法的噪聲

Refresh算法由Switch算法和Scale算法組成，在3.2節中證明了Switch算法的正確性，有。由引理3，只要保證最終噪聲小于qk/2，那么方案能正確解密。對任意，由引理4，當時，方案能正確解密，且

（4）安全性

IBFHE方案的安全性與IBE方案的安全性密不可分，定理3說明了本文中的IBE方案是IND-sIDCPA安全的，而IBFHE方案中，同態計算算法是公開的，不影響系統安全性；此外，IBE方案中對明文0或1的加密結果，具有不可區分性。而IBFHE方案是多個IBE密文進行計算的結果，同樣具有不可區分性，因此本文IBFHE方案也是IND-sID-CPA安全的。

4.6 性能分析

從理論和實驗結果上可以證明，本文方案在密鑰轉換過程中引入的噪聲值要遠小于文獻[16]中提出的方案。

4.6.1 理論分析

本文提出的身份基矩陣層級全同態加密方案，能一次加密一個l×l維的0、1明文矩陣，并實現了矩陣加法同態、乘法同態以及哈達瑪積同態。方案中使用的矩陣拉伸和提取操作是實現矩陣同態運算的重要理論基礎。矩陣密鑰轉換技術是實現全同態加密的重要操作，但執行該步驟的同時也會引入新的噪聲。相較于文獻[16]，本文中的改進密鑰轉換技術，不僅支持對任意維度的公鑰進行密鑰轉換，還大幅減少了噪聲的增長。具體數據見表1。

Table 1 Comparison of efficiency between proposed scheme in this paper and ref.[16]表1 本文方案與文獻[16]的效率比較

其中n為隨機整數,l為進行加密的明文矩陣維數，m=O((n+l)lbqk)，t為文獻[16]中定義的變量，值為(m+l)2ll bqk，n遠小于t。可見，本文方案的私鑰略大于文獻[16]，但在控制噪聲增長上具有很大的優勢。本文方案的密鑰轉換過程中引入的噪聲，主要受初始噪聲和矩陣尺寸參數n影響，而文獻[16]的方案中，t是多個矩陣尺寸參數與l bq相乘的結果。在一次密鑰轉換后，文獻[16]引入的噪聲為初始噪聲的t倍，而在初始噪聲相同的情況下，本文方案引入的噪聲僅為文獻[16]方案的n/t，并且不會受到其他參數的影響。

4.6.2 實驗證明

（1）實驗條件

本文方案仿真實驗說明如下：

硬件條件：本文使用九代i5處理器，主頻2.4 GHz，16 GB內存。

軟件條件：Win10_64位操作系統，編程軟件為Python3.8。

（2）實驗目標

本文方案的驗證指標主要是密鑰轉換過程中引入噪聲大小，噪聲越大表明性能越差。因此，為比較本文方案與文獻[16]在密鑰轉換過程中的噪聲增長大小，實驗中對兩種方案分別使用兩個相同明文進行加密與同態乘法運算，得到100個計算結果中的噪聲矩陣。由噪聲矩陣的范數值大小作為該過程引入噪聲的參考值，該值越大表明方案引入的噪聲越大，性能越差。

（3）實驗過程

本實驗分別對本文方案和文獻[16]方案，編寫程序實現下述過程，得到密鑰轉換過程中引入的噪聲：

①設定初始參數n、l、q，明文矩陣M1、M2←{0,1}l×l，計算得到m、t。

②根據Extract方法，產生兩組公私鑰對Sa、Pa與Sb、Pb。

③根據Enc方法，使用Sa分別對M1、M2進行加密，得到密文矩陣C1、C2。

④由4.1節方法，計算得到進行同態乘法或同態哈達瑪積運算后的密文和密鑰

⑤使用對應的密鑰轉換算法，得到以Sb加密的密文Cb。

⑦重復執行步驟②～⑥，得到多個實驗結果。

（4）實驗結果

在本次實驗中，設初始參數n=2，l=3，q=1 021，令m=n+l=5，t=(m+l)2ll bq=1 920。對明文M1=進行同態乘法運算，得到10組實驗數據，每個數據都是10次運算結果的平均值，具體數值見表2。將這10組數據繪制成直方圖，見圖2。可以看出，文獻[16]在一次密鑰轉換過程中引入了大量噪聲，其值均大于q/2，而本文方案引入的噪聲明顯較小，并且在本次實驗中僅為文獻[16]的0.23%。由于t是隨著n的增大而指數增大的，因此n/t的值會越來越小，故本文方案的提升會越來越明顯。因此本文方案的性能更好。

Table 2 Results of experiment表2 實驗結果

Fig.2 Histogram of noises圖2 噪聲直方圖

5 結束語

本文方案基于格上LWE困難問題，構造了一個基于身份的矩陣層級全同態加密方案，通過密鑰轉換技術降低同態運算密文的維度，使用模轉換技術減小了噪聲。采用矩陣存儲結構，可以實現矩陣的同態運算，因此本文方案是IND-sID-CPA安全的，同時具有較小的公鑰尺寸和較高的加密效率。方案還有許多可以改進的地方：一方面可以利用Bootstrapping技術，實現全同態加密；另一方面，可以基于本文方案，構造多用戶情況下的矩陣全同態加密方案。