同態加密技術在大數據安全中的應用研究

秦宏春

(中國人民解放軍 758471部隊,湖南 長沙 410007)

0 引言

由于近幾年物聯網傳感技術與移動互聯網的快速發展以及在全世界的迅速普及,導致大量的數據信息被記錄并上載到網絡。這些數據信息擁有規模巨大、結構復雜、價值密度低等特點。因此,如何從這些關聯性弱、碎片化的大數據集合中獲取具有商業價值的信息,是目前行業研究的熱點。但在大數據挖掘帶來各種社會便利的同時,也不可避免地存在大數據泄露個人隱私等安全問題。與傳統的數據隱私保護不同,大數據除了要防止存儲階段的泄露,還要防止計算階段的隱私泄露問題。如何兼顧保證大數據可以被保密存儲并被安全利用的同時不被惡意第三方獲取,是大數據隱私保護要面對的核心問題。

1 大數據不同階段下的安全問題

信息化時代,傳統的數據面臨著諸多的安全問題,如計算機系統自身的局限性與外部的惡意攻擊。而新型大數據與傳統數據的全流程都不盡相同,因此需要考慮的安全問題也有一定的差異。在分析大數據安全問題時,需要根據大數據的生命周期來分類。

在大數據的整個生命周期內,主要在于存儲、搜索和計算3個階段可能面臨隱私泄露的問題。這是因為大數據集擁有數據規模大的特點,一般的數據擁有者很難與傳統模式一樣將大數據存儲在本地,而不得不存儲在云服務器上。同樣由于數據的總量龐大,導致個人沒有足夠的算力完成大數據檢索或計算,因此往往需要將數據外包給第三方處理。但在實際環境中,無論是云服務存儲者還是第三方數據處理者都不是完全可信的,數據擁有者既要保證數據以密文存儲從而防止信息泄露,又要使得處理者可以順利計算。

1.1 大數據存儲階段

由于大數據擁有者往往將大數據存儲在云端,因此為了防止數據泄露,用戶需要對數據進行加密處理。而大數據量龐大且近指數級增長,所以如果選擇的加密算法效率低下,不但會消耗大量的加密時間,還會導致數據密文嚴重膨脹,占據過量云存儲空間[1]。同時,大數據結構復雜,穩健性較低的加密方案極易導致數據錯位和存儲混亂,不利于數據的后期處理與管理。

1.2 大數據搜索階段

大數據搜索主要是針對密文存儲形式的大數據完成基于關鍵詞、短語或正則表達式的查詢和檢索操作。因此,該階段的處理方式需要加密方案有良好的功能性,即加密后的密文有一定的抗碰撞性。尤其是在面對海量的數據集時,這樣的抗碰撞性既要使得密文可搜索又要擁有選擇明文攻擊下的不可區分性[2]。

1.3 大數據計算階段

用戶將大數據計算外包給第三方計算服務者時,往往希望第三方能在不破壞加密性的前提下完成相關計算。而大數據計算不但有著計算量龐大還有著計算方式復雜多樣等特點。該階段必須選擇一個具有密文可計算功能的隱私保護方案,并在計算的復雜度和計算方式上更為全面[3]。綜上所述,相比于傳統的數據模式,大數據各階段需要面對更多種的數據處理方式,這些處理方式與安全問題緊密相關,如果選擇的加密方案不當,會導致處理效率低下且容易導致數據受損甚至泄露。因此,本文接下來將分析基于同態加密的解決方案。

2 同態加密解決方案

加密是保護任何敏感信息隱私的關鍵機制,然而,傳統的加密方案在沒有解密的情況下不能對加密數據進行操作。換句話說,用戶不得不犧牲他們的隱私來使用云服務,如文件存儲、共享和協作。此外,不受信任的服務器、提供商和云運營商可以在用戶結束與服務器的連接后,很長時間內保持對用戶元素的物理識別。而同態加密這種特殊的加密方案可以解決一系列的問題,因為它的原理特性允許第三方對加密數據進行操作,而無須事先解密。假設明文為M={T1,T2…Tn};密文為C={c1,c2…cn};加密函數為E;解密函數為D;評估函數為f,則在同態加密中以下式子一定為真:E(f(T1,T2····Tn))=f(E(T1),E(T2)····E(Tn))。即經過同態加密之后,如果對密文進行操作,解密之后的明文也會有對應的效果。這樣的特性使得用戶可以安全地將數據交于第三方處理,在轉移了計算成本的同時又保護了個人的隱私,如圖1所示。

圖1 同態加密

同態加密根據同態性的程度可以分為3類,分別是部分同態加密、某種同態加密和完全同態加密。下面將介紹3類同態加密下的具體加密算法原理以及其算法性能。

2.1 部分同態加密

部分同態加密算法只允許一種類型的操作,比如加法或者乘法,但是使用的次數不受限制。由于同態操作的類型限制,只能作用于特定的應用,如電子投票和信息檢索。

2.1.1 RSA算法

RSA算法實現了乘法同態[4]。RSA的安全性基于兩個大素數乘積的因式分解問題的困難性。目前已經分解的最大整數232位十進制,768位二進制。而整數分解問題主要的破解方法是暴力破解,即窮舉素數相乘的結果。RSA作為較為早期的加密算法之一,應用廣泛,但是缺點在于密鑰尺寸大、加密解密速度慢。在計算機運算能力越來越強的今天,RSA變得非常不安全。

2.1.2 GM加密系統

GM加密系統實現了加法同態,其安全性主要是基于二次剩余難以復合困難性問題。但它不是一種有效的密碼系統,因為它的密文膨脹系數過大,可能會導致密文比原始明文大數百倍。

2.1.3 El-Gamal加密系統

El-Gamal加密系統實現了乘法同態,是一種基于Diffie-Hellman密鑰交換的用于公鑰密碼學的非對稱密鑰加密算法。該算法的缺點在于密文的一般擴展大小為1∶2,對于空間敏感型的系統不太友好。

2.1.4 Paillier

Paillier滿足同態加以外還滿足以下操作[5]:(E(m1)m2modn2)=m1m2modn,D(E(m1)E(m2)modn2)=(m1+m2)modn。Paillier加密基于一種新的基于復合剩余問題的概率加密方案,區別于其他的同態加密算法,其獨有的附加同態屬性描述了加密數據和明文上的各種操作之間的不同交叉關系,也給予了使用者更多的可能。

2.1.5 GM 加密系統的衍生

加密數據的任何乘法運算都對應于明文上的加法運算,即加法同態。是對GM加密系統的改進,同樣也是基于高剩余性問題。具體細節差異在于加密的信息不再是一個比特一個比特而是以塊為單位加密,以此提高了加密性能。

2.1.6 Okamoto-Uchiyama

該團隊提出了一種新的部分同態加密算法,主要思路是通過改變以前HE方案的集合而改進計算性能。還有其他大量的工作是對經典同態加密算法的改進,旨在提高計算效率、時間空間開銷。

部分同態加密是最早也是較為成熟的加密技術。上述所列舉的算法中,RSA與Paillier的運用最為廣泛。雖然大部分的同態加密只能實現加法或者乘法同態性,但是在性質與性能中達到了較好的平衡。

2.2 某種同態加密

某種同態加密允許有限次數的某些類型的操作,屬于不完全的同態方案,密文的大小隨著每個同態操作而增長,因此允許的同態操作的最大數量是有限的。

(1)BGN是一種同態加密方案[6],是Boneh等在2005提出的一種具有全同態性質的加密方案。和傳統的僅能支持單同態的El-gamal和Paillier加密方案不一樣,BGN能夠同時支持任意次數的加同態單,但只支持一次乘同態運算。由于乘法同態的實現是通過雙線性對性質實現的,所以只能實現一次的乘同態。

(2)其他方案:除去BGN還有多種其他類似的方案,但是大多效果不完全。比如Polly Cracke允許密文進行乘法和加法運算。但是運算的密文大小隨著同態運算呈指數增長,乘法運算的開銷極其昂貴。后續還有變種的算法提出,但是這些方案要么不安全要么不切實際。比如Albrecht介紹了一個帶有噪聲的波利破解密碼系統,其中同態加法運算不增加密文大小而乘法使得密文大小平方倍增長。

總的來說,某種同態加密是人們在研究完全同態加密過程中的產物。雖然能實現不改變密文大小且次數不限的同態加法,但是乘法往往會受到嚴格的限制,無論是次數還是密文存儲都是不理想的。在實際應用中一般不會采用某種同態加密,為了殘缺的乘法同態舍棄性能是得不償失的。

2.3 完全同態加密

在引入隱私同態概念近30年后,Gentry等[7]終于提出第一個完全同態加密方案。盡管這個方案只是理論性的,而且是不可實現的。但是在后續許多學者在這個理論基礎之上利用許多密碼假設進行了實例化,設計了越來越多更簡單且更有效的加密方案。目前主要有3個完全同態加密方案,分別是基于理想格、基于整數以及基于誤差學習。

2.3.1 基于理想格的同態加密

2011年,Gentry等[8]在他人的工作基礎之上通過優化密鑰生成和應用批處理技術,終于實現了Gentry初始方案的變體形式G09,這也是完全同態加密的第一次實現。然而,如同原始方案中的缺點一樣,其計算開銷極其龐大。公鑰大小為2.3 GB,生成密鑰需要2.2 h,加密一條消息需要3 min,而刷新密文需要30 min。它依賴于多種新型且未經測試的復雜性假設。

2.3.2 基于整數的同態加密

Dijk等[9]沒有選擇理想格,而是使用了基于整數構建了同態加密。該方案主要優點在于概念簡單,然而該方法依舊不實用,因為產生的公鑰龐大且加密效率低下。即使在后人優化之后,也還會生成大小為802 MB的公鑰,生成密鑰需要43 min,加密消息需要2 min7 s,刷新密文需要3 min 55 s。

2.3.3 基于誤差學習的同態加密

為了將FHE方案建立在經過充分研究的數學問題的基礎上,Brakerski 以及Vaikuntanathanz證明了第一個偏離Gentry計劃的FHE方案[10]。這種新型的FHE方案基于標準的LWE假設,通過引入一種叫做重新線性化的技術,避免了理想格上未經測試的假設。此外,應用了一種叫做降維模數的技術來避免Gentry方案中不可或缺的擠壓過程,從而阻止了涉及SSSA問題。但是這種方案依舊不是完美的,必須依賴于開銷巨大的自舉,從而開銷巨大。

綜上所述,Paillier方案是在加密效率、密文膨脹度以及安全性等指標中綜合性能最優并且運用范圍最廣的。盡管Paillier方案只能實現加法同態性,但該方案依舊是大數據計算階段隱私安全保護最有效的措施之一。

3 結語

同態加密方案的明密文計算同態特質可以有效解決大數據計算中隱私保護的問題,但是目前廣泛運用的同態加密往往是部分同態加密,只能完成加法或者乘法同態。針對大數據的計算方式復雜等特性,全同態加密則是最能平衡安全性和可計算性的方案。現有全同態加密技術的運行效率、密文膨脹程度和安全性仍沒有達到實際可運用的程度。因此,設計高效率和低成本的完全同態加密算法,并運用在大數據安全之中,是一個重要的研究方向。