邵 航,李子臣,王東飛
(北京印刷學(xué)院 信息工程學(xué)院,北京 102600)
云存儲(chǔ)和云服務(wù)器技術(shù)的迅猛發(fā)展,將數(shù)據(jù)搬上云,已是大勢(shì)所趨,這樣不僅可以使存儲(chǔ)容量實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容,方便及時(shí)應(yīng)對(duì)如“雙11”購物節(jié)等用戶數(shù)據(jù)激增的情況,還可以降低初創(chuàng)公司前期的投入成本,實(shí)現(xiàn)只需按需按量采購云服務(wù)器.同時(shí),惠于當(dāng)前各云廠商推出的個(gè)人免費(fèi)云盤服務(wù),對(duì)于普通用戶只需注冊(cè)就可以使用,這極大地方便了人們的日常生活.然而,數(shù)據(jù)存儲(chǔ)在第三方云端,無論是對(duì)于企業(yè)用戶,還是對(duì)于個(gè)人用戶,安全問題[1]始終困擾著他們.
與傳統(tǒng)存儲(chǔ)相比,目前的云存儲(chǔ)的數(shù)據(jù)都被放在云端,由云服務(wù)器統(tǒng)一計(jì)算管理.但云端存放的數(shù)據(jù)就可能處在一種不安全的狀態(tài)[2],一方面,有的企業(yè)會(huì)將全部數(shù)據(jù)上云,而這些數(shù)據(jù)中可能會(huì)有很多的秘密信息,例如一些企業(yè)隱私和用戶信息等; 另一方面,用戶不可能會(huì)完全信任提供云存儲(chǔ)和云計(jì)算的服務(wù)商.無論是企業(yè)還是個(gè)人用戶在使用云存儲(chǔ)時(shí)都會(huì)擔(dān)心數(shù)據(jù)的安全性,所以對(duì)于用戶不信任和數(shù)據(jù)安全問題急需解決.
為了保證數(shù)據(jù)安全,我們可以先將數(shù)據(jù)加密后再上傳到云端,但當(dāng)存儲(chǔ)的數(shù)據(jù)越來越多時(shí),對(duì)于數(shù)據(jù)的檢索又成為一大問題.傳統(tǒng)方式是先將數(shù)據(jù)解密后再檢索,但這樣的檢索效率非常低,無法滿足實(shí)際需求.所以我們需要設(shè)計(jì)出一種無需解密就能檢索的方案,而同態(tài)加密可以實(shí)現(xiàn)密文間的計(jì)算[3,4],所以使用同態(tài)加密技術(shù),這樣既能保證數(shù)據(jù)的安全性也能提升檢索效率.同態(tài)加密的概念是由Riverst 等人[5]于1978年首次提出,同年Riverst 等人[6]又提出了基于大整數(shù)分解難題的RSA 公鑰加密算法,該算法具有乘法同態(tài)性;1999年,Paillier 提出了基于合數(shù)階剩余類的Paillier 公鑰密碼算法[7],該算法具有加法同態(tài)性和乘法同態(tài)性;2009年Gentry 構(gòu)造出首個(gè)全同態(tài)加密方案[8],該方案基于理想格,之后Gentry 等人又在2010年和2013年分別提出DGHV 方案[9]和GSW13 方案[10],前者基于近似最大公因子問題(approximate greatest common divisor,AGCD)[11],后者基于LWE (learning with error)問題; 2012年以后,文獻(xiàn)[12,13]中提出BGV12方案和Bra12 方案,前者通過模交換和密鑰交換技術(shù)實(shí)現(xiàn)無需bootstrapping 就能建立層次型同態(tài)加密方案(Leveled-FHE)方案,后者無需使用模交換就可建立Leveled-FHE 方案.但全同態(tài)加密算法的效率很低[14],IBM 在其開源庫HElib 中嘗試使用了BGV 方案設(shè)計(jì)了一個(gè)基于全同態(tài)加密的密文檢索實(shí)驗(yàn)[15],實(shí)驗(yàn)結(jié)果表明,目前將全同態(tài)方案直接用于密文檢索會(huì)大大限制檢索效率,實(shí)用性較弱.此外國內(nèi)外學(xué)者也做出了很多研究,文獻(xiàn)[16]提出一個(gè)基于LWE 和AGCD 問題的新型密文同態(tài)加密方式,根據(jù)逐個(gè)計(jì)算密文相似度,進(jìn)而排序選出相似度最大者即為檢索結(jié)果,但其中密文排序增加了云端計(jì)算量; 文獻(xiàn)[17]利用加法同態(tài)性提出一種在密態(tài)數(shù)據(jù)庫上的可搜索加密方案; 文獻(xiàn)[18]以整數(shù)向量加密技術(shù)為基礎(chǔ),通過建立向量空間模型,進(jìn)而在密文下計(jì)算檢索向量與文件向量的相似度進(jìn)行檢索,但在建立空間向量模型和計(jì)算相似度時(shí)會(huì)增加計(jì)算量; 文獻(xiàn)[19]給出了一種基于改進(jìn)的同態(tài)加密算法的全文密文檢索方案,但也需要排序、查找后才能達(dá)到檢索的目的;文獻(xiàn)[20]提出了一個(gè)基于新型同態(tài)密文檢索方案CRSHE,但同樣需要通過排序反映文檔與關(guān)鍵詞之間的相關(guān)性去實(shí)現(xiàn)檢索.從上面可以看出同態(tài)加密技術(shù)在云存儲(chǔ)中實(shí)現(xiàn)密文檢索大有可為,但大都需要一些額外的計(jì)算,例如排序、查找、計(jì)算相似度等,增加系統(tǒng)開銷.
而本文針數(shù)據(jù)存儲(chǔ)的安全和密文檢索的高效需求,首先設(shè)計(jì)一個(gè)新的密文檢索模型,在此基礎(chǔ)上提出一種混合加密技術(shù),即使用成熟的ElGamal 算法和安全的國密SM4 算法設(shè)計(jì)了一種高效的云端同態(tài)密文檢索方案,并給出了該方案的具體流程.其次,通過理論證明和實(shí)驗(yàn)仿真的方式分析了方案的正確性與安全性.最后,對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析,實(shí)驗(yàn)數(shù)據(jù)表明,在保證檢索結(jié)果正確的前提下,能有效提高檢索效率.
在該方案設(shè)計(jì)的檢索模型如圖1 所示,主要參與方: 用戶、云服務(wù)器、可信第三方.方案的主要功能分為用戶錄入數(shù)據(jù)(1)和用戶檢索數(shù)據(jù)(2-7).
圖1 密文檢索系統(tǒng)模型
(1)用戶
用戶首先將加密數(shù)據(jù)上傳至云服務(wù)器,當(dāng)需要檢索時(shí),上傳檢索密文關(guān)鍵詞,下載所需加密文檔,然后解密得到所需文件.
(2)云服務(wù)器
云服務(wù)器作為存儲(chǔ)和計(jì)算數(shù)據(jù)的平臺(tái),在密文數(shù)據(jù)中檢索計(jì)算,將計(jì)算結(jié)果發(fā)送給可信第三方,解密得到檢索序號(hào),根據(jù)檢索序號(hào)返回最終的加密文檔給用戶.
(3)可信第三方
可信第三方首先產(chǎn)生同態(tài)加密的公私鑰,并公布公鑰; 然后將云服務(wù)器發(fā)送過來的密文通過私鑰解密,篩選出檢索序號(hào),并發(fā)送給云服務(wù)器.
ElGamal 算法[21]是國際上公認(rèn)的公鑰密碼體制,其加密算法是基于Diffile-Hellman 密鑰交換算法[22],是由Taher ElGamal 在1985年提出,其安全性基于計(jì)算有限域上的離散對(duì)數(shù)難題,相比于RSA 算法,ElGamal算法能抵抗重放攻擊.該算法由參數(shù)設(shè)置、密鑰生成、加密、解密和同態(tài)乘法5 部分組成:
(1)參數(shù)設(shè)置
隨機(jī)選擇一個(gè)大素?cái)?shù)p,構(gòu)造一個(gè)模p的有限域Zp,g是Zp上的生成元,且g∈Zp.
(2)密鑰生成
隨機(jī)選取X∈[1,p-1],計(jì)算Y=gXmodp,私鑰SK={X},公鑰PK={p,g,Y}.
(3)加密
發(fā)送者對(duì)于明文消息m,隨機(jī)生成一個(gè)秘密數(shù)k∈[1,p-1],使用公鑰對(duì)明文消息加密得到密文:E(m)={γ=gkmodp,β=mYkmodp},其中,E(·)表示加密算法.
(4)解密
接收者收到密文消息{c1,c2}后,利用私鑰解密得到明文D(E(m))=β(γX)-1modp,其中,D(·)表示解密算法.
(5)同態(tài)乘法
若對(duì)于兩個(gè)明文消息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 算法具有乘法同態(tài)性.
如圖2 所示,是該方案中云端密文檢索系統(tǒng)的整體框架,同態(tài)計(jì)算和求逆在云服務(wù)器中進(jìn)行實(shí)現(xiàn).
圖2 密文檢索系統(tǒng)整體框架
(1)初始化
可信第三方生成ElGamal 的公私鑰對(duì),并將公鑰公開; 用戶在客戶端生成SM4 算法的密鑰.
(2)錄入數(shù)據(jù)
用戶使用同態(tài)公鑰將關(guān)鍵詞加密,使用SM4 密鑰將文件內(nèi)容加密,然后將加密后的關(guān)鍵詞和加密后的文檔一起上傳至云服務(wù)器存儲(chǔ),即錄入數(shù)據(jù).
(3)檢索數(shù)據(jù)
用戶使用同態(tài)公鑰加密檢索關(guān)鍵詞,再向云服務(wù)器提交檢索請(qǐng)求,即檢索數(shù)據(jù).
(4)同態(tài)計(jì)算
云服務(wù)器接收到檢索請(qǐng)求后,首先將密文檢索關(guān)鍵詞先求逆,然后逐個(gè)與密文關(guān)鍵詞相乘,最后將結(jié)計(jì)算結(jié)果發(fā)送給可信第三方; 可信第三方收到后使用同態(tài)私鑰進(jìn)行解密,返回給云服務(wù)器一個(gè)結(jié)果; 云服務(wù)器根據(jù)結(jié)果,返回給用戶相應(yīng)的檢索結(jié)果.
(5)解密數(shù)據(jù)
用戶在客戶端收到云服務(wù)器發(fā)送的加密文件后,用SM4 密鑰解密,得到檢索關(guān)鍵詞所對(duì)應(yīng)的明文文件.
下面具體介紹整個(gè)方案的流程結(jié)構(gòu),整個(gè)方案主要可以分成兩部分,第1 部分是錄入數(shù)據(jù),第2 部分是檢索數(shù)據(jù),且每個(gè)角色都有不同的功能,圖3 是方案檢索成功的詳細(xì)序列圖.
圖3 方案序列圖
下面分別詳細(xì)介紹這兩部分.
(1)用戶錄入數(shù)據(jù)
用戶待上傳n個(gè)明文文件(1≤i≤n),如表1 所示.
表1 待上傳的明文數(shù)據(jù)
本方案支持多關(guān)鍵詞檢索,設(shè)關(guān)鍵詞個(gè)數(shù)為m個(gè)(1≤j≤n),但關(guān)鍵詞數(shù)量增加會(huì)增加同態(tài)計(jì)算的次數(shù),引起時(shí)間復(fù)雜度的增加,因此在保證檢索的效果和減少時(shí)間開銷的前提下,我們應(yīng)當(dāng)控制關(guān)鍵詞數(shù)量,所以在下面的實(shí)驗(yàn)中,我們?nèi)=2.
用戶生成的密鑰有: 用于ElGamal 算法加解密公私鑰對(duì){PK,SK},以及SM4 分組密碼算法的密鑰{K}.
該方案采用的混合加密,關(guān)鍵詞用ElGamal 算法加密,文件內(nèi)容使用國密SM4 算法加密,然后合并一起上傳服務(wù)器.每個(gè)用戶擁有自己上傳文件的密鑰,可信第三方擁有所有加密關(guān)鍵詞的密鑰,具體如表2 所示.
表2 角色和密鑰分配
用戶上傳文件流程如圖4 所示.
圖4 文件上傳
1)可信第三方生成同態(tài)加密公私鑰
隨機(jī)取一個(gè)較大的素?cái)?shù)p,構(gòu)造一個(gè)模p的有限域Zp,g是Zp中的生成元,隨機(jī)取X∈Zp,計(jì)算出Y=gXmodp,得到同態(tài)加密的公私鑰對(duì){SK={X},PK={p,g,Y}},且公布公鑰PK.
2)用戶生成對(duì)稱加密的密鑰并加密數(shù)據(jù)
在客戶端取隨機(jī)數(shù)k∈Zp,使用公鑰PK對(duì)關(guān)鍵詞Mij加密,計(jì)算得{γij=gkmodp,βij=MijYkmodp},生成對(duì)應(yīng)的密文關(guān)鍵詞C_Mij.其中文件關(guān)鍵詞Mij在加密前需要通過Unicode 編碼為十六進(jìn)制字符串并轉(zhuǎn)為整數(shù)形式; 在客戶端生成128 位的隨機(jī)數(shù)作為SM4 密鑰K并保存在本地,并使用密鑰K對(duì)文件加密得到密文文件C_Fi.
3)用戶上傳密文數(shù)據(jù).
將C_Mij和C_Fi拼接一起發(fā)送給云服務(wù)器存儲(chǔ).此時(shí)云服務(wù)器中的存儲(chǔ)內(nèi)容如表3 所示.
表3 云端中的密文數(shù)據(jù)
(2)用戶檢索數(shù)據(jù)
用戶檢索數(shù)據(jù)的流程如圖5 所示,該部分包含5 個(gè)階段.
圖5 用戶檢索文件
1)加密檢索關(guān)鍵詞
假設(shè)密文數(shù)據(jù)庫中的密文文件有n個(gè),用戶先將檢索關(guān)鍵詞Q通過Unicode 編碼為十六進(jìn)制字符串,并轉(zhuǎn)為整數(shù)形式得到Q*,這時(shí)使用之前生成的公鑰PK 對(duì)Q*進(jìn)行同態(tài)加密,計(jì)算得到{γQ=gkmodp,βQ=(Q*)Ykmodp},即生成檢索關(guān)鍵詞的密文C_Q*={γQ,βQ}.
2)同態(tài)計(jì)算
云服務(wù)器收到密文檢索關(guān)鍵詞C_Q*后,求逆得到(C_Q*)-1,然后逐個(gè)與密文關(guān)鍵詞C_Mij={γij,βij}做同態(tài)乘法得到具體運(yùn)算如式(1):
3)可信第三方解密
4)云服務(wù)器返回檢索結(jié)果
云服務(wù)器根據(jù)收到可信第三方返回的解密結(jié)果來判斷是否將密文文件發(fā)送給用戶: 若返回的是一個(gè)非0 的結(jié)果s(1 ≤s≤n),則返回序號(hào)為s所對(duì)應(yīng)的密文文件C_Fs; 若返回值為0,則表示未檢索到結(jié)果,向用戶發(fā)送“查詢失敗”的信息.
5)用戶解密
用戶從云服務(wù)器下載到密文文件C_Fs(1 ≤s≤n),利用SM4 的密鑰K對(duì)文件解密,得到最終檢索關(guān)鍵詞所對(duì)應(yīng)的原文件Fs.
本節(jié)通過一個(gè)具體的案例來驗(yàn)證本方案,加密原文件可以是圖書內(nèi)容,圖書數(shù)量n=4,關(guān)鍵詞個(gè)數(shù)m=2,關(guān)鍵詞M1 和M2 分別是書名和作者,實(shí)驗(yàn)環(huán)境為Intel(R)Core i5-6200U @ 2.30 GHz 雙核16 GB 內(nèi)存,Microsoft Visual Studio Community 2019.
(1)假設(shè)用戶有待加密上傳的文件如表4,以明文形式展示.
表4 明文數(shù)據(jù)
上面的明文數(shù)據(jù)使用混合加密,即關(guān)鍵詞{書名、作者}使用ElGamal 算法加密,文件內(nèi)容使用SM4 算法加密.
(2)將關(guān)鍵詞用Unicode 編碼為十六進(jìn)制字符串,并轉(zhuǎn)為整數(shù)形式,見表5.
表5 關(guān)鍵詞
將關(guān)鍵詞(整數(shù)形式)使用ElGamal 加密,參數(shù)設(shè)置:(p,g)(40049372667947663039,11743527543478996065),(X,Y)=(14450894889756208713,255895591548258 90551)將文件內(nèi)容使用SM4 加密,然后上傳云服務(wù)器,密文數(shù)據(jù)庫如表6.
表6 密文數(shù)據(jù)
(3)若用戶輸入檢索關(guān)鍵詞Q=“史記”,先用Unicode 編碼為十六進(jìn)制字符串,并轉(zhuǎn)為整數(shù)形式Q*,然后使用ElGamal 加密(Q*)-1得到檢索關(guān)鍵詞的逆元密文C_Q*={γQ,δQ},結(jié)果如表7 所示.
表7 檢索關(guān)鍵詞
(4)云服務(wù)器收到檢索關(guān)鍵詞的密文C_Q*后,將密文檢索關(guān)鍵詞求逆得(C_Q*)-1= {37747856122936643469,13243315324064048566},然后逐個(gè)與密文數(shù)據(jù)庫中的密文關(guān)鍵詞C_Mij做乘法得到(C_Q)*ij(i,j∈Z,1 ≤i≤4且1 ≤j≤2),如表8所示.
表8 同態(tài)乘法運(yùn)算密文相乘結(jié)果
表8 同態(tài)乘法運(yùn)算密文相乘結(jié)果
序號(hào)關(guān)鍵詞1關(guān)鍵詞2 1{1 23 1216929236222963946,128607310697629708}{33593146621890140288,37977864468152489955}2{18283956446679924477,24618066340401802334}{1366231225410332531,29051288589689848885}3{33896692461687507920,4109244469603721049}{34946155032641737178,22886193455501072227}4{10896494947855593771,3808468191905602827}{25731605953598699893,1282281649647820192}
云服務(wù)器將計(jì)算的結(jié)果發(fā)送給可信第三方,可信第三方收到消息后,使用私鑰SK逐個(gè)解密得到Q*ij(i,j∈Z,1 ≤i≤4且1 ≤j≤2),如表9.這里的Q*21=1,所以將s=2 返回給服務(wù)器.
表9 第三方解密結(jié)果(C_Q)*ij的解密結(jié)果
(5)云服務(wù)器收到可信第三方發(fā)來的s=2,將E(F2)發(fā)送給用戶,即用戶從云服務(wù)器下載到E(F2),最后使用SM4 密鑰解密得到原文件F2.
在該方案中,用戶首先要將加密后的文件和關(guān)鍵詞上傳至云端,然后從云端檢索出關(guān)鍵詞對(duì)應(yīng)的加密文件,解密即可得到檢索的文件,所以本方案的安全性可分為數(shù)據(jù)存儲(chǔ)安全性和檢索模型安全性.
(1)數(shù)據(jù)存儲(chǔ)安全性
關(guān)鍵詞是采用ElGamal 算法加密的,相比于RSA算法,ElGamal 算法能抵抗重放攻擊,另外根據(jù)計(jì)算有限域上的離散對(duì)數(shù)困難,攻擊者很難根據(jù)公鑰PK去計(jì)算或推導(dǎo)出私鑰SK,這就使得用戶在密文檢索過程中,攻擊者就算得到公鑰PK,也不能作為云服務(wù)器和可信第三方之間的中間者去解密云服務(wù)器發(fā)送的同態(tài)計(jì)算結(jié)果,這就保證了用戶在檢索過程中檢索數(shù)據(jù)不可篡改.
再者就是文件采用的是國密SM4 分組算法.加解密過程均由用戶在客戶端完成,云服務(wù)器無法獲知其密鑰K.SM4 保證了文件的安全性[23],可以抵抗窮舉攻擊、差分攻擊、線性攻擊等攻擊手段,具有較高的安全性,使得攻擊者即使獲得加密文件,也無法作為用戶和云服務(wù)器之間的中間者解密出原文件.
(2)檢索模型安全性
密文檢索過程滿足乘法同態(tài)性.方案中同態(tài)加密的公私鑰均由可信第三方生成,用戶將關(guān)鍵詞和文件加密上傳至云端,都是以密文形式存儲(chǔ).用戶將加密的檢索關(guān)鍵詞上傳至云端,利用同態(tài)加密的性質(zhì),將加密的檢索關(guān)鍵詞與云端中存儲(chǔ)的密文關(guān)鍵詞做乘法同態(tài)運(yùn)算,再利用可信第三方解密來求出檢索號(hào),以此完成密文檢索.由于整個(gè)過程均是在密文下進(jìn)行的,所以說云端是無法獲知任何有關(guān)密鑰和明文數(shù)據(jù)的,且只有用戶才能獲得明文數(shù)據(jù),這就保證了檢索過程中的數(shù)據(jù)是安全的,所以說檢索模型是安全的.
(1)效率分析
在本方案中的密文檢索只使用了乘法同態(tài),也就是只用部分同態(tài)來實(shí)現(xiàn),當(dāng)然也可以使用全同態(tài)來實(shí)現(xiàn)密文檢索,但目前全同態(tài)效率比較低,難以廣泛使用.以下面的例子為例,來證明本文使用部分同態(tài)比全同態(tài)效率更高.如表10,加密1 000 數(shù)字1 000 次,取10 次試驗(yàn)的平均時(shí)間; 將1 000 和2 000 的密文相乘,取10 次試驗(yàn)的平均耗時(shí),明顯可以看出使用ElGamal在加密和乘法同態(tài)運(yùn)算上速度更快.另外表11 展示與其他方案的對(duì)比,可以看出本方案更加輕量高效 這里BGV 算法和CKKS 算法的測(cè)試程序采用的是IBM 的開源庫fhe-toolkit-linux[15]; BFV 算法的測(cè)試程序采用的是微軟的開源庫SEAL[24].
表10 測(cè)試時(shí)間(ms)
表11 方案對(duì)比
(2)精確度分析
本方案針對(duì)個(gè)人用戶就是在云端構(gòu)建單用戶的密文數(shù)據(jù),進(jìn)而在云端進(jìn)行安全檢索,因?yàn)橐粋€(gè)文件可以有多個(gè)關(guān)鍵詞,所以用戶在檢索時(shí),既可以實(shí)現(xiàn)單個(gè)關(guān)鍵詞檢索,也可以實(shí)現(xiàn)多關(guān)鍵詞檢索.
單個(gè)關(guān)鍵詞檢索時(shí),檢索結(jié)果只有兩種: 找到文件或者是未檢索到; 多關(guān)鍵詞檢索時(shí),若輸入的是一個(gè)文件對(duì)應(yīng)的多個(gè)關(guān)鍵詞,那么只要有一個(gè)匹配上,則檢索成功,若輸入的是多個(gè)文件對(duì)用的關(guān)鍵詞,則返回多個(gè)匹配上的文件,進(jìn)而實(shí)現(xiàn)多文件檢索,這樣效率會(huì)更加高,其精確度和效率遠(yuǎn)高于逐個(gè)關(guān)鍵詞檢索.
本文利用同態(tài)加密的性質(zhì),設(shè)計(jì)出新的密文檢索模型,再結(jié)合安全的國密算法,提出了一個(gè)基于同態(tài)加密的云端密文存儲(chǔ)檢索方案.該方案能夠在保證數(shù)據(jù)安全的前提下進(jìn)行數(shù)據(jù)檢索,即檢索過程中云端無法獲知任何有關(guān)密鑰信息和明文數(shù)據(jù).與其他方案相比,具有輕量級(jí)和高效性,可以應(yīng)用于小型個(gè)人云端U 盤的場景,有較好的實(shí)用價(jià)值.經(jīng)實(shí)驗(yàn)數(shù)據(jù)分析表明,本文方案檢索結(jié)果正確、安全性好、效率高、實(shí)用性強(qiáng).在下一步的研究中,將嘗試設(shè)計(jì)一種高效的全同態(tài)加密算法,并將其應(yīng)用在云端密文檢索中,使之具有更好的安全性.