無需重線性化的NTRU型全同態(tài)加密方案*

湯殿華 ， 曹云飛

（1.保密通信重點實驗室，四川 成都 610041；2.中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

全同態(tài)加密是一種功能強大的加密技術(shù)，能夠在加密數(shù)據(jù)上執(zhí)行任意的計算，同時將對應的計算映射到相應的明文中，其計算結(jié)果是為密文?？梢哉f，全同態(tài)加密技術(shù)能夠全密態(tài)處理數(shù)據(jù)。采用該加密技術(shù)，用戶可以將數(shù)據(jù)以加密形式外包給任何不可信服務(wù)器進行“密文計算”來獲取服務(wù)，保證數(shù)據(jù)安全。全同態(tài)加密技術(shù)具有廣闊的應用前景，例如云安全、加密數(shù)據(jù)庫、大數(shù)據(jù)安全、搜索引擎的加密詢問等。

同態(tài)密碼技術(shù)對我們并不陌生，例如RSA[1]、ElGamal[2]、Paillier[3]等加密方案。這些加密算法都具有同態(tài)性，但只有單個同態(tài)運算性質(zhì)，不能同時具有“加同態(tài)”和“乘同態(tài)”，以致不能夠執(zhí)行任意的密文計算。1978年，Rivest，Adleman，Dertouzos[4]首次提出了“隱私同態(tài)”的概念，希望解決密文任意計算問題。直至2009年，Gentry基于理想格提出了第一個全同態(tài)加密方案[5]，實現(xiàn)了“隱私同態(tài)”的構(gòu)想。

采用Gentry的設(shè)計方法，后續(xù)出現(xiàn)了許多全同態(tài)加密方案。按照方案設(shè)計類型可以分為整數(shù)型[6]、GGH型[7]、Regev型[8-9]、NTRU型[10]。這些方案都引入的噪聲，隨著同態(tài)操作的進行，噪聲將增大，當噪聲規(guī)模超過某個門限值時，將不能被正確解密。因此，噪聲管理是全同態(tài)密碼研究的一個重點問題。

在BLLN方案[10]的基礎(chǔ)上，基于NTRU加密方案，我們提出了一個全同態(tài)加密方案。與同類NTRU方案相比，該方案去除了重線性化算法，并且具有更為簡潔的同態(tài)操作，更小的噪聲增長率。

1 準備知識

1.1 符號定義

對于一個非零正整數(shù)q，令模值為q的剩余類所構(gòu)成的整數(shù)環(huán)為?q。當q為奇數(shù)時，?q的元素集合表示為(-q2,q2]∩?；當q為偶數(shù)時，?q元素集合表示為(-q2,q2]∩?。特別當q=2時，?q元素集合為{0,1}。

對于一個實數(shù)z和一個整數(shù)t，用qt(z)表示z除以t的商，rt(z)∈(-t/2,t/2)表示余數(shù)。即qt(z)=也用 [z]t表示rt(z)。

除特殊說明外，一般使用a=(a0,a1,…,an-1)表示列向量，b=[b0,b1,…,bn-1]表示行向量。

我們將在整系數(shù)多項式環(huán)R= ? [x]Φd(x)上進行構(gòu)造方案，其中Φd(x)為d階分圓多項式，一般選擇為Φd(x) =xd/2+1，其中d= 2m,m∈?，為了方便令n=d/2。令q是非零正整數(shù)，定義表示Rq上所有可逆元素組成的集合。

令D1和D2為離散集合E上的概率分布。則他們的統(tǒng)計距離表示為我們用z←D表示從分布D隨機抽樣一個隨機變量。

給定Rq上一個元素u(x)=u0+u1x+…+un-1xn-1，可以將其寫成向量形式u=(u0,u1,…,un-1)，其2-范數(shù)為和無窮范數(shù)為（未做特別說明，||u||都表示為u的無窮范數(shù)）。R上的乘法擴展因子

1.2 離散高斯分布

離散高斯分布廣泛用于格基密碼方案的設(shè)計，尤其是基于錯誤學習問題（Learning With errors problem，LWE）和環(huán)上的錯誤學習問題（Ring Learning With Errors problem，RLWE）問題的密碼方案。下面給出有關(guān)離散高斯分布相關(guān)概念。

均值為0且方差為σ2的正太分布N(0,σ2)，其概率密度函數(shù)為對于1個n實數(shù)域上的向量x∈?n，一個正實數(shù)s＞0，令函數(shù)由于則v=ρ/sn ss是一個∈?n上的概率密度函數(shù)。對于一個可數(shù)集合定義對于任何一個向量定義是對ρs(x)進行一個向量c的平移。

定義1B有界分布。如果分布χ滿足：Pre←χ[|e|＜B]≤1-negl(n)。則稱其為B有界分布。

對于均值為0，方差為σ2的高斯分布N(0,σ2)，成立不等式那么當k＞9.2時即高斯分布式一個有界分布。同理離散高斯分布DZn,σ也是一個有界分布，可以取界B=9.2σ。

1.3 RLWE問題

首先定義一個分布As,χ：設(shè)χ是Rq上的一個分布，此處χ一般將取為離散高斯分布。令s∈Rq，a←Rq為隨機均勻選取，隨機抽樣一個錯誤e←χ，計算b=a·s+e，則得到兩個環(huán)元素(a,b)所構(gòu)成的新分布定義為As,χ。同時將Rq×Rq上的均勻分布定義為U。

Lyubaskevsky，Peikert和 Regev提出了 RLWE問題[11]，并將此困難問題歸約到多項式環(huán)理想格中的近似最短向量問題（Shortest Vector Problem，SVP）。下面給出其定義：

定義 2 判別 RLWE 問題假設(shè)：DRLWEn,q,χ。由 (a,b=a·s+e)產(chǎn)生的分布As,χ與Rq×Rq上的均勻分布U是計算不可區(qū)分的，即As,χ≈U。

當s取自分布χ時，DRLWEn,q,χ仍然是一個困難問題。

1.4 DSPR問題

Stehle和Steinfeld在研究NTRU的可證明安全性時， 研究了DSPR問題[12]（Decisional small Polynomial Ratio Problem），并得出q為素數(shù)，分圓多項式環(huán)條件下，h=g/f（g、f取自離散高斯分布χ）所形成的分布與Rq上的均勻分布是不可區(qū)分的。微軟研究中心的Joppe W. Bos等人將該DSPR進行了推廣[10]。

定義4 DSPR問題：DSPRn,q,χ。對于安全參數(shù)為λ，n、q為整數(shù)，為Rq上的分布，令即t為Rq上的可逆元素。則DSPRn,q,χ問題為：h=(y1+t·χz1)/(y2+t·χz2)modq所形成的分布與Rq上的均勻分布是不可區(qū)分的。

一般χ為分布表示限制于上的離散高斯分布D?n,σ。DRq,σ表示限制于Rq上的離散高斯分布D?n,σ，該分布可以對每個系數(shù)采用D?n,σ抽樣來獲得。

定理1 令d≥8是一個2的冪，q≥5是一個素數(shù)，令Φd(x)=xd/2+1，設(shè)Φd(x)在模q上可分解為個不可約多項式因子令表示中心為z∈Rq的離散高斯分布則分布與均勻分布的統(tǒng)計距離為：

由定理1可知，通過設(shè)置參數(shù)可以保障h和兩個分布的統(tǒng)計距離可忽略，并且推斷出h=g/f（g、f取自離散高斯分布χ）所形成的分布與是統(tǒng)計不可區(qū)分的。

1.5 同態(tài)加密方案的定義

定義5 同態(tài)加密方案。一個同態(tài)加密方案是概率多項式時間算法的一個四元組HE=（KeyGen，Enc，Dec，Evaluate），如下：

KeyGen：根據(jù)安全參數(shù)λ，生成方案的私鑰sk、公鑰pk、計算公鑰evk。

Enc：給出一個明文m，用公鑰pk加密明文m，得到密文c。

Dec：輸入私鑰和密文c，進行解密運算，輸出明文m′。

Evaluate：輸入公鑰pk，t輸入線電路Cir，一組密文c=(c1,c2,…,ct)，其中。ci=Encpk(mi),i=1,2,…,t輸出c*=Evaluate(pk,Cir,c)，且以極大的概率滿足Dec(sk,c*)=Cir(m1,m2,…,mt)。

既然同態(tài)加密能夠?qū)γ芪倪M行計算，那么需要對其密文計算的程度進行衡量。也就是Evaluate算法所支持的運算集合。

定義6C -同態(tài)。設(shè)C是一個電路集合，HE是一個同態(tài)加密方案，任取一個電路Cir∈C，設(shè)其輸入線有t個。如果對任意的一組明文m1,m2,…,mt和所對應的一組密文c=(c1,c2,…,ct)（其中ci=Encpk(mi),i=1,2,…,t），有下面的等式成立：

則稱該方案為C-同態(tài)，或者方案對于一個電路集合C 是正確的，同時也稱C為方案HE的可許電路集合，當C是一個有限電路集合時，也稱方案為類同態(tài)加密方案。

定義7 緊同態(tài)加密。如果存在一個多項式g=g(λ)，使得HE方案的Evaluate算法的輸出比特長度不超過g。則稱HE是一個緊同態(tài)加密方案。

注意：g與所運算的電路Cir、輸入密文數(shù)無關(guān)。表明隨著同態(tài)操作的進行，密文的尺寸始終保持在一個界之內(nèi)，其尺寸獨立于同態(tài)操作數(shù)。

定義8 緊運算。如果HE是緊的且對電路集合C 是正確的。稱該同態(tài)加密方案HE緊運算C 中的電路。

定義9 全同態(tài)加密方案。一個方案HE對所有的電路既是緊的，又是同態(tài)的，則稱其是一個全同態(tài)加密方案。

定理2 自舉轉(zhuǎn)化定理。如果一個同態(tài)加密方案HE能夠同態(tài)計算自身的解密電路，并且之后還能計算一個乘法電路，HE方案滿足循環(huán)安全，那么該方案可以轉(zhuǎn)化為一個全同態(tài)加密方案。

1.6 比特分解算法與比特分解逆算法

整數(shù)環(huán)?q上的數(shù)b∈?q，可以表示成比特長度為l= ?logq?+1的二進制數(shù)據(jù)(bl-1bl-2…b0)2，將其按住從低位到高位的順序?qū)懗蒷維向量(b0,b1,…,bl-1)。

對于b∈?q，其比特分解算法BD，規(guī)定為：

同理，對于n維向量其比特分解算法BD，規(guī)定為：BD(a)=(BD(a0),BD(a1),…,BD(an-1))，即 BD(a)=(a00,a01,…,a0,l-1,a10,a11,…,

可以將BDI寫成矩陣表達的形式為：

對于m×n階矩陣其比特分解算法BD和比特分解逆算法BDI類似。即將每一行看著1個n維向量處理，然后調(diào)用向量的BD和BDI算法。

令c∈Rq，其比特分解算法規(guī)定為：BD(c)=

令Rq上的l維向量c=(c0,c1,…,cl-1)，則其比特分解逆算法BDI，規(guī)定為

令Rq上的m維向量則比特分解算法BD，規(guī)定為BD(c)=(BD(c0),BD(c1),…,BD(cm-1))。類似可以定義Rq上向量的比特分解逆算法，以及Rq上矩陣的比特分解算法和逆分解算法。

特別地， 對于Rq上的l單位矩陣Il×l，BDI(Il×l)=(1,2,…,2l-1)。 則對于c∈Rq，有同理對于同樣有

2 全同態(tài)加密方案

2.1 類同態(tài)加密方案NSHE

本小節(jié)基于RLWE問題和DSPR問題提出了一個NTRU型的類同態(tài)加密方案（Somewhat Homomorphic Encryption），命名為NSHE方案。該方案具有一定深度的同態(tài)計算能力，并且其密文計算算法形式簡單，不需要重線性化算法來控制密文尺寸增長?；诖送瑧B(tài)加密方案，可以利用自舉轉(zhuǎn)化定理進一步構(gòu)造全同態(tài)加密方案。令本方案的運算均為上的運算，下面將給出類同態(tài)加密方案的具體描述。

SH.KeyGen(1λ)：輸入安全參數(shù)λ，生成分圓多項式環(huán)離散高斯分布和為明文空間的模值，則明文空間為：在離散高斯分布上隨機選擇f′←DRq,σkey，令f=t·f′+1，并檢測f是否可逆。如果不可逆，重選擇f′，止到選擇出可逆的f。計算f-1，然后隨機選擇計算

SH.Enc(m,pk)：輸入消息m∈Rt，隨機選擇根據(jù)公鑰pk=h計算：

其中Il×l為l階單位矩陣。

SH.Dec(c,sk)： 輸入密文cl×1=(c0,c1,…,cl-1)， 使用私鑰sk=f進行解密，

SH.Add(c,c′)： 輸入兩個密文c,c′， 計算

SH.Mult(c,c′)：輸入兩個密文c,c′和計算密鑰evk。計算最后得到

2.2 解密正確性條件

定理3 令密文c是由本方案SH.Enc(m,pk)所產(chǎn)生，令e2,0·g，則本密文c能夠被正確解密的條件為：

證明：根據(jù)類同態(tài)加密方案的解密算法，存在多項式向量kc′∈R，使得成立如下等式：

令v=e1·f+e2·g，kc=kc′·f-e2·kg，v,kc為l維列向量。由2.6節(jié)可知，BDI(Il×l)=(1,2,…,2l-1)。由于Δ·t=q-rt(q)，f=t·f′+1 則有：

進一步得到：

可以進一步推廣定理3的結(jié)論，得到定理4。

定理4 設(shè)經(jīng)過同態(tài)操作后的密文或者由SH.Enc(m,pk)產(chǎn)生的密文c，其存在這樣的表達式(t/q)·(c·f)=m·BDI(Il×l)+v+t·kc，其中那么c能夠被正確解密的條件為：

對于密文c，稱(t/q)·(c·f)表達式中的v為噪聲，噪聲大小為||v0||∞。

那么由SH.Enc(m,pk)直接產(chǎn)生的密文c的噪聲為其噪聲規(guī)模為

2.3 同態(tài)操作的噪聲分析

由于密文中含有噪聲，那么隨著同態(tài)加法和同態(tài)乘法操作進行，密文中的噪聲不斷地在增大，一旦噪聲的規(guī)模不滿足解密正確性條件，將導致解密錯誤。下面分析同態(tài)加法和同態(tài)乘法的噪聲增長率，令兩個輸入密文c、c′，且在代入私鑰sk=f時具有如下表達形式：

存在kc,kc′∈Rl，使得成立：

設(shè)這兩密文的噪聲規(guī)模分別為E、E′。根據(jù)t·kc=(t/q)·(c·f)-m·BDI(Il×l)-v， 可以推斷出

（1）同態(tài)加法

由于密文c、c′所對于的消息m∈Rt、m′∈Rt，其消息在Rt加法運算為m+m′=[m+m′]t+radd·t，||radd||≤1。由同態(tài)加法算法SH.Add(c,c′)可知，存在kAdd∈Rl使得cAdd=c+c′+q·kAdd。則有：

由以上運算可以得出cAdd的噪聲項為vAdd=v+v′。則其噪聲規(guī)模為EAdd=||v0+v0′||∞≤E+E′。

（2）同態(tài)乘法

同態(tài)乘法的噪聲分析相對較為復雜。令消息m∈Rt、m′∈Rt在Rt上的乘法運算為m·m′=[m·m′]t+t·rMult，||rMult||≤δR·t/4+1/2。根據(jù)同態(tài)乘法，存在kM,kr∈Rl， 成立cMult=BD(c′Mult)·r+q·kM，則有：

那么：

綜上所述，所得：

則密文cMult的噪聲為：

根據(jù)分析可知密文c′中噪聲分量的規(guī)模都是小于E′，c的情況也一樣，因此cMult噪聲規(guī)模為：

由同態(tài)加法和同態(tài)乘法操作的噪聲分析可知。同態(tài)加法的噪聲增長比較小，可粗略看為兩個密文的噪聲相加；同態(tài)乘法的噪聲增長較大，可粗略看為兩個密文噪聲的線性組合。綜上所述，本方案的同態(tài)操作的噪聲增長均為線性。

2.4 同態(tài)計算能力

定理4類同態(tài)加密方案NSHE能夠同態(tài)計算的電路深度L滿足以下條件：

其中：

證明：根據(jù)同態(tài)操作的噪聲分析，可以看出“同態(tài)乘法”所引入的噪聲比“同態(tài)加法”要大很多，所以我們粗略地使用“方案能夠計算的乘法深度”來作為方案能夠同態(tài)計算的電路深度。

由類同態(tài)加密方案NSHE可知，密文的新鮮噪聲規(guī)模為：

那么兩個新鮮密文經(jīng)過一次同態(tài)乘法之后，噪聲規(guī)模為：

則：E1＜A·E+B。

再經(jīng)過一次同態(tài)乘法，噪聲規(guī)模為：E2＜A·E1+B＜A(A·E+B)+B＜A2·E+A·B+B。

依次類推，經(jīng)過深度為L同態(tài)乘法，噪聲規(guī)模為：

為了保證經(jīng)過深度為L的同態(tài)乘法運算之后的密文能夠被正確解密，那么必須滿足即

對該不等式求解，得到：

2.5 全同態(tài)加密方案

根據(jù)Gentry的自舉轉(zhuǎn)化定理可知，當類同態(tài)加密方案能夠在滿足自舉性質(zhì)時，可以通過自舉轉(zhuǎn)化定理轉(zhuǎn)化為一個全同態(tài)加密方案。所謂自舉性就是：類同態(tài)加密方案能夠同態(tài)計算自身的解密電路，并且之后還能計算一次同態(tài)乘法。

根據(jù)文獻[8]對解密結(jié)構(gòu)的分析，本方案當t=2時解密電路的電路深度為：

當解密電路的深度加1后小于方案的同態(tài)計算能力時，類同態(tài)加密方案可以由自舉轉(zhuǎn)化成為全同態(tài)加密方案。要求成立以下不等式

類同態(tài)加密方案不天然具有自舉性，必須通過一些技術(shù)，在保證其同態(tài)計算能力不變的情況下，對解密算法進行處理，降低解密算法的電路深度。

（1）方法1：采用模轉(zhuǎn)換技術(shù)（Modulus Switching），降低模值q′，從而降低解密電路的深度。

（2）方法2：采用密鑰轉(zhuǎn)換技術(shù)（Key Switching），轉(zhuǎn)換為一個更為“簡單”私鑰。例如非零系數(shù)項數(shù)較少，系數(shù)小的私鑰f*。下面給出密鑰轉(zhuǎn)換技術(shù)。

密鑰轉(zhuǎn)換技術(shù)需要一個輔助信息ks，可以理解為在新公私鑰(pk*,sk*)=(h*,f*)下，對原私鑰f加密。即其中。h*=g*/f*那么密鑰轉(zhuǎn)換算法為：

其存在kks,v*,kc*∈Rl，成立等式：

通過分析可知，c*所由私鑰f*解密，對應的消息仍然為m。

3 安全性證明

本節(jié)將給出2.1節(jié)所給出的同態(tài)加密方案在vDRLWEn,m,q,χ困難問題下具有IND-CPA安全。

定理5在DRLWEn,q,χ困難問題假設(shè)下，類同態(tài)加密方案NSHE是不可區(qū)分選擇明文安全的（Indistinguishability Under Chosen-plaintext Attack，IND-CPA）。

證明：采用Stehle和Steinfeld在文獻[12]中的證明方法來證明方案安全性，具體如下：

令A 是一個對本方案IND-CPA攻擊者。B 是一個對vDRLWEn,m,q,χ困難問題的挑戰(zhàn)者，能夠訪問預先設(shè)定秘密信息s←DRql,σerr的諭言機O，返回一個U(Rq×Rql)或者As,m,χ抽樣。攻擊-挑戰(zhàn)游戲模型如下：

B 訪問諭言機O，獲得一個抽樣 (h′,c′)，令pk=h′，并將pk發(fā)送給攻擊者A 。

A 在消息空間Rt中隨機選擇兩個消息m0,m1，并發(fā)送給挑戰(zhàn)者B 。

B隨機選取一個比特b←{0,1}，計算挑戰(zhàn)密文c=Δ·mb·BDI(Il×l)+c′，將c發(fā)送給攻擊者A 。

A根據(jù)自己攻擊能力，猜測b的值為b′，并將b′發(fā)送給B 。

如果b′=b，B輸出1，否則輸出0。

由于t在Rq上可逆，且通過DSPR問題的定理1可知，h′與真實的公鑰h分布是統(tǒng)計不可區(qū)分的。又因為當B 訪問諭言機O，響應的是一個As,m,χ抽樣 (h′,c′=s·h′+e)，則c=Δ·mb·BDI(Il×l)+c′=Δ·mb·BDI(Il×l)+s·h′+e是符合真實密文分布的。因此B和A間的挑戰(zhàn)-攻擊游戲建立了正確的IND-CPA模型。vDRLWEn,m,q,χ是困難的，那么NSHE方案是滿足IND-CPA安全的。

4 結(jié) 語

全同態(tài)密碼由于具有密態(tài)計算功能，能夠保證數(shù)據(jù)計算處理的信息安全，特別滿足當前云計算，大數(shù)據(jù)的安全需求，這使得全同態(tài)密碼具有廣闊的應用前景。雖然全同態(tài)密碼的同態(tài)操作已經(jīng)處于毫秒級水平，但這仍然不能滿足復雜環(huán)境的時鐘級速度。因此全同態(tài)密碼的效率仍然是研究的重點。我們基于NTRU提出一個全同態(tài)加密方案，與同類NTRU方案相比，該方案去除了重線性化算法，并且具有更為簡潔的同態(tài)操作，更小的噪聲增長率。