摘 要：Gentry的全同態(tài)加密算法（Fully Homomorphic Encryption）運(yùn)算需要大量的空間存儲所需要的公鑰，給實際操作帶來一定的難度，本文提出了對全同態(tài)加密算法的優(yōu)化，在不影響安全性的同時，節(jié)省了系統(tǒng)加密時間，減少公鑰的存儲空間，提高了算法的可操作性和運(yùn)算效率。

關(guān)鍵詞：全同態(tài)加密算法；公鑰；云計算；密碼學(xué)

中圖分類號：TP309.7

隨著科技的日新月異，造就了當(dāng)今的數(shù)字化時代，云計算的出現(xiàn)讓人們隨時可以在云終端去接收或發(fā)送他們所需要的網(wǎng)上資源，使信息的傳遞變得越來越方便。但在便利性的同時，也突顯出了安全性及隱私性的重要。雖然我們知道信息加密是最為安全的做法，但當(dāng)需要對這些加密后的信息進(jìn)行處理運(yùn)算時，必須先將這些加密后的密文進(jìn)行解密再進(jìn)行運(yùn)算，如此一來，不僅造成安全上的風(fēng)險，更使運(yùn)算的效率降低。為了解決安全性上的疑慮，許多學(xué)者份研究如何設(shè)計同態(tài)加密算法來確保資料的安全性及正確性。其中，最為著名的就是Gentry的全同態(tài)加密算法。

1 Gentry全同態(tài)加密算法

Gentry全同態(tài)加密算法的思想共分成四個部分，分別是：密鑰生成、加密算法、同態(tài)運(yùn)算和解密算法。

1.1 密鑰生成（KeyGen（λ））：（其中輸入：λ，輸出：私鑰ρ、公鑰xi）

（1）選取一個安全參數(shù)λ，由此變數(shù)可求得、、，其中為私鑰的長度，為公鑰的個數(shù)，為q的長度，其中=O（λ2）、=O（λ5）。（2）、在[2，2]中，選取一個夠大的奇數(shù)p當(dāng)私鑰，亦即p=（2Z+1） [2，2]。（3）、選取個亂數(shù)qi及個亂數(shù)i，其中i （-2，2）、qi （2，2），為i的長度，且=λ，產(chǎn)生的公鑰為xi=pqi+2i，i=0，…，（-1），其中x0必須是奇數(shù)，而且x0=max{xi|?i∈[0，（）]}，'為x0除p后的余數(shù)且必須為偶數(shù)。

1.2 加密算法Encrypt（pk，m）：（輸入：xi、明文mi {0，1}，輸出：密文C）

（1）假設(shè)明文有t位元，將明文拆解成單一位元的數(shù)字，也就是分成{m1，m2，…，mt，}，?i，mi {0，1}；（2）對于每個mi做加密，i=1，…，t；（3）得到密文C={c1，c2，…，ct}。

1.3 同態(tài)運(yùn)算（Evaluate（pk，f，c1，c2，…，ct））：（輸入：f、c i、pk，輸出：c）

（1）將密文傳送到運(yùn)算端運(yùn)算：對任意兩個密文參數(shù)ci，cj，若想做加法同態(tài)則輸出ci+cj，若想做加法同態(tài)則輸出ci*cj；（2）將（1）運(yùn)算結(jié)果整理成C’=c1⊙c2…◎ct，其中任兩個密文參數(shù)ci，cj中間的運(yùn)算元不一定相等。

1.4 解密算法（Decrypt（sk，c））（輸入：p、c，輸出：m’）

由User輸入：，產(chǎn)生：密鑰SK。密文組：c1，c2，…，ct。for each ci=（mi+2i+∑i∈sxj）mod x0，將傳來的密文進(jìn)行運(yùn)算Evall（c1，c2，…，ct）=C。并運(yùn)算后回傳給User，并由User端解密，密文解密的明文m’=（c mod p）mod 2。

2 同態(tài)加密算法分析

2.1 同態(tài)加密算法正確性

假設(shè)明文為兩位元數(shù)字（m1||m2），且公鑰為xi=pqi+2i，i=0，…，（-1）、私鑰為p。所以密文C={c1，c2}={m1+21+∑j∈s1 xj，m2+22+∑k∈s2 xk}。同態(tài)運(yùn)算以加法為例（乘法也一樣）：c1+c2=m1+21+∑j∈s1 xj +m2+22+∑k∈s2 xk=p（∑j∈s1 qj）+2（1+∑j∈s1 j+2+∑k∈s2 ）+（m1+m2）。解密：（（c1+c）mod p）mod 2=（m1+m2），所以符合加法同態(tài)

2.2 同態(tài)加密算法算法的資源消耗分析

雖然Gentry算法可以被用在任意函數(shù)的加密算法中，但是在實際操作上有相當(dāng)大的難度。其中最重要的原因是，產(chǎn)生的一個公鑰群組需要太多的儲存空間。一般來說，公鑰的大小最少有800M，非常消耗磁盤的儲存空間。

3 FHE算法的優(yōu)化

針對Gentry的FHE算法設(shè)計，我們優(yōu)化的過程中仍采用Gentry的FHE金鑰生成Encrypt（）、同態(tài)運(yùn)算（Evaluate（pk，f，c1，c2，…，ct））和解密算法（Decrypt（sk，c））階段的算法設(shè)計思想，而在加密算法（Encrypt（pk，mi {0，1}））階段，我們采取優(yōu)化縮減公鑰個數(shù)的方法，設(shè)計出新的加密方案，以達(dá)到提高效率的目的。

加密算法（（Encrypt （pk，mi）：（輸入：xi、明文mi {0，1}，輸出：密文C）

（1）假設(shè)明文有t位元，將明文拆解成單一位元的數(shù)字，也就是分成{m1，m2，…，mt}，?i，mi {0，1}。

（2）對于每個mi做加密，i=1，…，t。加密過程如下：隨機(jī)從S={-1，0，1}集合中選?。ā?1）個數(shù)值ai，亦即?ai {-1，0，1}，i=1，…，（’-1）。1）計算對aixi從1到（’-1）的和數(shù)值記作T；2）在（-2，2）中隨機(jī)選取一個亂數(shù)γi；3）計算W=mi+2i+T；4）隨機(jī)選取xk { 1， 2，…， （’-1）}；5）選取Ai如果0x0或Wi<-x0則Ai=0；6）密文ci=（mi+2γi+T+AiXk）mod x0。

4 改進(jìn)后的算法分析

優(yōu)化后的算法只需更少的公鑰即可達(dá)成一樣的安全性。因為在Gentry的算法設(shè)計中，加密階段對每一把公鑰只有選取與不選取兩種可能情況，所以若有n把公鑰，以他的加密方案只有2n種公鑰組合方式。而優(yōu)化后的算法中，增添了負(fù)數(shù)的概念，在加密階段對每一把公鑰有選、不選和取負(fù)值的三種可能。所以若有n把公鑰，則優(yōu)化后的加密方案有3n種公鑰組合方式。例如：若加密算法中使用1000把公鑰，則公鑰組合共有21000種可能性。但經(jīng)優(yōu)化后則只需要log3（21000）640把公鑰即可達(dá)成一樣的安全性，大大縮減了大約1/3的時間去產(chǎn)生公鑰，也減少了公鑰的存儲空間，更符合實際的應(yīng)用。

在金鑰生成以及加密時間方面，由于優(yōu)化后所需要的公開金鑰數(shù)量低于Gentry的金鑰個數(shù)，因此算法優(yōu)化后金鑰生成只需約原算法的67%的時間即可完成。而更重要的是在加密過程中，所需要的時間也只需要80%的時間即可完成。并且優(yōu)化后的算法增加了兩個變數(shù)AiXk，其目的是為了確保資料的安全性不變。

5 結(jié)束語

Gentry的全同態(tài)加密算法經(jīng)優(yōu)化后，其加密所需要的公鑰不需要占據(jù)太多的存儲空間或資源，利用減少公鑰個數(shù)來達(dá)到降低所需空間，并且在資料隱私不影響的情況下，同樣保證了對資料進(jìn)行加密及同態(tài)運(yùn)算的正確性。因此，優(yōu)化后的Gentry全同態(tài)算法，降低公鑰所需的空間更易實際操作，在資料庫的運(yùn)算及存儲上的應(yīng)用也更廣泛。

參考文獻(xiàn)：

[1]湯殿華，祝世雄，曹云飛.一個較快速的整數(shù)上的全同態(tài)加密方案[J].計算機(jī)工程與應(yīng)用，2012（28）：117-122.

[2]BONEH D，GENTRY.A fully homomorphic encryption scheme[D].Stanford：Stanford University，2009.

[3]Gentry C and Halevi S.Implementing gentry’s fullyhomomorphic encryption scheme[A].EUROCRYPT 2011 Proceedings，Tallinn，Estonia[C]，2011：129-148.

[4]Stehle D and Steinfeld R.Faster fully homomorphic encryption[A].ASIACRYPT 2010 Proceedings，Singapore[C]，2010：377-394.

作者簡介：胡勇祥（1976.09-），男，湖北黃岡人，技術(shù)部主任，講師，碩士研究生，研究方向：計算機(jī)網(wǎng)絡(luò)及密碼學(xué)。

作者單位：黃岡師范學(xué)院，湖北黃岡 438000