基于Gentry全同態(tài)加密算法公鑰個(gè)數(shù)優(yōu)化的研究

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

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

中圖分類號(hào)：TP309.7

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

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

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

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

（1）選取一個(gè)安全參數(shù)λ，由此變數(shù)可求得、、，其中為私鑰的長(zhǎng)度，為公鑰的個(gè)數(shù)，為q的長(zhǎng)度，其中=O（λ2）、=O（λ5）。（2）、在[2，2]中，選取一個(gè)夠大的奇數(shù)p當(dāng)私鑰，亦即p=（2Z+1） [2，2]。（3）、選取個(gè)亂數(shù)qi及個(gè)亂數(shù)i，其中i （-2，2）、qi （2，2），為i的長(zhǎng)度，且=λ，產(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）對(duì)于每個(gè)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)算：對(duì)任意兩個(gè)密文參數(shù)ci，cj，若想做加法同態(tài)則輸出ci+cj，若想做加法同態(tài)則輸出ci*cj；（2）將（1）運(yùn)算結(jié)果整理成C’=c1⊙c2…◎ct，其中任兩個(gè)密文參數(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，將傳來(lái)的密文進(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ù)的加密算法中，但是在實(shí)際操作上有相當(dāng)大的難度。其中最重要的原因是，產(chǎn)生的一個(gè)公鑰群組需要太多的儲(chǔ)存空間。一般來(lái)說(shuō)，公鑰的大小最少有800M，非常消耗磁盤(pán)的儲(chǔ)存空間。

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

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

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

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

（2）對(duì)于每個(gè)mi做加密，i=1，…，t。加密過(guò)程如下：隨機(jī)從S={-1，0，1}集合中選?。ā?1）個(gè)數(shù)值ai，亦即?ai {-1，0，1}，i=1，…，（’-1）。1）計(jì)算對(duì)aixi從1到（’-1）的和數(shù)值記作T；2）在（-2，2）中隨機(jī)選取一個(gè)亂數(shù)γi；3）計(jì)算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á)成一樣的安全性。因?yàn)樵贕entry的算法設(shè)計(jì)中，加密階段對(duì)每一把公鑰只有選取與不選取兩種可能情況，所以若有n把公鑰，以他的加密方案只有2n種公鑰組合方式。而優(yōu)化后的算法中，增添了負(fù)數(shù)的概念，在加密階段對(duì)每一把公鑰有選、不選和取負(fù)值的三種可能。所以若有n把公鑰，則優(yōu)化后的加密方案有3n種公鑰組合方式。例如：若加密算法中使用1000把公鑰，則公鑰組合共有21000種可能性。但經(jīng)優(yōu)化后則只需要log3（21000）640把公鑰即可達(dá)成一樣的安全性，大大縮減了大約1/3的時(shí)間去產(chǎn)生公鑰，也減少了公鑰的存儲(chǔ)空間，更符合實(shí)際的應(yīng)用。

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]湯殿華，祝世雄，曹云飛.一個(gè)較快速的整數(shù)上的全同態(tài)加密方案[J].計(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.

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

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