一種適用于云存儲的改進全同態(tài)加密方案

武警工程大學(xué)研究生管理大隊 胡人遠

一種適用于云存儲的改進全同態(tài)加密方案

武警工程大學(xué)研究生管理大隊 胡人遠

【摘要】全同態(tài)加密思想在云存儲、密文檢索等多方面有重要應(yīng)用，為了得到更適合云存儲的全同態(tài)加密方案，對現(xiàn)有的全同態(tài)加密方案研究現(xiàn)狀進行了分析對比，提出一種基于DGHV方案的改進全同態(tài)加密方案。在保證方案安全性的前提下，將單次加密數(shù)據(jù)量提高到3bit。經(jīng)論證，改進后單次加密數(shù)據(jù)量提高的同時，公鑰尺寸大大縮小，且降低了計算復(fù)雜度，適用于云存儲平臺。

【關(guān)鍵詞】全同態(tài)加密；云存儲；密文檢索

隨著云計算技術(shù)的不斷推廣，信息數(shù)據(jù)的存儲與管理成為云計算領(lǐng)域的最熱門話題之一。云存儲技術(shù)作為解決信息數(shù)據(jù)存儲和管理的有效途徑之一，由并行存儲、分布式存儲和網(wǎng)格存儲發(fā)展而來，但畢竟作為一個新興技術(shù)，各方面仍不是很成熟，尤其是安全方面。使用云計算的外包存儲服務(wù)［1］就不可避免的要將用戶數(shù)據(jù)上傳至云端，用戶在失去數(shù)據(jù)絕對擁有權(quán)和控制權(quán)的情況下，如何保護用戶的數(shù)據(jù)安全，這將是云存儲面臨的最大實際問題。在此基礎(chǔ)上，在云存儲平臺實現(xiàn)密文計算，密文檢索等功能，這需要繼續(xù)探索改進數(shù)據(jù)加密技術(shù)。

上世紀70年代， Rivest等人［2］提出了FHE問題，希望通過全同態(tài)的性質(zhì)可以在不解密密文的情況下，對密文進行加減乘除運算，且運算后的結(jié)果解密后與對應(yīng)明文運算后的結(jié)果保持一致。隨后，國內(nèi)外學(xué)者對同態(tài)加密進行了大量的研究，但產(chǎn)生的許多同態(tài)加密方案并沒有達到全同態(tài)加密的要求。直至2009年，IBM研究員Gentry在該領(lǐng)域取得了重大突破，提出基于理想格的全同態(tài)加密方案［3］，并其博士論文［4］中對全同態(tài)加密進行了更深入的論述。這兩篇文章給全同態(tài)加密研究領(lǐng)域點亮了前進的方向。為實現(xiàn)密文檢索又提供了一種可行性技術(shù)。

目前，國內(nèi)關(guān)于整數(shù)上的全同態(tài)加密技術(shù)的研究成果大多停留在基于現(xiàn)有方案基礎(chǔ)提出的改進方案的水平。如湯殿華等人［5］在文獻［3］的基礎(chǔ)上進行改進，與文獻［3］相比，具有較小的公鑰尺寸、計算效率更高的特點，但是在安全性上存在缺陷。林如磊等人［6］提出一次加密2bit明文，將模2運算改為模4運算，在效率方面進一步提高，并對方案安全性進行分析。全同態(tài)加密技術(shù)研究還有一個方向是基于LWE困難問題的，但能否運用到云存儲上仍需進一步研究分析。

本文主要研究分析云存儲的性質(zhì)特點，結(jié)合國內(nèi)相關(guān)的改進思路，對文獻［7］中的整數(shù)上的全同態(tài)加密方案進行了改進，將單次加密數(shù)據(jù)量由1bit改進為3bit，并使用Gen-try的全同態(tài)加密思想，構(gòu)造全同態(tài)加密方案，并采用文獻［7］中的技術(shù)使公鑰尺寸大大縮小，使方案具有更高的效率。

1 理論基礎(chǔ)

1.1 同態(tài)加密原理

同態(tài)是近世代數(shù)理論中的一個基礎(chǔ)概念。

假設(shè)加密函數(shù)為EK解密函數(shù)為DK運算操作為a和明文M（m0，m1，…，mi），公式為a（DK（M（m0，m1，…，mi）））= D（a（M（m0，m1，…，mi）））

FHE加密方案包含有以下四種算法：

密鑰部分（Key） ： 根據(jù)給出的參數(shù)γ， 生成私鑰sk和公鑰pk；

加密部分（Enc） ： 明文m通過公鑰pk加密后獲得密文c；

解密部分（Dec）： 明文m由私鑰解密密文c后得到

密文運算算法（Evaluate） ： 輸出t個輸入的電路C和公鑰pk，還有明文對應(yīng)的密文c。用公式可以表示輸出為Evaluate（pk，C，c）。

1.2 DGHV全同態(tài)加密

DGHV的具體方案［7］為：

（1）構(gòu)造一個somewhat加密方案。

生成密鑰：選取p作為密鑰，其中p滿足的條件為：p是一個大素數(shù)且p∈［2η-1，2η）；

加密部分：1bit的明文m∈｛0，1｝，m加密生成的密文c=m+pq+2r，在加密過程中隨機生成q和r，其中q是一個遠大于p的較大整數(shù)，r是一個較小的整數(shù)且2r小于p/2；

解密部分：解密過程為明文m =（cmodp）mod2。

（2）將somewhat方案構(gòu)造成非對稱公鑰方案。

由于q是公開的，那么如果直接將pq作為公鑰，則私鑰p很容易被計算出來，所以假設(shè)一個集合｛xi，xi=pqi+2ri｝ ，選擇集合中的任意項構(gòu)成子集S，將子集中元素的和作為公鑰sum（s）=，式子可表示為： c=m+2r+sum（s）。那么具有隨機性質(zhì)的公鑰，則可以有效保證密文不被破解出來

（3）使用壓縮解密技術(shù)對密文不斷刷新，控制噪聲的增量。

由解密算法可以發(fā)現(xiàn)，當密文cmodp （p/2，p/2）之間時，則能解密得出明文。如果超出這個范圍則無法還原明文。每次運算前，對“新鮮”密文，進行一次“加密”，從而使要進行運算操作的密文噪聲大小控制在一定范圍之內(nèi)，從而達到消減噪聲的目的。從而保證運算后的新密文能夠被成功解密。

2 改進的基于整數(shù)的全同態(tài)加密方案

2.1 改進方案原理

通過對文獻［7］的研究與分析，提出一種能一次加密3bit密文的基于整數(shù)的全同態(tài)加密方案，其單次加密數(shù)據(jù)量更大，公鑰更小。

首先對文中使用的符號進行說明：

λ：安全參數(shù)；

ρ：噪聲的長度，為抵抗暴力攻擊，噪聲長度應(yīng)該取ρ=ω（logλ）；

η： 私鑰的二進制長度，私鑰長度滿足η≥ρΘ（λlog2λ）；

γ：公鑰的二進制長度，私鑰長度滿足γ=ω（η2logλ）；

τ： 公鑰的個數(shù)，τ≥γ+ω（logλ），文中需要的公鑰個數(shù)為2。

其中ω（）是高階無窮大量。

2.2 構(gòu)造全同態(tài)加密方案

2.2.1 構(gòu)造部分同態(tài)的somewhat方案

將模2運算改為模23運算，單次可加密3bit明文信息

（1）KeyGen（λ）：由安全參數(shù)λ生成η比特的密鑰p，令密鑰sk=p。

（2）Encrypt（sk，m）：對m∈｛000，001，010，…，111｝進行加密得c=m+23r+pq，其中，r是ρ比特大小的隨機整數(shù)，q是加密過程中生成γ比特大小的隨機整數(shù)。

（3）Decrypt（sk，c）：m=（cmodp）mod23。

cmodp的值為噪聲大小，只有當|m+23r|＜p/2時，那么噪聲cmodp=m+23r，則才能還原出有效的明文。下面對方案的同態(tài)性進行驗證：

驗證得，構(gòu)造的對稱加密方案既滿足加法同態(tài)又滿足乘法同態(tài)。但是方案中的噪聲會隨著運算次數(shù)的增加而不斷“膨脹”。但噪聲值大于p/2時，則以上等式不成立，即無法解密出有效明文。同時有上述公式可見，在加法同態(tài)運算中噪聲不斷線性增長的，而在乘法同態(tài)運算中呈幾何增長。

2.2.2 轉(zhuǎn)化為公鑰加密體制

需要添加一組“0”的密文作為公鑰，具體方法步驟如下：

（1）KeyGen（λ）：在加密過程中隨機生成η比特的私鑰p，令x0=pq0，且x0是奇數(shù)并符合rp（x0）被23整除。且b=｛0，1｝，1≤i≤，

（2）Encrypt（pk，m）：τ維向量b=（1≤i，j≤，bi，j∈｛0，1｝），加密過程中隨機生成固定的大質(zhì)數(shù)Q，（且p的位數(shù)要大于Q的位數(shù)）明文m∈｛000，001，010，…，111｝，密文c為：

（3）Decrypt（sk，c）：對密文解密的明文為m=（cmodp）mod23，在加密過程中對x0求模是降低密文大小。

2.2.3 壓縮解密電路實現(xiàn)全同態(tài)加密方案

按照文獻［7］的步驟，利用方案的自舉性壓縮解密電路，即向公鑰中加入一些私鑰信息，通過這部分私鑰信息對密文進行預(yù)處理，保持密文“新鮮”，實現(xiàn)全同態(tài)，預(yù)處理后的大大加快解密速度，并降低了運算復(fù)雜度。

2.3 改進方案安全性分析

該方案的安全性是基于部分近似最大公約數(shù)問題（GCD）這一點與DGHV方案相似。其安全級別達到了IND-CPA安全，在Dijk的文獻［7］中已得到論證，到目前為止最大公約數(shù)問題是不能被解決，所以該方案符合安全性。同時文中的將稀疏子集和問題引入到壓縮解密算法中，更加保證了文中算法的安全性。

2.4 改進方案與DGHV方案的比較

Dijk等人提出的基于整數(shù)上的全同態(tài)加密方案是第一個整數(shù)上的全同態(tài)加密方案，本文改進的具有較小公鑰尺寸的Somewhat同態(tài)加密方案也是基于整數(shù)上的。所以，下面對改進后的方案與DGHV方案從安全性與效率等方面進行比較，衡量安全性的指標主要有：方案安全級別、基于的困難問題假設(shè)等，影響方案效率的指標：公/私鑰的尺寸、加/解密算法復(fù)雜度、算法吞吐量等。如表1所示：

表1 DGHV方案與改進方案的對比

從表1的對比不難發(fā)現(xiàn)，改進后的方案保留了基于整數(shù)的全同態(tài)加密方案基于困難問題方面的優(yōu)勢，安全性上達到IND-CPA。效率方面，較低了公鑰尺寸并增加了單次可加密的數(shù)據(jù)量，降低了加解密復(fù)雜度，加快了加密速度。大大提高了算法處理數(shù)據(jù)的能力。

3 改進方案在云存儲平臺中的應(yīng)用

采用改進后的全同態(tài)加密方案對云存儲環(huán)境中數(shù)據(jù)進行加密后，在保證數(shù)據(jù)在傳輸和存儲過程中的安全性的前提下，可以不用解密就可對密文進行檢索，與傳統(tǒng)加密方法相比，大大縮短了加解密過程，減少了計算的復(fù)雜度，提高了效率。且改進方案具有連續(xù)性好、計算復(fù)雜度低、效率高等特點，提高了云存儲平臺的信息檢索速度。改進方案在云存儲環(huán)境中應(yīng)用如圖1所示。

圖1 全同態(tài)加密在云存儲平臺中的應(yīng)用

用戶通過云服務(wù)器端身份認證后與云存儲平臺建立安全通信信道，保證用戶數(shù)據(jù)傳輸過程安全。云存儲平臺中的客戶端通過將數(shù)據(jù)上傳/下載至HDFS所處的服務(wù)器的本地硬盤的一個臨時空間，而后對數(shù)據(jù)進行加密/解密操作，對加密后的數(shù)據(jù)進行復(fù)制、分塊等操作存放到相應(yīng)數(shù)據(jù)節(jié)點。用戶提出對數(shù)據(jù)進行檢索操作時，由客戶端建立索引，并生成檢索密文關(guān)鍵詞通過MapReduce技術(shù)對密文進行檢索，得出結(jié)果后由數(shù)據(jù)加/解密引擎解密后由客戶端傳至用戶端。

4 結(jié)束語

文中通過研究分析近年來國內(nèi)外全同態(tài)加密技術(shù)的相關(guān)成果，在國內(nèi)現(xiàn)有研究結(jié)果基礎(chǔ)上，提出一種適合于云存儲平臺的全同態(tài)加密算法，但改進后在公鑰尺寸，計算復(fù)雜度等方面相較于傳統(tǒng)加密方案效率上仍有一定差距，所以仍需要在該領(lǐng)域不斷深入研究降低計算復(fù)雜度，提高計算效率，增強安全性。

參考文獻

［1］劉帆，楊明.一種用于云存儲的密文策略屬性基加密方案［J］.計算機應(yīng)用研究，2012，29（4）∶1452-1456.

［2］RIVEST R L，ADLEMAN L，DERTOUZOS M L. On data banks and privacy homomorphisms ［J］. Foundations of Secure Computation，1978，4（11）∶169-180.

［3］Gentry C.Fully homomorphic encryption using ideal lattices［C］// STOC'09，2009∶169-178.

［4］Gentry C.A fully homomorphic encryption scheme ［D/OL］. Stanford University，2009.http∶//crypto.stanford.edu/craig.

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

［6］林如磊，王箭，杜賀.整數(shù)上的全同態(tài)加密方案的改進［J］.計算機應(yīng)用研究，2013，30（5）∶1515-1519.

［7］van Dijk M，Gentry C，Halevi S，et al.Fully homomorphic encryption over the intergers［C］//Proceedings of EUROCRYPT 2010.Riviera，F(xiàn)rench∶ ［s.n.］，2010∶24-43.