身份基矩陣層級(jí)全同態(tài)加密方案*

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

遼寧工程技術(shù)大學(xué)軟件學(xué)院，遼寧葫蘆島 125105

1 引言

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

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

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

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

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

2 相關(guān)理論

2.1 符號(hào)說明

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

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

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

2.2 格理論

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

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

定義2（滿秩整數(shù)格）對(duì)向量和矩陣A∈，滿秩整數(shù)格定義為：

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

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

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

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

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

（1）A在統(tǒng)計(jì)上接近均勻分布；

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

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

2.3 LWE

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

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

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

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

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

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

2.4 矩陣運(yùn)算

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

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

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

3 身份基矩陣加密方案

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

3.1 基本方案

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

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

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

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

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

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

3.2 正確性與安全性

本文設(shè)計(jì)的IBE方案是正確的且具有IND-sIDCPA安全。

（1）正確性

引理3對(duì)于消息矩陣M←{0,1}l×l以及隨機(jī)選取的噪聲矩陣，q為任意一個(gè)大于2的素?cái)?shù)。解密運(yùn)算M′=2E+Mmodqmod 2，滿足M′=M的前提條件是2||E||∞≤q。

證明若方案正確解密，則2Emodqmod 2=0 。當(dāng)2||E||∞＞q時(shí)，矩陣中至少存在一個(gè)元素2e大于q，由于q是素?cái)?shù)，因此2emodqmod 2=1，該值會(huì)改變對(duì)應(yīng)位置M′的值，導(dǎo)致解密失敗，因此2||E||∞≤q。□

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

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

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

（2）安全性

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

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

4 身份基矩陣層級(jí)全同態(tài)加密方案

層級(jí)全同態(tài)加密即經(jīng)過深度為L的計(jì)算電路后，方案能正確解密，但對(duì)L+1次同態(tài)運(yùn)算后的密文，無法正確解密。本章使用3.1節(jié)的身份基矩陣加密方案，構(gòu)造一個(gè)身份基矩陣層級(jí)全同態(tài)加密方案。方案實(shí)現(xiàn)一次全同態(tài)運(yùn)算的流程如下：

（1）通過IBE.Setup算法產(chǎn)生L組參數(shù)以及主公鑰和主私鑰。

（2）通過IBE.Extract算法產(chǎn)生L組密鑰和對(duì)應(yīng)的公鑰，并計(jì)算乘法密鑰和哈達(dá)瑪積密鑰（見4.1節(jié)），以及分別對(duì)應(yīng)的轉(zhuǎn)置密鑰（見4.2節(jié)SwitchKeyGen算法）。

（3）執(zhí)行矩陣加法、乘法或哈達(dá)瑪積的同態(tài)操作（見4.1節(jié)），矩陣同態(tài)加法不改變密文尺寸，可以用原私鑰正常解密。若執(zhí)行了乘法或哈達(dá)瑪積運(yùn)算，則轉(zhuǎn)到下一個(gè)步驟。

（4）對(duì)由步驟（3）得到的高維密文矩陣，使用密鑰轉(zhuǎn)換技術(shù)（見4.2節(jié)SwitchKey算法），獲得能由指定密鑰解密的低維密文，同時(shí)不改變明文的值。

（5）使用模轉(zhuǎn)換技術(shù)（見4.3節(jié)Scale算法），將模數(shù)由q轉(zhuǎn)換為一個(gè)較小的p。經(jīng)過模轉(zhuǎn)換技術(shù)能將噪聲縮減為原來的p/q，以支持執(zhí)行更多次的同態(tài)運(yùn)算。

本文方案中將密鑰轉(zhuǎn)換技術(shù)和模轉(zhuǎn)換技術(shù)聯(lián)合組成一個(gè)Refresh算法，每次執(zhí)行乘法和哈達(dá)瑪積運(yùn)算后，通過調(diào)用Refresh算法輸出的新密文可以繼續(xù)進(jìn)行同態(tài)運(yùn)算。具體方案見4.4節(jié)。

4.1 矩陣同態(tài)運(yùn)算

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

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

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

在進(jìn)行同態(tài)乘法和同態(tài)哈達(dá)瑪積運(yùn)算后，提高了密文和密鑰的維度，需要借助密鑰轉(zhuǎn)換技術(shù)，在不影響正常解密的前提下，對(duì)密文和密鑰降維。

4.2 矩陣密鑰轉(zhuǎn)換技術(shù)

采用密鑰轉(zhuǎn)換技術(shù)對(duì)4.1節(jié)中的C*、S*進(jìn)行降維，使經(jīng)過同態(tài)運(yùn)算的密文能繼續(xù)進(jìn)行同態(tài)運(yùn)算。矩陣密鑰轉(zhuǎn)換技術(shù)用到了以下兩個(gè)算法[20]：

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

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

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

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

4.3 矩陣模轉(zhuǎn)換技術(shù)

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

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

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

在每次進(jìn)行同態(tài)運(yùn)算后，調(diào)用密鑰轉(zhuǎn)換技術(shù)和模轉(zhuǎn)換技術(shù)，將密文維數(shù)降低到普通值，同時(shí)縮減噪聲，以支持下一次同態(tài)運(yùn)算。

4.4 本文方案

基于3.1節(jié)設(shè)計(jì)的IBE方案，結(jié)合文獻(xiàn)[16]，構(gòu)造一個(gè)層級(jí)身份基全同態(tài)加密方案。方案實(shí)現(xiàn)了同態(tài)加法運(yùn)算（IBFHE.Add）、同態(tài)乘法運(yùn)算（IBFHE.Mult）以及同態(tài)哈達(dá)瑪積運(yùn)算（IBFHE.PMult）。在同態(tài)運(yùn)算后，通過刷新操作（IBFHE.Refresh）獲得以新密鑰加密的新密文。具體方案如下：

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

（2）IBFHE.Extract(params,id)：根據(jù)IBFHE.Setup中公開的參數(shù)以及電路深度L，采用IBE.Extract算法產(chǎn)生對(duì)應(yīng)深度的公鑰、私鑰，并計(jì)算此時(shí)的乘法和哈達(dá)瑪積的轉(zhuǎn)置密鑰。對(duì)k=L到0：

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

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

（5）IBFHE.Add(C1,C2)：輸入兩個(gè)同層次密文C1、C2（當(dāng)層次不同時(shí)，調(diào)用IBFHE.Refresh刷新較高層次的密文，下同），計(jì)算并輸出同態(tài)加法運(yùn)算結(jié)果Cadd=C1+C2。此時(shí)對(duì)應(yīng)的私鑰不變。

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

4.5 噪聲分析與安全性

（1）加解密的噪聲

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

（2）同態(tài)運(yùn)算的噪聲

設(shè)C1、C2是密鑰為Sk的兩個(gè)密文，其噪聲分別記為，設(shè)兩者的噪聲上界均為B。對(duì)于同態(tài)加法運(yùn)算，輸出密文最大噪聲為2B。對(duì)于同態(tài)乘法運(yùn)算，對(duì)于同態(tài)哈達(dá)瑪積運(yùn)算，。由引理3，如果這些噪聲小于qk/2，那么后續(xù)能正確解密。

（3）IBFHE.Refresh算法的噪聲

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

（4）安全性

IBFHE方案的安全性與IBE方案的安全性密不可分，定理3說明了本文中的IBE方案是IND-sIDCPA安全的，而IBFHE方案中，同態(tài)計(jì)算算法是公開的，不影響系統(tǒng)安全性；此外，IBE方案中對(duì)明文0或1的加密結(jié)果，具有不可區(qū)分性。而IBFHE方案是多個(gè)IBE密文進(jìn)行計(jì)算的結(jié)果，同樣具有不可區(qū)分性，因此本文IBFHE方案也是IND-sID-CPA安全的。

4.6 性能分析

從理論和實(shí)驗(yàn)結(jié)果上可以證明，本文方案在密鑰轉(zhuǎn)換過程中引入的噪聲值要遠(yuǎn)小于文獻(xiàn)[16]中提出的方案。

4.6.1 理論分析

本文提出的身份基矩陣層級(jí)全同態(tài)加密方案，能一次加密一個(gè)l×l維的0、1明文矩陣，并實(shí)現(xiàn)了矩陣加法同態(tài)、乘法同態(tài)以及哈達(dá)瑪積同態(tài)。方案中使用的矩陣?yán)旌吞崛〔僮魇菍?shí)現(xiàn)矩陣同態(tài)運(yùn)算的重要理論基礎(chǔ)。矩陣密鑰轉(zhuǎn)換技術(shù)是實(shí)現(xiàn)全同態(tài)加密的重要操作，但執(zhí)行該步驟的同時(shí)也會(huì)引入新的噪聲。相較于文獻(xiàn)[16]，本文中的改進(jìn)密鑰轉(zhuǎn)換技術(shù)，不僅支持對(duì)任意維度的公鑰進(jìn)行密鑰轉(zhuǎn)換，還大幅減少了噪聲的增長。具體數(shù)據(jù)見表1。

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

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

4.6.2 實(shí)驗(yàn)證明

（1）實(shí)驗(yàn)條件

本文方案仿真實(shí)驗(yàn)說明如下：

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

軟件條件：Win10_64位操作系統(tǒng)，編程軟件為Python3.8。

（2）實(shí)驗(yàn)?zāi)繕?biāo)

本文方案的驗(yàn)證指標(biāo)主要是密鑰轉(zhuǎn)換過程中引入噪聲大小，噪聲越大表明性能越差。因此，為比較本文方案與文獻(xiàn)[16]在密鑰轉(zhuǎn)換過程中的噪聲增長大小，實(shí)驗(yàn)中對(duì)兩種方案分別使用兩個(gè)相同明文進(jìn)行加密與同態(tài)乘法運(yùn)算，得到100個(gè)計(jì)算結(jié)果中的噪聲矩陣。由噪聲矩陣的范數(shù)值大小作為該過程引入噪聲的參考值，該值越大表明方案引入的噪聲越大，性能越差。

（3）實(shí)驗(yàn)過程

本實(shí)驗(yàn)分別對(duì)本文方案和文獻(xiàn)[16]方案，編寫程序?qū)崿F(xiàn)下述過程，得到密鑰轉(zhuǎn)換過程中引入的噪聲：

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

②根據(jù)Extract方法，產(chǎn)生兩組公私鑰對(duì)Sa、Pa與Sb、Pb。

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

④由4.1節(jié)方法，計(jì)算得到進(jìn)行同態(tài)乘法或同態(tài)哈達(dá)瑪積運(yùn)算后的密文和密鑰

⑤使用對(duì)應(yīng)的密鑰轉(zhuǎn)換算法，得到以Sb加密的密文Cb。

⑦重復(fù)執(zhí)行步驟②～⑥，得到多個(gè)實(shí)驗(yàn)結(jié)果。

（4）實(shí)驗(yàn)結(jié)果

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

Table 2 Results of experiment表2 實(shí)驗(yàn)結(jié)果

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

5 結(jié)束語

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