湯殿華 ， 曹云飛

（1.保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；2.中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引 言

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

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

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

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

1 準(zhǔn)備知識(shí)

1.1 符號(hào)定義

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

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

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

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

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

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

1.2 離散高斯分布

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

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

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

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

1.3 RLWE問(wèn)題

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

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

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

當(dāng)s取自分布χ時(shí)，DRLWEn,q,χ仍然是一個(gè)困難問(wèn)題。

1.4 DSPR問(wèn)題

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

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

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

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

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

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

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

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

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

Dec：輸入私鑰和密文c，進(jìn)行解密運(yùn)算，輸出明文m′。

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

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

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

則稱(chēng)該方案為C-同態(tài)，或者方案對(duì)于一個(gè)電路集合C 是正確的，同時(shí)也稱(chēng)C為方案HE的可許電路集合，當(dāng)C是一個(gè)有限電路集合時(shí)，也稱(chēng)方案為類(lèi)同態(tài)加密方案。

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

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

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

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

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

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

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

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

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

可以將BDI寫(xiě)成矩陣表達(dá)的形式為：

對(duì)于m×n階矩陣其比特分解算法BD和比特分解逆算法BDI類(lèi)似。即將每一行看著1個(gè)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))。類(lèi)似可以定義Rq上向量的比特分解逆算法，以及Rq上矩陣的比特分解算法和逆分解算法。

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

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

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

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

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

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

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

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

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

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

2.2 解密正確性條件

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

證明：根據(jù)類(lèi)同態(tài)加密方案的解密算法，存在多項(xiàng)式向量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 則有：

進(jìn)一步得到：

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

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

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

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

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

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

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

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

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

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

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

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

同態(tài)乘法的噪聲分析相對(duì)較為復(fù)雜。令消息m∈Rt、m′∈Rt在Rt上的乘法運(yùn)算為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)加法的噪聲增長(zhǎng)比較小，可粗略看為兩個(gè)密文的噪聲相加；同態(tài)乘法的噪聲增長(zhǎng)較大，可粗略看為兩個(gè)密文噪聲的線性組合。綜上所述，本方案的同態(tài)操作的噪聲增長(zhǎng)均為線性。

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

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

其中：

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

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

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

則：E1＜A·E+B。

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

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

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

對(duì)該不等式求解，得到：

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

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

根據(jù)文獻(xiàn)[8]對(duì)解密結(jié)構(gòu)的分析，本方案當(dāng)t=2時(shí)解密電路的電路深度為：

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

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

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

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

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

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

通過(guò)分析可知，c*所由私鑰f*解密，對(duì)應(yīng)的消息仍然為m。

3 安全性證明

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

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

證明：采用Stehle和Steinfeld在文獻(xiàn)[12]中的證明方法來(lái)證明方案安全性，具體如下：

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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