秦宏春

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

0 引言

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

1 大數(shù)據(jù)不同階段下的安全問題

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

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

1.1 大數(shù)據(jù)存儲階段

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

1.2 大數(shù)據(jù)搜索階段

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

1.3 大數(shù)據(jù)計算階段

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

2 同態(tài)加密解決方案

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

圖1 同態(tài)加密

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

2.1 部分同態(tài)加密

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

2.1.1 RSA算法

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

2.1.2 GM加密系統(tǒng)

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

2.1.3 El-Gamal加密系統(tǒng)

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

2.1.4 Paillier

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

2.1.5 GM 加密系統(tǒng)的衍生

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

2.1.6 Okamoto-Uchiyama

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

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

2.2 某種同態(tài)加密

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

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

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

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

2.3 完全同態(tài)加密

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

2.3.1 基于理想格的同態(tài)加密

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

2.3.2 基于整數(shù)的同態(tài)加密

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

2.3.3 基于誤差學(xué)習(xí)的同態(tài)加密

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

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

3 結(jié)語

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