緊致優(yōu)化DGHV全同態(tài)加密方案*

湯殿華，曹云飛，楊浩淼

0 引言

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

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

Gentry的方案基于理想格數(shù)學(xué)結(jié)構(gòu)，運(yùn)算復(fù)雜。Dijk等人避免了這種復(fù)雜的代數(shù)結(jié)構(gòu)，提出一個(gè)整數(shù)上的全同態(tài)加密方案—DGHV方案［7］，其運(yùn)算完全基于整數(shù)運(yùn)算，更容易理解。全同態(tài)加密方案除了滿足能夠無限計(jì)算“同態(tài)加”和“同態(tài)乘”之外，還應(yīng)滿足緊致性:密文尺寸需要保持有界，不能隨著同態(tài)操作而無限增大。在DGHV方案中，其類同態(tài)方案(Somewhat Homomorphic Scheme)的同態(tài)乘和同態(tài)加操作沒有進(jìn)行類似于加密算法中的模運(yùn)算，導(dǎo)致了密文尺寸的不斷增加。為了保證全同態(tài)加密方案的緊致性，DGHV方案的同態(tài)解密算法，在更新密文噪聲的同時(shí)，也將密文尺寸控制在?O(λ7)的水平，但在同態(tài)解密算法的內(nèi)部運(yùn)算過程中，密文數(shù)據(jù)的尺寸仍在不斷增加。

文中給出了一個(gè)緊致優(yōu)化技術(shù)，使得DGHV方案中類同態(tài)方案和全同態(tài)方案均滿足緊致性要求，密文尺寸始終保持在?O(λ5)以內(nèi)，而且保證了同態(tài)解密算法的內(nèi)部運(yùn)算的密文尺寸不增加。

1 準(zhǔn)備知識

定義1 同態(tài)加密方案。同態(tài)加密方案由四個(gè)概率多項(xiàng)式時(shí)間算法組成 HE=(KeyGen，Enc，Dec，Evaluate):

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

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

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

Evaluate:輸入公鑰 pk，t輸入線電路 Cir，一組密文 →c=(c1，c2，…，ct)，其中 ci=Encpk(mi)。輸出 c*=Evaluate(pk，Cir，→c)，且滿足 Dec(sk，c*)=Cir(m1，m2，…，mt)。

由定義1可以看出，同態(tài)加密方案除了包括傳統(tǒng)公鑰加密方案的所有算法(KeyGen，Enc，Dec)之外，還包括一個(gè)額外的運(yùn)算算法Evaluate。該算法是用于同態(tài)處理一個(gè)電路，是方案同態(tài)性的體現(xiàn)，能夠在不解密條件下，對密文的操作實(shí)現(xiàn)了相應(yīng)的明文操作，并且操作結(jié)果也為密態(tài)。

文中研究的方案是單比特的加密形式，即明文空間為{0，1}，所運(yùn)算的電路為布爾電路，這樣就可以對應(yīng)于計(jì)算機(jī)中的數(shù)字邏輯電路，而計(jì)算機(jī)所完成的所有程序都是通過數(shù)字邏輯電路執(zhí)行，如果方案能夠同態(tài)運(yùn)算所有的布爾電路，那么就可以密態(tài)完成計(jì)算機(jī)中所有程序及服務(wù)。

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

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

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

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

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

定理1自舉轉(zhuǎn)化定理。如果一個(gè)同態(tài)加密方案HE是能夠同態(tài)計(jì)算“自身解密電路”或“解密電路加上額外的門電路”，且滿足循環(huán)安全，那么該方案可以轉(zhuǎn)化為一個(gè)全同態(tài)加密方案。

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

本節(jié)描述Dijk等人所提出的DGHV方案［7］，其中包括用于構(gòu)造全同態(tài)加密方案的基石—somewhat同態(tài)加密方案，和DGHV全同態(tài)加密方案。

2． 1 Somewhat同態(tài)加密方案

在DGHV方案中需要一些參數(shù)來控制各個(gè)變量的比特長度，其參數(shù)設(shè)置為:ρ=λ，ρ'=2λ，η=?O(λ2)，θ=?O(λ4)，γ=?O(λ5)，τ=γ+λ，其中 λ 為安全參數(shù)。

首先需要定義一個(gè)用于公鑰生成的分布，如下:

Somewhat同態(tài)加密方案 SHE=(KeyGen'，Enc'，Dec'，Evaluate')描述如下:

KeyGen'(λ):根據(jù)輸入的安全參數(shù)λ，隨機(jī)選擇 p←(2? +1)∩［2η-1，2η)。在分布 Dγ，ρ(p)中隨機(jī)選取 τ+1 個(gè)數(shù)(x0，x1，…，xτ)，以致 x0為其中最大的數(shù)，并x0mod p是偶數(shù)。若不滿足條件，重新選取直至滿足條件。令私鑰sk=p，公鑰pk=→x=(x0，x1，…，xτ)。

Enc'(pk，m):消息為 m∈{0，1}。隨機(jī)選擇一個(gè)整數(shù) r∈(-2ρ'，2ρ')和一個(gè) τ+1 維的比特向量 →v∈{0，1}τ+1。計(jì)算密文c=m+2r+2＜→x，→v＞mod x0。

Dec'(sk，c):輸出 m'=(c mod p)mod 2。

Evaluate'(pk，C，c1，c2，…，ct):根據(jù)輸入的公鑰pk，布爾算術(shù)電路 C，和 t個(gè)密文(c1，c2，…，ct)，執(zhí)行整數(shù)上加法和乘法運(yùn)算。輸出電路的結(jié)果c'。

該方案的同態(tài)操作可以分解為兩種基本操作:Add(c0，c1)=c0+c1，Mult(c0，c1)=c0×c1。

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

為了將SHE方案轉(zhuǎn)化為全同態(tài)加密方案，Dijk等人采用“稀疏子集和”對方案的解密算法進(jìn)行了壓縮，使得方案滿足自舉性，應(yīng)用自舉轉(zhuǎn)化，從而獲得全同態(tài)加密方案。其方案FHE=(KeyGen，Enc，Dec，Evaluate)描述如下:

參數(shù)選取:κ=γη/ρ'，Θ=ω(κ log λ)，θ=λ。

KeyGen(λ):運(yùn)行SHE方案的密鑰生成算法產(chǎn)生sk=p，pk=→x，設(shè)置K=?2κ/p?，隨機(jī)選取一個(gè)漢明重量 θ的比特向量 →s∈{0，1}Θ，設(shè)其指標(biāo)集為 S={i|si=1}。均勻隨機(jī)選取 ui∈? ∩［0，2κ+1)，i=0，1，…，Θ-1，使其滿足 K=，令 yi=ui/2κ，i=0，1，…，Θ-1，令向量→y=(y0，y1，…，yΘ-1)。輸出私鑰SK=→s，公鑰PK=(→x，→y)。

Enc(PK，m):調(diào)用SHE方案生成c=Enc'(pk，m)。然后計(jì)算［c·yi］2，i=0，1，…，Θ-1，并對其二進(jìn)制表達(dá)保留小數(shù)點(diǎn)后n=logθ+3位的精度，記為zi。得到新密文 ?c={c，(z0，z1，…，zΘ-1)}。

Evaluate(PK，C，c1，…，ct):將算術(shù)電路 C 中的運(yùn)算替換成整數(shù)上加法和乘法運(yùn)算，每個(gè)運(yùn)算門的輸入線上加入解密電路，擴(kuò)展成增強(qiáng)型解密電路。然后，將密文 c1，c2，…，ct輸入到電路中，首先進(jìn)行重加密(同態(tài)解密)操作來更新密文，然后將更新后的密文c'輸入到電路門中進(jìn)行運(yùn)算，將門輸出作為主密文c″，并使用PK中的→y生成對應(yīng)的其擴(kuò)展密文 →z″，由此構(gòu)成密文 ?c'=(c″，→z″)，如此在電路中運(yùn)算下去。得到最后的輸出。

3 緊致優(yōu)化技術(shù)

由第2節(jié)的方案描述可以看出，導(dǎo)致DGHV方案中somewhat同態(tài)加密方案密文尺寸增加的原因在于:Add(c0，c1)=c0+c1，Mult(c0，c1)=c0×c1沒有進(jìn)行模操作。因此，文中的初始想法思想為:Add(c0，c1)=(c0+c1)mod x0，Mult(c0，c1)=(c0×c1)mod x0。

計(jì)算同態(tài)加法和同態(tài)乘法，需要進(jìn)行模x0。但x0中帶有隨機(jī)噪聲項(xiàng)r0，模x0將引入一個(gè)新的誤差。需要對模操作之后的引入噪聲進(jìn)行分析。

1)同態(tài)加法:由于兩個(gè)密文之和不會(huì)太大，其和的比特長度與輸入密文的尺寸大約一致，模x0只是帶入了一個(gè)小的x0倍數(shù)，可以確定引入的新誤差的上界。

2)同態(tài)乘法:兩個(gè)密文之積將變得非常大，其乘積的比特長度大約兩倍于輸入密文尺寸，模x0運(yùn)算帶入了一個(gè)很大的x0倍數(shù)，同時(shí)帶入的新噪聲也非常大，無法確定其上界。所以我們對乘法進(jìn)行優(yōu)化，確保噪聲的可控性。

3． 1 同態(tài)操作緊致優(yōu)化技術(shù)

優(yōu)化過程需要一些輔助數(shù)據(jù) x'0，x'1，…，x'γ，其都是非?？拷黳的倍數(shù)，與方案的公鑰相似，但其參數(shù)的選取范圍不一樣，主要在于p的倍式因子q'i的選取。

對同態(tài)乘法作修改，c1，c2為兩個(gè)密文，兩個(gè)密文相乘之后，按順序進(jìn)行分別模 x'γ，x'γ-1，…，x'0。即 opt(c1×c2)=(…(((c1×c2)mod x'γ)mod x'γ-1)…)mod x'0。

優(yōu)化后的同態(tài)操作算法為:Add(c0，c1)=(c0+c1)mod x0，Mult(c0，c1)=opt(c1×c2)。

3． 2 噪聲分析

設(shè)m1，m2為兩個(gè)消息比特，由SHE加密算法分別產(chǎn)生其密文c1，c2。

模x0相當(dāng)于加了一個(gè)x0的倍數(shù)，則存在兩個(gè)整數(shù) k1，k2，使得

并記兩個(gè)密文中的噪聲為n1，n2。

1)同態(tài)加法的噪聲分析 SHE．Add(c1，c2):(c1+c2)mod x0

在方案中，|c1|＜x0/2，|c2|＜x0/2。由三角不等式得|c1+c2|＜x0。又由于|(c1+c2)mod x0|≤x0/2，根據(jù)這兩個(gè)不等式可得|(c1+c2)mod x0-(c1+c2)|≤(3/2)x0。設(shè)同態(tài)加法中引入的x0倍數(shù)因子為kAdd。

c1+c2mod x0=c1+c2+kAddx0，|kAddx0|=|(c1+c2)mod x0-(c1+c2)|≤x0，由此得|kAdd|≤1。

SHE．Add(c1，c2)所獲得新密文的噪聲為:

2)同態(tài)乘法的噪聲分析 SHE．Mult(c1，c2):opt(c1×c2)

首先分析模 x'γ所帶入的倍數(shù)因子 kMult，γ，即(c1×c2)mod x'γ=c1×c2+kMult，γx'γ。

加密算法產(chǎn)生的新密文c的比特長度為γ，c1×c2的比特長度最多為 2γ，由于 x'i∈［2γ+i-1，2γ+i)，則有|c1×c2|≤22γ＜2x'γ。結(jié)合|(c1×c2)mod x'γ|≤x'γ/2，利用三角不等式有|kMult，γx'γ|=|(c1×c2)mod x'γ-(c1+c2)|≤(5/2)x'γ，顯然 |kMult，γ|≤2。

按照優(yōu)化算法的模順序，分析在模 x'γ-1過程中，所帶入的倍數(shù)因子 kMult，γ-1，即如下等式:

與模 x'γ噪聲分析思路類似，根據(jù)|(c1×c2)·mod x'γ|≤ x'γ/2 ＜ 22γ-1＜ 2x'γ-1和 |(c1× c2mod x'γ)mod x'γ-1|≤x'γ-1/2，可以得到|kMult，γ-1|≤2。

同理分析可得|kMult，i|≤2，i=0，1，…，γ-1。

SHE．Mult(c1，c2)所獲得新密文的噪聲:nMult=那 么 |nMult|＜ |n1|· |n2|+(γ+1)·2ρ+1

綜上所述，同態(tài)加法運(yùn)算帶入的新噪聲為2ρ，在同態(tài)乘法運(yùn)算帶入的新噪聲為(γ+1)·2ρ+1。新的噪聲加入，會(huì)降低方案的運(yùn)算能力，下面將對其詳細(xì)分析，并給出方案的支持同態(tài)運(yùn)算的多項(xiàng)式次數(shù)。

3． 3 優(yōu)化方案的同態(tài)運(yùn)算能力

根據(jù)Dijk等人的分析思路，將所需運(yùn)算的電路C 表示成 t個(gè)變元的多項(xiàng)式 f(x1，x2，…，xt)，設(shè)其多項(xiàng)式次數(shù)為d。這里把SHE能夠同態(tài)運(yùn)算多項(xiàng)式次數(shù)d作為方案的同態(tài)能力指標(biāo)估計(jì)。由文獻(xiàn)［7］引理A．1可知，Enc'(pk，m)所產(chǎn)生的新鮮密文的噪聲為τ·2ρ+3，并記為X;同態(tài)加法中引入的新噪聲記為 A=2ρ;同態(tài)乘法引入的新噪聲記為 B=(γ+1)·2ρ+1。

首先分析一個(gè)d次單項(xiàng)式xi1xi2xi3…xid的噪聲，由于乘法中噪聲變化為|nMult|＜|n1|·|n2|+B。則d次單項(xiàng)式的噪聲為:(…(((X·X+B)·X+B)·X+B)…)X+B，歸納得Xd+BXd-2+BXd-3+…+BX+B=Xd+B·(Xd-1-1)/(X-1)。對多項(xiàng)式 f(x1，x2，…，xt)進(jìn)行放縮處理，將其每一項(xiàng)都放大為一個(gè)d次單項(xiàng)式，由于 f(x1，x2，…，xt)一共有‖f‖1項(xiàng)，則將進(jìn)行‖f‖1-1個(gè)同態(tài)加法，引入新噪聲為(‖f‖1-1)A。綜合分析可以得出經(jīng)過 f(x1，x2，…，xt)同態(tài)運(yùn)算之后的噪聲為:‖f‖1(Xd+B·(Xd-1-1)/(X-1))+(‖f‖1-1)A，為了保證解密的正確，噪聲上界不能超過p/8。那么可以得到以下等式:

代入 X= τ·2ρ+3，A=2ρ，B=(γ+1)·2ρ+1。B/(X-1)≈(γ+1)/4τ，B/X(X-1)≈(γ+1)/τ2·2ρ+5，忽略此這兩項(xiàng)。粗略得到方案的支持同態(tài)運(yùn)算的多項(xiàng)式次數(shù)，即同態(tài)運(yùn)算能力為:

4 結(jié)語

緊致性是全同態(tài)加密方案的必要條件。DGHV方案通過同態(tài)解密算法取得整個(gè)全同態(tài)加密方案的緊致性，導(dǎo)致每個(gè)電路輸出的密文尺寸為?O(λ7)。文中在同態(tài)操作中引入模運(yùn)算，并對同態(tài)乘法進(jìn)行優(yōu)化，使得DGHV方案在同態(tài)操作取得緊致性，將密文尺寸控制在?O(λ5)，但由于需要在同態(tài)操作時(shí)進(jìn)行γ個(gè)模運(yùn)算，因此該優(yōu)化技術(shù)增加了同態(tài)操作的計(jì)算量。再則，文中的緊致性技術(shù)使得同態(tài)解密算法［8］內(nèi)部運(yùn)算中的密文尺寸不增長，這可以使得全同態(tài)加密方案中κ的選取由=γη/ρ'變成γ+2，參數(shù)設(shè)置變得更小。

［1］ 張盛勇，陳世康．網(wǎng)絡(luò)編碼的安全問題初探［J］．通信技術(shù)，2012，45(01):105-107．

ZHANG Sheng-yong，CHEN Shi-kang．Explortion on Security of Network Coding［J］．Communications Technology，2012(01):105-107．

［2］ RIVEST L R，SHAMIR A，ADLEMAN L．A Method for Obtaining Digital Signatures Public Key Cryptosystem［J］．Communication of ACM，1978，21(01):120-126．

［3］ ELGAMAL T．A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms［J］．Information Theory ，IEEE Transactions，1985，31(04):469-472．

［4］ PAILLIER P．Public-key Cryptosystems based on Composite Degree Residuosity Classes［C］//In J．Stern(Ed．)，EUROCRYPT'99．［s．l．］:Springer，1999:223-238．

［5］ RIVEST L R，ADLEMAN L，DERTOUZOSL M．On Data Banks and Privacy Homomorphisms［C］//In Foundations of Secure Computation．［s．l．］:Academic Press，1978:169-180．

［6］ GENTRY C．Fully Homomorphic Encryption Using Ideal Lattices［C］//In STOC'09．［s．l．］:ACM，2009:169-178．

［7］ DIJK VAN M，GENTRY C，HALEVIS，et al．Fully Homomorphic Encryption over the Integers［C］//In Proc．of Eurocrypt．［s．l．］:Springer，2010:24-43．

［8］ 湯殿華，祝世雄，曹云飛．整數(shù)上全同態(tài)加密方案的重加密技術(shù)［J］．信息安全與通信保密，2012(01):76-79．

TANG Dian-hua，ZHU Shi-xiong，CAO Yun-fei，Recrypt Technology of A Fully Homomorphic Encryption over Scheme Integers［J］．Information Security and Communictions Privacy，2012(01):76-79．