基于ElGamal的同態云端密文存儲檢索方案①

邵 航,李子臣,王東飛

(北京印刷學院 信息工程學院,北京 102600)

云存儲和云服務器技術的迅猛發展,將數據搬上云,已是大勢所趨,這樣不僅可以使存儲容量實現動態擴容,方便及時應對如“雙11”購物節等用戶數據激增的情況,還可以降低初創公司前期的投入成本,實現只需按需按量采購云服務器.同時,惠于當前各云廠商推出的個人免費云盤服務,對于普通用戶只需注冊就可以使用,這極大地方便了人們的日常生活.然而,數據存儲在第三方云端,無論是對于企業用戶,還是對于個人用戶,安全問題[1]始終困擾著他們.

與傳統存儲相比,目前的云存儲的數據都被放在云端,由云服務器統一計算管理.但云端存放的數據就可能處在一種不安全的狀態[2],一方面,有的企業會將全部數據上云,而這些數據中可能會有很多的秘密信息,例如一些企業隱私和用戶信息等; 另一方面,用戶不可能會完全信任提供云存儲和云計算的服務商.無論是企業還是個人用戶在使用云存儲時都會擔心數據的安全性,所以對于用戶不信任和數據安全問題急需解決.

為了保證數據安全,我們可以先將數據加密后再上傳到云端,但當存儲的數據越來越多時,對于數據的檢索又成為一大問題.傳統方式是先將數據解密后再檢索,但這樣的檢索效率非常低,無法滿足實際需求.所以我們需要設計出一種無需解密就能檢索的方案,而同態加密可以實現密文間的計算[3,4],所以使用同態加密技術,這樣既能保證數據的安全性也能提升檢索效率.同態加密的概念是由Riverst 等人[5]于1978年首次提出,同年Riverst 等人[6]又提出了基于大整數分解難題的RSA 公鑰加密算法,該算法具有乘法同態性;1999年,Paillier 提出了基于合數階剩余類的Paillier 公鑰密碼算法[7],該算法具有加法同態性和乘法同態性;2009年Gentry 構造出首個全同態加密方案[8],該方案基于理想格,之后Gentry 等人又在2010年和2013年分別提出DGHV 方案[9]和GSW13 方案[10],前者基于近似最大公因子問題(approximate greatest common divisor,AGCD)[11],后者基于LWE (learning with error)問題; 2012年以后,文獻[12,13]中提出BGV12方案和Bra12 方案,前者通過模交換和密鑰交換技術實現無需bootstrapping 就能建立層次型同態加密方案(Leveled-FHE)方案,后者無需使用模交換就可建立Leveled-FHE 方案.但全同態加密算法的效率很低[14],IBM 在其開源庫HElib 中嘗試使用了BGV 方案設計了一個基于全同態加密的密文檢索實驗[15],實驗結果表明,目前將全同態方案直接用于密文檢索會大大限制檢索效率,實用性較弱.此外國內外學者也做出了很多研究,文獻[16]提出一個基于LWE 和AGCD 問題的新型密文同態加密方式,根據逐個計算密文相似度,進而排序選出相似度最大者即為檢索結果,但其中密文排序增加了云端計算量; 文獻[17]利用加法同態性提出一種在密態數據庫上的可搜索加密方案; 文獻[18]以整數向量加密技術為基礎,通過建立向量空間模型,進而在密文下計算檢索向量與文件向量的相似度進行檢索,但在建立空間向量模型和計算相似度時會增加計算量; 文獻[19]給出了一種基于改進的同態加密算法的全文密文檢索方案,但也需要排序、查找后才能達到檢索的目的;文獻[20]提出了一個基于新型同態密文檢索方案CRSHE,但同樣需要通過排序反映文檔與關鍵詞之間的相關性去實現檢索.從上面可以看出同態加密技術在云存儲中實現密文檢索大有可為,但大都需要一些額外的計算,例如排序、查找、計算相似度等,增加系統開銷.

而本文針數據存儲的安全和密文檢索的高效需求,首先設計一個新的密文檢索模型,在此基礎上提出一種混合加密技術,即使用成熟的ElGamal 算法和安全的國密SM4 算法設計了一種高效的云端同態密文檢索方案,并給出了該方案的具體流程.其次,通過理論證明和實驗仿真的方式分析了方案的正確性與安全性.最后,對實驗數據進行分析,實驗數據表明,在保證檢索結果正確的前提下,能有效提高檢索效率.

1 預備知識

1.1 檢索模型

在該方案設計的檢索模型如圖1 所示,主要參與方: 用戶、云服務器、可信第三方.方案的主要功能分為用戶錄入數據(1)和用戶檢索數據(2-7).

圖1 密文檢索系統模型

(1)用戶

用戶首先將加密數據上傳至云服務器,當需要檢索時,上傳檢索密文關鍵詞,下載所需加密文檔,然后解密得到所需文件.

(2)云服務器

云服務器作為存儲和計算數據的平臺,在密文數據中檢索計算,將計算結果發送給可信第三方,解密得到檢索序號,根據檢索序號返回最終的加密文檔給用戶.

(3)可信第三方

可信第三方首先產生同態加密的公私鑰,并公布公鑰; 然后將云服務器發送過來的密文通過私鑰解密,篩選出檢索序號,并發送給云服務器.

1.2 ElGamal 同態加密算法

ElGamal 算法[21]是國際上公認的公鑰密碼體制,其加密算法是基于Diffile-Hellman 密鑰交換算法[22],是由Taher ElGamal 在1985年提出,其安全性基于計算有限域上的離散對數難題,相比于RSA 算法,ElGamal算法能抵抗重放攻擊.該算法由參數設置、密鑰生成、加密、解密和同態乘法5 部分組成:

(1)參數設置

隨機選擇一個大素數p,構造一個模p的有限域Zp,g是Zp上的生成元,且g∈Zp.

(2)密鑰生成

隨機選取X∈[1,p-1],計算Y=gXmodp,私鑰SK={X},公鑰PK={p,g,Y}.

(3)加密

發送者對于明文消息m,隨機生成一個秘密數k∈[1,p-1],使用公鑰對明文消息加密得到密文:E(m)={γ=gkmodp,β=mYkmodp},其中,E(·)表示加密算法.

(4)解密

接收者收到密文消息{c1,c2}后,利用私鑰解密得到明文D(E(m))=β(γX)-1modp,其中,D(·)表示解密算法.

(5)同態乘法

若對于兩個明文消息m1,m2,加密后的密文分別為:E(m1)={γ1=gk1modp,β1=m1Yk1modp}和E(m2)={γ2=gk2modp,β2=m2Yk2modp},則E(m1)E(m2)={γ1γ2,β1β2}={gk1+k2modp,m1m2Yk1+k2modp},且D(E(m1)因此ElGamal 算法具有乘法同態性.

2 方案設計

2.1 整體方案設計

如圖2 所示,是該方案中云端密文檢索系統的整體框架,同態計算和求逆在云服務器中進行實現.

圖2 密文檢索系統整體框架

(1)初始化

可信第三方生成ElGamal 的公私鑰對,并將公鑰公開; 用戶在客戶端生成SM4 算法的密鑰.

(2)錄入數據

用戶使用同態公鑰將關鍵詞加密,使用SM4 密鑰將文件內容加密,然后將加密后的關鍵詞和加密后的文檔一起上傳至云服務器存儲,即錄入數據.

(3)檢索數據

用戶使用同態公鑰加密檢索關鍵詞,再向云服務器提交檢索請求,即檢索數據.

(4)同態計算

云服務器接收到檢索請求后,首先將密文檢索關鍵詞先求逆,然后逐個與密文關鍵詞相乘,最后將結計算結果發送給可信第三方; 可信第三方收到后使用同態私鑰進行解密,返回給云服務器一個結果; 云服務器根據結果,返回給用戶相應的檢索結果.

(5)解密數據

用戶在客戶端收到云服務器發送的加密文件后,用SM4 密鑰解密,得到檢索關鍵詞所對應的明文文件.

2.2 系統具體結構

下面具體介紹整個方案的流程結構,整個方案主要可以分成兩部分,第1 部分是錄入數據,第2 部分是檢索數據,且每個角色都有不同的功能,圖3 是方案檢索成功的詳細序列圖.

圖3 方案序列圖

下面分別詳細介紹這兩部分.

(1)用戶錄入數據

用戶待上傳n個明文文件(1≤i≤n),如表1 所示.

表1 待上傳的明文數據

本方案支持多關鍵詞檢索,設關鍵詞個數為m個(1≤j≤n),但關鍵詞數量增加會增加同態計算的次數,引起時間復雜度的增加,因此在保證檢索的效果和減少時間開銷的前提下,我們應當控制關鍵詞數量,所以在下面的實驗中,我們取m=2.

用戶生成的密鑰有: 用于ElGamal 算法加解密公私鑰對{PK,SK},以及SM4 分組密碼算法的密鑰{K}.

該方案采用的混合加密,關鍵詞用ElGamal 算法加密,文件內容使用國密SM4 算法加密,然后合并一起上傳服務器.每個用戶擁有自己上傳文件的密鑰,可信第三方擁有所有加密關鍵詞的密鑰,具體如表2 所示.

表2 角色和密鑰分配

用戶上傳文件流程如圖4 所示.

圖4 文件上傳

1)可信第三方生成同態加密公私鑰

隨機取一個較大的素數p,構造一個模p的有限域Zp,g是Zp中的生成元,隨機取X∈Zp,計算出Y=gXmodp,得到同態加密的公私鑰對{SK={X},PK={p,g,Y}},且公布公鑰PK.

2)用戶生成對稱加密的密鑰并加密數據

在客戶端取隨機數k∈Zp,使用公鑰PK對關鍵詞Mij加密,計算得{γij=gkmodp,βij=MijYkmodp},生成對應的密文關鍵詞C_Mij.其中文件關鍵詞Mij在加密前需要通過Unicode 編碼為十六進制字符串并轉為整數形式; 在客戶端生成128 位的隨機數作為SM4 密鑰K并保存在本地,并使用密鑰K對文件加密得到密文文件C_Fi.

3)用戶上傳密文數據.

將C_Mij和C_Fi拼接一起發送給云服務器存儲.此時云服務器中的存儲內容如表3 所示.

表3 云端中的密文數據

(2)用戶檢索數據

用戶檢索數據的流程如圖5 所示,該部分包含5 個階段.

圖5 用戶檢索文件

1)加密檢索關鍵詞

假設密文數據庫中的密文文件有n個,用戶先將檢索關鍵詞Q通過Unicode 編碼為十六進制字符串,并轉為整數形式得到Q*,這時使用之前生成的公鑰PK 對Q*進行同態加密,計算得到{γQ=gkmodp,βQ=(Q*)Ykmodp},即生成檢索關鍵詞的密文C_Q*={γQ,βQ}.

2)同態計算

云服務器收到密文檢索關鍵詞C_Q*后,求逆得到(C_Q*)-1,然后逐個與密文關鍵詞C_Mij={γij,βij}做同態乘法得到具體運算如式(1):

3)可信第三方解密

4)云服務器返回檢索結果

云服務器根據收到可信第三方返回的解密結果來判斷是否將密文文件發送給用戶: 若返回的是一個非0 的結果s(1 ≤s≤n),則返回序號為s所對應的密文文件C_Fs; 若返回值為0,則表示未檢索到結果,向用戶發送“查詢失敗”的信息.

5)用戶解密

用戶從云服務器下載到密文文件C_Fs(1 ≤s≤n),利用SM4 的密鑰K對文件解密,得到最終檢索關鍵詞所對應的原文件Fs.

3 系統實現與安全性分析

3.1 具體實現

本節通過一個具體的案例來驗證本方案,加密原文件可以是圖書內容,圖書數量n=4,關鍵詞個數m=2,關鍵詞M1 和M2 分別是書名和作者,實驗環境為Intel(R)Core i5-6200U @ 2.30 GHz 雙核16 GB 內存,Microsoft Visual Studio Community 2019.

(1)假設用戶有待加密上傳的文件如表4,以明文形式展示.

表4 明文數據

上面的明文數據使用混合加密,即關鍵詞{書名、作者}使用ElGamal 算法加密,文件內容使用SM4 算法加密.

(2)將關鍵詞用Unicode 編碼為十六進制字符串,并轉為整數形式,見表5.

表5 關鍵詞

將關鍵詞(整數形式)使用ElGamal 加密,參數設置:(p,g)(40049372667947663039,11743527543478996065),(X,Y)=(14450894889756208713,255895591548258 90551)將文件內容使用SM4 加密,然后上傳云服務器,密文數據庫如表6.

表6 密文數據

(3)若用戶輸入檢索關鍵詞Q=“史記”,先用Unicode 編碼為十六進制字符串,并轉為整數形式Q*,然后使用ElGamal 加密(Q*)-1得到檢索關鍵詞的逆元密文C_Q*={γQ,δQ},結果如表7 所示.

表7 檢索關鍵詞

(4)云服務器收到檢索關鍵詞的密文C_Q*后,將密文檢索關鍵詞求逆得(C_Q*)-1= {37747856122936643469,13243315324064048566},然后逐個與密文數據庫中的密文關鍵詞C_Mij做乘法得到(C_Q)*ij(i,j∈Z,1 ≤i≤4且1 ≤j≤2),如表8所示.

表8 同態乘法運算密文相乘結果

表8 同態乘法運算密文相乘結果

序號關鍵詞1關鍵詞2 1{1 23 1216929236222963946,128607310697629708}{33593146621890140288,37977864468152489955}2{18283956446679924477,24618066340401802334}{1366231225410332531,29051288589689848885}3{33896692461687507920,4109244469603721049}{34946155032641737178,22886193455501072227}4{10896494947855593771,3808468191905602827}{25731605953598699893,1282281649647820192}

云服務器將計算的結果發送給可信第三方,可信第三方收到消息后,使用私鑰SK逐個解密得到Q*ij(i,j∈Z,1 ≤i≤4且1 ≤j≤2),如表9.這里的Q*21=1,所以將s=2 返回給服務器.

表9 第三方解密結果(C_Q)*ij的解密結果

(5)云服務器收到可信第三方發來的s=2,將E(F2)發送給用戶,即用戶從云服務器下載到E(F2),最后使用SM4 密鑰解密得到原文件F2.

3.2 安全性分析

在該方案中,用戶首先要將加密后的文件和關鍵詞上傳至云端,然后從云端檢索出關鍵詞對應的加密文件,解密即可得到檢索的文件,所以本方案的安全性可分為數據存儲安全性和檢索模型安全性.

(1)數據存儲安全性

關鍵詞是采用ElGamal 算法加密的,相比于RSA算法,ElGamal 算法能抵抗重放攻擊,另外根據計算有限域上的離散對數困難,攻擊者很難根據公鑰PK去計算或推導出私鑰SK,這就使得用戶在密文檢索過程中,攻擊者就算得到公鑰PK,也不能作為云服務器和可信第三方之間的中間者去解密云服務器發送的同態計算結果,這就保證了用戶在檢索過程中檢索數據不可篡改.

再者就是文件采用的是國密SM4 分組算法.加解密過程均由用戶在客戶端完成,云服務器無法獲知其密鑰K.SM4 保證了文件的安全性[23],可以抵抗窮舉攻擊、差分攻擊、線性攻擊等攻擊手段,具有較高的安全性,使得攻擊者即使獲得加密文件,也無法作為用戶和云服務器之間的中間者解密出原文件.

(2)檢索模型安全性

密文檢索過程滿足乘法同態性.方案中同態加密的公私鑰均由可信第三方生成,用戶將關鍵詞和文件加密上傳至云端,都是以密文形式存儲.用戶將加密的檢索關鍵詞上傳至云端,利用同態加密的性質,將加密的檢索關鍵詞與云端中存儲的密文關鍵詞做乘法同態運算,再利用可信第三方解密來求出檢索號,以此完成密文檢索.由于整個過程均是在密文下進行的,所以說云端是無法獲知任何有關密鑰和明文數據的,且只有用戶才能獲得明文數據,這就保證了檢索過程中的數據是安全的,所以說檢索模型是安全的.

3.3 性能分析

(1)效率分析

在本方案中的密文檢索只使用了乘法同態,也就是只用部分同態來實現,當然也可以使用全同態來實現密文檢索,但目前全同態效率比較低,難以廣泛使用.以下面的例子為例,來證明本文使用部分同態比全同態效率更高.如表10,加密1 000 數字1 000 次,取10 次試驗的平均時間; 將1 000 和2 000 的密文相乘,取10 次試驗的平均耗時,明顯可以看出使用ElGamal在加密和乘法同態運算上速度更快.另外表11 展示與其他方案的對比,可以看出本方案更加輕量高效 這里BGV 算法和CKKS 算法的測試程序采用的是IBM 的開源庫fhe-toolkit-linux[15]; BFV 算法的測試程序采用的是微軟的開源庫SEAL[24].

表10 測試時間(ms)

表11 方案對比

(2)精確度分析

本方案針對個人用戶就是在云端構建單用戶的密文數據,進而在云端進行安全檢索,因為一個文件可以有多個關鍵詞,所以用戶在檢索時,既可以實現單個關鍵詞檢索,也可以實現多關鍵詞檢索.

單個關鍵詞檢索時,檢索結果只有兩種: 找到文件或者是未檢索到; 多關鍵詞檢索時,若輸入的是一個文件對應的多個關鍵詞,那么只要有一個匹配上,則檢索成功,若輸入的是多個文件對用的關鍵詞,則返回多個匹配上的文件,進而實現多文件檢索,這樣效率會更加高,其精確度和效率遠高于逐個關鍵詞檢索.

4 總結與展望

本文利用同態加密的性質,設計出新的密文檢索模型,再結合安全的國密算法,提出了一個基于同態加密的云端密文存儲檢索方案.該方案能夠在保證數據安全的前提下進行數據檢索,即檢索過程中云端無法獲知任何有關密鑰信息和明文數據.與其他方案相比,具有輕量級和高效性,可以應用于小型個人云端U 盤的場景,有較好的實用價值.經實驗數據分析表明,本文方案檢索結果正確、安全性好、效率高、實用性強.在下一步的研究中,將嘗試設計一種高效的全同態加密算法,并將其應用在云端密文檢索中,使之具有更好的安全性.