NTRU型無需密鑰交換的全同態(tài)加密方案

宋新霞，陳智罡，周國民

（1. 浙江萬里學(xué)院基礎(chǔ)學(xué)院，浙江 寧波 315100；2. 浙江萬里學(xué)院電子與計算機(jī)學(xué)院，浙江 寧波 315100；3. 浙江警察學(xué)院計算機(jī)與信息技術(shù)系，浙江 杭州 310053)

NTRU型無需密鑰交換的全同態(tài)加密方案

宋新霞1，陳智罡2，周國民3

（1. 浙江萬里學(xué)院基礎(chǔ)學(xué)院，浙江 寧波 315100；2. 浙江萬里學(xué)院電子與計算機(jī)學(xué)院，浙江 寧波 315100；3. 浙江警察學(xué)院計算機(jī)與信息技術(shù)系，浙江 杭州 310053)

詳細(xì)分析了環(huán)LWE上NTRU基本加密方案的噪聲特性與同態(tài)性，引出了“零次同態(tài)加密”的概念，并且說明了環(huán)LWE上NTRU基本加密方案是一個零次同態(tài)加密。提出了2個同態(tài)加密方案，展示了如何基于NTRU零次同態(tài)加密，設(shè)計NTRU型BGN同態(tài)加密方案與全同態(tài)加密方案。在該NTRU型全同態(tài)加密方案中，其密鑰在密文計算中始終保持不變，因此，無需密鑰交換就獲得了一個全同態(tài)加密方案。此外，該NTRU型全同態(tài)加密的密文是一個向量，相比密文是矩陣的GSW全同態(tài)加密方案，具有存儲與傳輸上的優(yōu)勢。

全同態(tài)加密；NTRU加密；環(huán)LWE問題；密鑰交換；BGN同態(tài)加密

1 引言

全同態(tài)加密能夠在不知道密鑰的情況下，對密文進(jìn)行任意計算，這種特殊的性質(zhì)使全同態(tài)加密有廣泛的應(yīng)用需求。同態(tài)加密的概念自 1978年提出后[1]，一直是密碼學(xué)界的開放難題，直到2009年Gentry提出第一個全同態(tài)加密方案[2]。隨后人們基于不同的困難問題，設(shè)計出一些全同態(tài)加密方案，如小數(shù)理想上的全同態(tài)加密方案[3]、整數(shù)上的全同態(tài)加密方案[4～6]、LWE（環(huán)LWE）上的全同態(tài)加密方案[7～12]。在這些全同態(tài)加密方案中，由于環(huán) LWE上的全同態(tài)加密方案簡單、效率高，安全性被歸約到格上標(biāo)準(zhǔn)困難問題，并且被認(rèn)為具有抗量子攻擊的特性，所以成為目前主流的全同態(tài)加密方案。

目前，環(huán) LWE上的全同態(tài)加密方案所基于的基本公鑰加密方案[13,14]及其變形[7]，其本身具有加法同態(tài)屬性，但不具有乘法同態(tài)屬性。為了使密文能夠進(jìn)行乘法計算，定義密文乘積形式為張量密文c1?c2，對應(yīng)的密鑰是s?s。盡管這樣定義能夠使密文進(jìn)行乘法計算，但這導(dǎo)致了密文和密鑰的維數(shù)膨脹，如果不對維數(shù)約減的話，將進(jìn)行不了幾次乘法。為此，文獻(xiàn)[7]引入了密鑰交換技術(shù)，通過密鑰交換可以將維數(shù)膨脹的密文轉(zhuǎn)換成一個正常維數(shù)的新密文，對應(yīng)的密鑰是一個正常維數(shù)的新密鑰。可以說，密鑰交換技術(shù)導(dǎo)致了環(huán) LWE上全同態(tài)加密方案的誕生，但密鑰交換也是需要付出代價的。

一方面，每次密文乘法計算后，都要將乘積密文與密鑰交換矩陣相乘，從而進(jìn)行密鑰交換得到一個正常維數(shù)的密文，極大地影響了計算效率；另一方面，密鑰交換矩陣是公鑰，對一個深度為L的全同態(tài)加密方案，在公鑰中需要包含L個密鑰交換矩陣。在環(huán) LWE的全同態(tài)加密方案下，每個密鑰交換矩陣是的矩陣，密鑰交換矩陣的尺寸是，而在LWE的全同態(tài)加密方案下，每個密鑰交換矩陣是的高維矩陣，密鑰交換矩陣的尺寸是 (n + 1)3log2q?？梢?，密鑰交換矩陣占用了大量空間。因此，如何去除密鑰交換過程是全同態(tài)加密研究中一個非常重要的問題。

一個自然的想法就是如果密文是多項式，則多項式的乘積不會引起密文維數(shù)的增長。環(huán)LWE上的NTRU加密方案的密文是一個多項式，本文首先分析了該方案的噪聲特性與同態(tài)性，引出了“零次同態(tài)加密”的概念，說明NTRU加密方案是一個“零次同態(tài)加密”，即密文乘積 c1·c2本身具有潛在的乘法同態(tài)性，但由于噪聲增長依賴于密文c1的長度，導(dǎo)致密文乘積噪聲過大而喪失了乘法同態(tài)性。此外，密鑰在密文乘積中是保持不變的。這與先前的張量積形式構(gòu)造的全同態(tài)加密方案是不同的。

為了約減噪聲，本文將密文c1的系數(shù)展開成位的形式，同時為了獲得同態(tài)性，將密文c2從多項式“提升”到向量c2'，其中，向量中的每個元素是分別對明文2im (i=0,…,l)的加密。即向量中的第一個密文是NTRU加密的原始密文，其他密文都是為了同態(tài)性而存在的。密文乘積是行向量與列向量的乘積，即 BitDecomp(c1)·c2'，其中，BitDecomp(c1)輸出的是行向量。從而構(gòu)建出一個BGN加密方案，該方案具有加法同態(tài)性，但是只能夠進(jìn)行一次乘法計算。是因為密文乘積的結(jié)果沒有提供為了同態(tài)性而存在的元素。在此基礎(chǔ)上，將密文c1也從多項式“提升”到向量。密文進(jìn)行乘積時，將向量中的每個元素展開成位的形式，形成一個矩陣，密文乘積是矩陣與向量的乘積，從而獲得了乘法同態(tài)性，構(gòu)造出一個全同態(tài)加密方案。

本文詳細(xì)展示了如何基于NTRU零次同態(tài)加密，設(shè)計一個NTRU型BGN同態(tài)加密方案與全同態(tài)加密方案。在該NTRU型全同態(tài)加密方案中，其密鑰在密文計算中始終保持不變，因此無需密鑰交換就獲得了一個全同態(tài)加密方案。此外，該NTRU型全同態(tài)加密的密文是一個向量，而GSW全同態(tài)加密中的密文是矩陣[10]，因此具有存儲與傳輸上的優(yōu)勢。

2 預(yù)備知識

1) 基本符號

本文的向量默認(rèn)為列向量。向量用小寫粗體表示，矩陣用大寫粗體表示。R上的元素用小寫表示。( )T表示轉(zhuǎn)置。令a∈R，則，其中，是多項式 a的系數(shù)，定義表示無窮范數(shù)，即多項式 a的系數(shù)的最大值。對于 a，b∈R，有

使用x←D表示x從分布D中取樣。為了簡單起見，定義B邊界分布為從該分布取樣的值不超過B。如果D是R上的B邊界分布，x←D表示x是一個B邊界的多項式，即

2) 環(huán)LWE問題與判定小多項式比問題

本文方案的安全性基于判定環(huán) LWE問題和判定小多項式比問題。環(huán)LWE問題是LWE問題在環(huán)上的推廣[13,14]。判定小多項式比問題參考文獻(xiàn)[15]。

3) 全同態(tài)加密

一個同態(tài)加密方案包含 4個概率多項式算法：公鑰和密鑰生成算法、加密算法、解密算法、密文計算算法。具體定義參考文獻(xiàn)[2, 7]。另外，BGN同態(tài)加密指的是具有加法同態(tài)性，但是只能夠進(jìn)行一次乘法的方案[16,17]。

3 NTRU型BGN同態(tài)加密方案

本節(jié)基于文獻(xiàn)[11]提出的NTRU基本加密方案，設(shè)計一個 BGN同態(tài)加密方案，該方案具有加法同態(tài)性，但是只能夠進(jìn)行一次乘法同態(tài)計算。首先對NTRU基本加密方案的加密噪聲和解密噪聲進(jìn)行分析，為后面同態(tài)加密方案的噪聲分析奠定基礎(chǔ)。

3.1 NTRU基本加密方案的噪聲分析

E.SecretKeygen(1λ)：選取 f′←χ，計算f←2f′+1使f≡1(mod 2)。若f在Rq上是不可逆的，則重新選取f′。令私鑰sk=f∈R。

E.PublicKeygen(sk)：選取g←χ，計算h=2g f?1∈Rq，令公鑰pk=h。

E.Enc(pk, m)：消息m∈{0,1}，選取s，e←χ，輸出密文c←m+hs+2e∈Rq。E.Dec(sk, c)：輸出m←cf mod 2。

下面從加密噪聲和解密噪聲的角度說明方案的正確性，也便于下文對同態(tài)操作的噪聲進(jìn)行分析。

引理1 加密噪聲

q, n, Rq,χ是上述加密方案的參數(shù)，令χ的上界是B。任意f′←χ，計算f←2f′+1使f ≡1(mod 2)。若 f在 Rq上是不可逆的，則重新選取 f′。任意m∈{0,1}。令h←E.PublicKeygen(f)，c←E.Enc(h, m)，則存在v且使如下等式成立

其中，v為密文的噪聲。

證明 根據(jù)基本加密方案有

cf = mf + hsf + 2ef = mf + 2gs +2ef = mf + 2v∈Rq

由于χ的上界是B，所以g、s、e的系數(shù)上界是B，f的系數(shù)上界是2B+1。又可知，gs的系數(shù)上界是nB2，ef的系數(shù)上界是nB(2B+1)，所以，v的系數(shù)上界是3nB2+nB，即

引理1給出了初始密文（新鮮密文）的噪聲上界。由于密文計算過程中噪聲會增長，而解密的正確性與密文中噪聲大小是相關(guān)的，引理2給出了密文能夠正確解密的噪聲界。

引理2 解密噪聲

任意f, c∈Rq，且有f ≡1(mod 2)。若滿足其中，m∈{0,1}，。則有

E.Dec(f, c)=cf (mod 2)=mf + 2v(mod 2) = mf (mod 2)= m

引理2說明在解密過程中，只要保持形如“mf + 2v”的解密結(jié)構(gòu)，且，就能夠正確解密。這種保持解密結(jié)構(gòu)的思想在下文設(shè)計同態(tài)加密屬性的過程中非常有用。

3.2 NTRU型BGN同態(tài)加密方案

上述NTRU基本加密方案具有加法同態(tài)性，但不具有乘法同態(tài)性。為了獲得乘法同態(tài)性，本文將上述NTRU基本加密方案的密文提升成向量的形式，向量中每個元素是對如下明文的加密：m, m2,…, m2l，向量的長度是。BGN同態(tài)加密方案的參數(shù)選擇和NTRU基本加密方案相同，方案如下。

6) BGN.Mult(pk, c1, c2)：令c10是密文向量c1中的第一個元素，輸出BitDecomp(c10)·c2∈。注意 BitDecomp(c10)是一個行向量，其中每個元素是一個系數(shù)為0或1的多項式，而c2是一個列向量。

上述BGN方案的正確性、安全性和NTRU基本加密方案是一樣的。該 BGN加密方案的乘法密文的長度非常短，只是一個多項式，與基本加密方案的密文長度相同。下面分析這2個方案的同態(tài)性。

3.3 同態(tài)性

由于上述NTRU基本加密方案和BGN同態(tài)加密方案的加法同態(tài)性是顯然的，下面只關(guān)注其乘法同態(tài)性。

3.3.1 NTRU基本加密方案的同態(tài)性

令ci∈Rq(i=1,2)是用基本加密方案對明文mi∈{0,1}的加密，其對應(yīng)密鑰是f，有cif =mif + 2vi∈Rq，且滿足。令c×= c1?c2，則c×f= c1? ( m2f + 2v2)= m2(m1f + 2v1)+2c1v2= m1m2f +2m2v1+ 2c1v2。其中，v2和v1的系數(shù)都是小的，但是由于c是R上的密文，所以其系數(shù)的界為1q，因此密文乘積的噪聲主要依賴于密文 c1的長度，由于，顯然噪聲值遠(yuǎn)大于，因此

令ci∈(i=1, 2)是用BGN同態(tài)加密方案對明文mi∈{0,1}的加密，其對應(yīng)密鑰是f，其中，c10是密文向量 c1中的第一個元素。令 c×= Bit-Decomp(c10)?c2，則有

由于 v10、BitDecomp(c1)和 v2都是小的，所以密文乘法可以正確解密，從而密文進(jìn)行一次乘法計算。

但是如果c×再和另外一個乘法密文c×＇進(jìn)行乘法計算，由于沒有c×和c×＇的向量形式密文，所以按照上述乘法定義將無法計算，從而只能進(jìn)密文乘積無法正確解密。所以在乘法同態(tài)計算中，由于噪聲依賴于密文導(dǎo)致噪聲值過大，從而一次乘法也無法進(jìn)行。所以基本加密方案不具有乘法同態(tài)性。

這種由于噪聲阻礙了同態(tài)性的獲得的方案，稱為零次同態(tài)加密。零次同態(tài)加密可以看成是部分同態(tài)加密（somewhat homomorphic encryption）的極端情況。

3.3.2 BGN加密方案的同態(tài)性

令c為用BGN加密方案對明文m∈{0,1}的加密，對應(yīng)密鑰是f。根據(jù)解密定義可知c f =(c0f, c1f,…,clf)T= (mf +fhs0+2fe0, m2f + fhs1+2fe1,…, m?2lf + fhsl+ 2fel)T=(m, m2,…, m2l)Tf +2v= mPowerof2(f) +2v，其中，v= gsi+eif (i=0,…,l)。注意Powerof2(f)表示的是一個列向量。行一次乘法計算。

下面構(gòu)造一個NTRU層次型全同態(tài)加密方案。

4 層次型全同態(tài)加密方案

在該層次型全同態(tài)加密方案中，密鑰在密文計算過程中是保持不變的，不需要密鑰交換。方案如下。

1) FHE.Setup(λ, L)：輸入安全參數(shù)λ和電路深度 L，輸出多項式次數(shù) n、分圓多項式φ( x) = xn+1，其中，n是2的冪次方；環(huán)上的噪聲分布χ，其界為 B；素數(shù)模 q。令

2) FHE.KeyGen(λ)：選取 f’←χ，計算 f←2f’+1使f ≡1(mod 2)。若f在Rq上是不可逆的，則重新選取f’。令私鑰sk=f∈R。選取g←χ，計算h=2g f-1∈Rq，令公鑰pk=h。

3) FHE.Enc(pk, m)：消息m∈{0,1}，選取si，ei←χ(i=0,…,l)，輸出密文向量 c=ci(i=0,…,l)，其中，ci←m2i+hsi+2ei∈Rq。

4) FHE.Dec(sk, c)：輸出m← c0f mod 2。

5) FHE.Add(pk, c1, c2)：輸出

6) FHE.Mult(pk, c1, c2)：輸出BitDecomp(c1)?

下面分析該方案的安全性。

定理1 選擇參數(shù)（n, χ, q）使小多項式比問題和環(huán) LWE問題的困難性假設(shè)成立。h和hsi+2ei(i=1,…,l)如全同態(tài)加密方案所述，則分布（h，hsi+2ei）與Rq×Rq上均勻選取的元素是不可區(qū)分的。

證明 對于任意的i，根據(jù)加密算法的定義，hsi+2ei相當(dāng)于對0的加密。根據(jù)文獻(xiàn)[11]中的小多項式比問題假設(shè)，gf?1與Rq上均勻選取的元素不可區(qū)分，所以，公鑰h=2gf?1也是與Rq上均勻選取的元素不可區(qū)分。又根據(jù)文獻(xiàn)[14]中RLWE困難性的假設(shè)，hsi+2ei與Rq上均勻選取的元素不可區(qū)分，所以，密文ci與Rq上均勻選取的元素不可區(qū)分。由此證明了上述全同態(tài)加密方案的安全性。

下面從同態(tài)性和噪聲約減 2個角度進(jìn)行分析，從而說明上述方案的正確性。

4.1 同態(tài)性分析

由于方案的加法同態(tài)性是顯然的，所以只關(guān)注其乘法同態(tài)性。

由于v1、BitDecomp(c1)和v2中的元素都是小的，根據(jù)解密算法可以正確解密。因此方案具有乘法同態(tài)性。

4.2 密文計算的噪聲分析

本節(jié)對上述方案的加法和乘法的噪聲進(jìn)行分析，從而說明方案可以進(jìn)行多項式深度的同態(tài)密文電路計算。

1) 加法噪聲分析

根據(jù)方案的加法定義，令c+= c1+c2，則有

2) 乘法噪聲分析

根據(jù)乘法定義，令 c×=BitDecomp(c1)?c2∈，則有 c×f=m1m2Powerof2(f) + 2m2v1+ 2BitDecomp(c1)?v2∈。令c1j是矩陣BitDecomp(c1)中的第j行向量，則c1j中有l(wèi)+1個系數(shù)為0或1的多項式。另外根據(jù)≤3nB2+nB，得到≤nl(3nB2+nB)= nlE。令N=nl≈nlogq，有≤E，由此可知c×的噪聲為(N+1)E。

下面分析深度為L的密文電路計算的噪聲。這里只考慮乘法，因為乘法的噪聲增長遠(yuǎn)大于加法的噪聲增長。首先，分析深度為2的乘法電路，令1×c和2×c是經(jīng)過深度為 1的乘法電路計算的結(jié)果，其噪聲分別為 v1′和 v2′，由上可知≤(N+1)E。經(jīng)過第2層乘法電路計算后，其結(jié)果記為，則有2BitDecomp(c1)?v2′。由于≤(N+1)E，所以≤N(N+1)E。另外(N+1)E，所以的噪聲為(N+1)2E。以此類推，經(jīng)過深度為L的電路計算，其噪聲至多為(N+1)LE。只要(N+1)LE不超過，密文就能夠正確解密。

4.3 乘法計算優(yōu)化

在上述2個密文乘法計算中，噪聲主要依賴于第一個密文（被乘數(shù)）的噪聲，所以，改變乘法順序可以優(yōu)化密文計算。該事實(shí)也在文獻(xiàn)[18]中觀察到。如(i=1,…,4)是4個初始密文，每個密文中的噪聲都為 E。上述電路乘法是兩兩相乘，即將乘積 c1c2c3c4分成 c5←c1c2和c6←c3c4，然后再計算c5c6。如果按照順序方式乘積，首先計算c5←c1c2，再計算c6←c5c3，最后計算 c7←c6c4。根據(jù)上面的噪聲分析，c5的噪聲是(N+1)E，c6的噪聲是(N+1)E+NE=(2N+1)E，c7的噪聲是(2N+1)E+NE=(3N+1)E。以此類推，那么經(jīng)過深度為L的電路計算，其噪聲至多為(LN+1)E。這意味著對同樣的L，經(jīng)過乘法優(yōu)化，q可以取為關(guān)于n的多項式，即q可以變得更小，使計算效率提高?；蛘哒f對于同樣的q，電路深度L可以更深。關(guān)于全同態(tài)加密電路深度與具體參數(shù)問題可以參考文獻(xiàn)[19～21]。

5 結(jié)束語

環(huán)LWE上的NTRU基本加密方案的密文形式非常簡單，就是Rq上的一個多項式，因此其乘積形式也非常自然簡單，就是2個密文多項式的乘積，但其密文乘積的噪聲主要依賴于乘積中的第一個密文，所以密文乘積的噪聲過大，導(dǎo)致一次乘法也進(jìn)行不了。為了約減噪聲，本文將第一個密文表示成位的形式，將第2個密文由多項式提升到向量，設(shè)計了一個環(huán)LWE上的NTRU型BGN同態(tài)加密方案。該BGN加密方案的乘法密文的長度非常短，只是一個多項式，與基本加密方案的密文長度相同。然后，將第一個密文也從多項式提升到向量形式，通過上述約減噪聲的方法獲得了乘法同態(tài)性。由于密文乘積是一個方陣與向量的乘積，所以密文乘積的結(jié)果還是向量，并沒有導(dǎo)致密文乘積的膨脹，從而獲得了一個無需密鑰交換的全同態(tài)加密方案。本文方案與密文是矩陣的GSW全同態(tài)加密相比，具有存儲與傳輸上的優(yōu)勢。

[1] RIVEST R L, ADLEMAN L, DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169-180.

[2] GENTRY C. Fully homomorphic encryption using ideal lattices[C]//The 41st Annual ACM Symposium on Theory of Computing. 2009: 169-178.

[3] SMART N P, VERCAUTEREN F. Fully homomorphic encryption with relatively small key and ciphertext sizes[M]//Public Key Cryptography-PKC 2010. Berlin: Springer, 2010: 420-443.

[4] DIJK M V, GENTRY C, HALEVI S, et al. Fully homomorphic encryption over the integers[M]//Advances in Cryptology-Eurocrypt 2010. Berlin: Springer, 2010: 24-43.

[5] JEAN-SéBASTIEN C, AVRADIP M, NACCACHE D, et al. Fully homomorphic encryption over the integers with shorter public keys[M]//Advances in Cryptology-CRYPTO 2011. Berlin Heidelberg: Springer, 2011: 487-504.

[6] JEAN-SéBASTIEN C, NACCACHE D, TIBOUCHI M. Public key compression and modulus switching for fully homomorphic encryption over the integers[M]//Advances in Cryptology-Eurocrypt 2012. Berlin Heidelberg: Springer, 2012: 446-464.

[7] BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]//IEEE 52nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society. 2011: 97-106.

[8] BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[C]//The 3rd Innovations in Theoretical Computer Science Conference. 2012: 309-325.

[9] BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical gapSVP[M]//Advances in Cryptology-CRYPTO 2012. Berlin Heidelberg: Springer, 2012: 868-886.

[10] GENTRY C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptoticallyfaster, attribute-based[M]//Advances in Cryptology-CRYPTO 2013. Berlin Heidelberg: Springer, 2013: 75-92.

[11] LóPEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]//The 44th Symposium on Theory of Computing. 2012: 1219-1234.

[12] CHEN Z G, WANG J, ZHANG Z N, et al. A fully homomorphic encryption scheme with better key size[J]. China Communications, 2014, 11(9): 89-99.

[13] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]//The 37th Annual ACM Symposium on Theory of Computing. 2005: 84-93.

[14] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[M]//Advances in Cryptology-EUROCRYPT 2010. Berlin Heidelberg: Springer, 2010: 1-23.

[15] STEHLé D, STEINFELD R. Making NTRU as secure as worst-case problems over ideal lattices[M]//Advances in Cryptology-EUROCRYPT 2011. Berlin Heidelberg: Springer, 2011: 27-47.

[16] GENTRY C, HALEVI S, VAIKUNTANATHAN V. A simple BGN-type cryptosystem from LWE[M]//Advances in Cryptology –EUROCRYPT 2010. Berlin Heidelberg: Springer, 2010: 506-522.

[17] BONEH D, GOH E J, NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C]//Theory of Cryptography: Second Theory of Cryptography Conference(TCC 2005). 2005: 325-41.

[18] BRAKERSKI Z, VAIKUNTANATHAN V. Lattice-based FHE as secure as PKE[C]//The 5th Conference on Innovations in Theoretical Computer Science. 2014: 1-12.

[19] 陳智罡, 宋新霞，趙秀鳳. 一個LWE上的短公鑰多位全同態(tài)加密方案[J]. 計算機(jī)研究與發(fā)展, 2016,53(10): 2216-2223. CHEN Z G, SONG X X, ZHAO X F. A multi-bit fully homomorphic encryption with better key size from LWE[J]. Journal of Computer Research and Development, 2016, 53(10): 2216-2223.

[20] 陳智罡, 石亞峰, 宋新霞. 全同態(tài)加密具體安全參數(shù)分析[J]. 密碼學(xué)報, 2016, 3(5): 480-491. CHEN Z G, SHI Y F, SONG X X. Estimating concert security parameters of fully homomorphic encryption[J]. Journal of Cryptologic Research, 2016, 3(5): 480-491.

[21] 陳智罡, 王箭, 宋新霞. 全同態(tài)加密研究[J]. 計算機(jī)應(yīng)用與研究, 2014, 31(6): 1624-1631. CHEN Z G, WANG J, SONG X X. Survey on fully homomorphic encryption[J]. Application Research of Computer, 2014, 31(6): 1624-1631.

NTRU-type fully homomorphic encryption scheme without key switching

SONG Xin-xia1, CHEN Zhi-gang2, ZHOU Guo-min3

(1. College of Junior, Zhejiang Wanli University, Ningbo 315100, China; 2. College of Electronic and Computer, Zhejiang Wanli University, Ningbo 315100, China; 3. Department of Computer and Information Technology, Zhejiang Police College, Hangzhou 310053, China)

In order to construct a fully homomorphic encryption scheme based on NTRU cryptosystem from ring learning with errors, noise growth and homomorphic property in the NTRU cryptosystem were analyzed. The concept of zero homomorphic encryption was introdced and that the NTRU cryptosystem was zero homomorphic encryption was shown. A BGN homomorphic encryption scheme and a fully homomorphic encryption scheme were proposed based on the NTRU cryptosystem. In the proposed NTRU-type fully homomorphic encryption scheme, the secret key doesn’t change in homomorphic multiplications. Thus a fully homomorphic encryption scheme can be obtained without key switching that was used in the previous fully homomorphic encryption schemes. Moreover, the ciphertext is a vector in the proposed NTRU-type fully homomorphic encryption scheme which has the advantage of storage and transmission compared to GSW fully homomorphic encryption scheme where the ciphertext is a matrix.

fully homomorphic encryption, NTRU cryptosystem, ring learning with errors, key switching, BGN homomorphic encryption

TP309.7

A

10.11959/j.issn.2096-109x.2017.00117

宋新霞（1973-），女，陜西戶縣人，浙江萬里學(xué)院副教授，主要研究方向為代數(shù)密碼。

陳智罡（1972-），男，四川資中人，博士，浙江萬里學(xué)院副教授，主要研究方向為全同態(tài)加密、格公鑰密碼學(xué)。

周國民（1971-），男，浙江義烏人，浙江警察學(xué)院副教授，主要研究方向為網(wǎng)絡(luò)安全與執(zhí)法。

2016-09-10；

2016-10-30。通信作者：陳智罡，zhig.chen@foxmail.com

浙江省自然科學(xué)基金資助項目（No.LYNF020002）；浙江省公益性技術(shù)應(yīng)用研究計劃基金資助項目（No.2017C33079）；NSFC—浙江兩化融合聯(lián)合基金資助項目（No.U1509219）；寧波市自然科學(xué)基金資助項目（No.2016A610226）

Foundation Items: Zhejinag Provincial Natural Science Foundation of China (No.LYNF020002), The Public Projects of Zhejiang Province (No.2017C33079), NSFC-Zhejiang Joint Fund for the Integration of Industrialization Information (No.U1509219), Ningbo Natural Science Foundation (No.2016A610226)