一種適用于云存儲的改進全同態加密方案
2016-06-21 07:02:23武警工程大學研究生管理大隊胡人遠
電子世界 2016年11期
武警工程大學研究生管理大隊 胡人遠
一種適用于云存儲的改進全同態加密方案
武警工程大學研究生管理大隊 胡人遠
【摘要】全同態加密思想在云存儲、密文檢索等多方面有重要應用，為了得到更適合云存儲的全同態加密方案，對現有的全同態加密方案研究現狀進行了分析對比，提出一種基于DGHV方案的改進全同態加密方案。在保證方案安全性的前提下，將單次加密數據量提高到3bit。經論證，改進后單次加密數據量提高的同時，公鑰尺寸大大縮小，且降低了計算復雜度，適用于云存儲平臺。
【關鍵詞】全同態加密；云存儲；密文檢索
隨著云計算技術的不斷推廣，信息數據的存儲與管理成為云計算領域的最熱門話題之一。云存儲技術作為解決信息數據存儲和管理的有效途徑之一，由并行存儲、分布式存儲和網格存儲發展而來，但畢竟作為一個新興技術，各方面仍不是很成熟，尤其是安全方面。使用云計算的外包存儲服務［1］就不可避免的要將用戶數據上傳至云端，用戶在失去數據絕對擁有權和控制權的情況下，如何保護用戶的數據安全，這將是云存儲面臨的最大實際問題。在此基礎上，在云存儲平臺實現密文計算，密文檢索等功能，這需要繼續探索改進數據加密技術。
上世紀70年代， Rivest等人［2］提出了FHE問題，希望通過全同態的性質可以在不解密密文的情況下，對密文進行加減乘除運算，且運算后的結果解密后與對應明文運算后的結果保持一致。隨后，國內外學者對同態加密進行了大量的研究，但產生的許多同態加密方案并沒有達到全同態加密的要求。直至2009年，IBM研究員Gentry在該領域取得了重大突破，提出基于理想格的全同態加密方案［3］，并其博士論文［4］中對全同態加密進行了更深入的論述。這兩篇文章給全同態加密研究領域點亮了前進的方向。為實現密文檢索又提供了一種可行性技術。
目前，國內關于整數上的全同態加密技術的研究成果大多停留在基于現有方案基礎提出的改進方案的水平。如湯殿華等人［5］在文獻［3］的基礎上進行改進，與文獻［3］相比，具有較小的公鑰尺寸、計算效率更高的特點，但是在安全性上存在缺陷。林如磊等人［6］提出一次加密2bit明文，將模2運算改為模4運算，在效率方面進一步提高，并對方案安全性進行分析。全同態加密技術研究還有一個方向是基于LWE困難問題的，但能否運用到云存儲上仍需進一步研究分析。
本文主要研究分析云存儲的性質特點，結合國內相關的改進思路，對文獻［7］中的整數上的全同態加密方案進行了改進，將單次加密數據量由1bit改進為3bit，并使用Gen-try的全同態加密思想，構造全同態加密方案，并采用文獻［7］中的技術使公鑰尺寸大大縮小，使方案具有更高的效率。
1 理論基礎
1.1 同態加密原理
同態是近世代數理論中的一個基礎概念。
假設加密函數為EK解密函數為DK運算操作為a和明文M（m0，m1，…，mi），公式為a（DK（M（m0，m1，…，mi）））= D（a（M（m0，m1，…，mi）））
FHE加密方案包含有以下四種算法：
密鑰部分（Key） ： 根據給出的參數γ， 生成私鑰sk和公鑰pk；
加密部分（Enc） ： 明文m通過公鑰pk加密后獲得密文c；
解密部分（Dec）： 明文m由私鑰解密密文c后得到
密文運算算法（Evaluate） ： 輸出t個輸入的電路C和公鑰pk，還有明文對應的密文c。用公式可以表示輸出為Evaluate（pk，C，c）。
1.2 DGHV全同態加密
DGHV的具體方案［7］為：
（1）構造一個somewhat加密方案。
生成密鑰：選取p作為密鑰，其中p滿足的條件為：p是一個大素數且p∈［2η-1，2η）；
加密部分：1bit的明文m∈｛0，1｝，m加密生成的密文c=m+pq+2r，在加密過程中隨機生成q和r，其中q是一個遠大于p的較大整數，r是一個較小的整數且2r小于p/2；
解密部分：解密過程為明文m =（cmodp）mod2。
（2）將somewhat方案構造成非對稱公鑰方案。
由于q是公開的，那么如果直接將pq作為公鑰，則私鑰p很容易被計算出來，所以假設一個集合｛xi，xi=pqi+2ri｝ ，選擇集合中的任意項構成子集S，將子集中元素的和作為公鑰sum（s）=，式子可表示為： c=m+2r+sum（s）。那么具有隨機性質的公鑰，則可以有效保證密文不被破解出來
（3）使用壓縮解密技術對密文不斷刷新，控制噪聲的增量。
由解密算法可以發現，當密文cmodp （p/2，p/2）之間時，則能解密得出明文。如果超出這個范圍則無法還原明文。每次運算前，對“新鮮”密文，進行一次“加密”，從而使要進行運算操作的密文噪聲大小控制在一定范圍之內，從而達到消減噪聲的目的。從而保證運算后的新密文能夠被成功解密。
2 改進的基于整數的全同態加密方案
2.1 改進方案原理
通過對文獻［7］的研究與分析，提出一種能一次加密3bit密文的基于整數的全同態加密方案，其單次加密數據量更大，公鑰更小。
首先對文中使用的符號進行說明：
λ：安全參數；
ρ：噪聲的長度，為抵抗暴力攻擊，噪聲長度應該取ρ=ω（logλ）；
η： 私鑰的二進制長度，私鑰長度滿足η≥ρΘ（λlog2λ）；
γ：公鑰的二進制長度，私鑰長度滿足γ=ω（η2logλ）；
τ： 公鑰的個數，τ≥γ+ω（logλ），文中需要的公鑰個數為2。
其中ω（）是高階無窮大量。
2.2 構造全同態加密方案
2.2.1 構造部分同態的somewhat方案
將模2運算改為模23運算，單次可加密3bit明文信息
（1）KeyGen（λ）：由安全參數λ生成η比特的密鑰p，令密鑰sk=p。
（2）Encrypt（sk，m）：對m∈｛000，001，010，…，111｝進行加密得c=m+23r+pq，其中，r是ρ比特大小的隨機整數，q是加密過程中生成γ比特大小的隨機整數。
（3）Decrypt（sk，c）：m=（cmodp）mod23。
cmodp的值為噪聲大小，只有當|m+23r|＜p/2時，那么噪聲cmodp=m+23r，則才能還原出有效的明文。下面對方案的同態性進行驗證：
驗證得，構造的對稱加密方案既滿足加法同態又滿足乘法同態。但是方案中的噪聲會隨著運算次數的增加而不斷“膨脹”。但噪聲值大于p/2時，則以上等式不成立，即無法解密出有效明文。同時有上述公式可見，在加法同態運算中噪聲不斷線性增長的，而在乘法同態運算中呈幾何增長。
2.2.2 轉化為公鑰加密體制
需要添加一組“0”的密文作為公鑰，具體方法步驟如下：
（1）KeyGen（λ）：在加密過程中隨機生成η比特的私鑰p，令x0=pq0，且x0是奇數并符合rp（x0）被23整除。且b=｛0，1｝，1≤i≤，
（2）Encrypt（pk，m）：τ維向量b=
（3）Decrypt（sk，c）：對密文解密的明文為m=（cmodp）mod23，在加密過程中對x0求模是降低密文大小。
2.2.3 壓縮解密電路實現全同態加密方案
按照文獻［7］的步驟，利用方案的自舉性壓縮解密電路，即向公鑰中加入一些私鑰信息，通過這部分私鑰信息對密文進行預處理，保持密文“新鮮”，實現全同態，預處理后的大大加快解密速度，并降低了運算復雜度。
2.3 改進方案安全性分析
該方案的安全性是基于部分近似最大公約數問題（GCD）這一點與DGHV方案相似。其安全級別達到了IND-CPA安全，在Dijk的文獻［7］中已得到論證，到目前為止最大公約數問題是不能被解決，所以該方案符合安全性。同時文中的將稀疏子集和問題引入到壓縮解密算法中，更加保證了文中算法的安全性。
2.4 改進方案與DGHV方案的比較
Dijk等人提出的基于整數上的全同態加密方案是第一個整數上的全同態加密方案，本文改進的具有較小公鑰尺寸的Somewhat同態加密方案也是基于整數上的。所以，下面對改進后的方案與DGHV方案從安全性與效率等方面進行比較，衡量安全性的指標主要有：方案安全級別、基于的困難問題假設等，影響方案效率的指標：公/私鑰的尺寸、加/解密算法復雜度、算法吞吐量等。如表1所示：
表1 DGHV方案與改進方案的對比
從表1的對比不難發現，改進后的方案保留了基于整數的全同態加密方案基于困難問題方面的優勢，安全性上達到IND-CPA。效率方面，較低了公鑰尺寸并增加了單次可加密的數據量，降低了加解密復雜度，加快了加密速度。大大提高了算法處理數據的能力。
3 改進方案在云存儲平臺中的應用
采用改進后的全同態加密方案對云存儲環境中數據進行加密后，在保證數據在傳輸和存儲過程中的安全性的前提下，可以不用解密就可對密文進行檢索，與傳統加密方法相比，大大縮短了加解密過程，減少了計算的復雜度，提高了效率。且改進方案具有連續性好、計算復雜度低、效率高等特點，提高了云存儲平臺的信息檢索速度。改進方案在云存儲環境中應用如圖1所示。
圖1 全同態加密在云存儲平臺中的應用
用戶通過云服務器端身份認證后與云存儲平臺建立安全通信信道，保證用戶數據傳輸過程安全。云存儲平臺中的客戶端通過將數據上傳/下載至HDFS所處的服務器的本地硬盤的一個臨時空間，而后對數據進行加密/解密操作，對加密后的數據進行復制、分塊等操作存放到相應數據節點。用戶提出對數據進行檢索操作時，由客戶端建立索引，并生成檢索密文關鍵詞通過MapReduce技術對密文進行檢索，得出結果后由數據加/解密引擎解密后由客戶端傳至用戶端。
4 結束語
文中通過研究分析近年來國內外全同態加密技術的相關成果，在國內現有研究結果基礎上，提出一種適合于云存儲平臺的全同態加密算法，但改進后在公鑰尺寸，計算復雜度等方面相較于傳統加密方案效率上仍有一定差距，所以仍需要在該領域不斷深入研究降低計算復雜度，提高計算效率，增強安全性。
參考文獻
［1］劉帆，楊明.一種用于云存儲的密文策略屬性基加密方案［J］.計算機應用研究，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］湯殿華，祝世雄，曹云飛.一個較快速的整數上的全同態加密方案［J］.計算機工程與應用，2012，48（28）∶7-122.
［6］林如磊，王箭，杜賀.整數上的全同態加密方案的改進［J］.計算機應用研究，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，French∶ ［s.n.］，2010∶24-43.
