基于全同態(tài)加密的ORAM方案

宋寧寧

(中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京 100083)

0 引言

大數(shù)據(jù)時代信息總量以驚人的速度增長[1]，云存儲可為用戶提供按需、彈性、高效、可擴展、低成本的存儲服務。用戶將數(shù)據(jù)存儲在云端，這使數(shù)據(jù)的歸屬權(quán)和管理權(quán)分離，在云服務提供商不可信的情況下，用戶需要對敏感數(shù)據(jù)進行加密保證其機密性。用戶可以將敏感數(shù)據(jù)進行加密后將密文傳到服務器端進行存儲，需要使用時進行下載并用密鑰解密，進而得到明文數(shù)據(jù)，但云端密文數(shù)據(jù)的檢索、處理等可用性受到影響。因此，如何在保證存儲安全的同時，實現(xiàn)密文檢索是大數(shù)據(jù)安全存儲需要解決的關(guān)鍵問題[2]。

除了保證密文機密性，檢索關(guān)鍵詞的安全性，本文對密文檢索在訪問模式方面的安全性提出了新的要求。訪問模式指的是用戶訪問云端數(shù)據(jù)的模式，包括訪問類型是讀操作還是寫操作、訪問概率等信息。通常密文檢索算法考慮密文檢索中的密文機密性和檢索關(guān)鍵詞的安全性，忽略訪問模式帶來的隱私泄露。但是，不完全可信的云端通過長時間地觀察用戶的訪問模式，通過復雜的統(tǒng)計分析獲得關(guān)于用戶查詢數(shù)據(jù)的隱私信息，造成用戶的隱私泄露。不經(jīng)意隨機存儲機(ORAM)機制[3]能夠允許用戶對云端進行讀操作或?qū)懖僮?，但云端無法對讀操作和寫操作進行區(qū)分，同時云端也無法獲取用戶對某個密文的訪問概率，從而達到保護密文檢索訪問模式的目的。

現(xiàn)有的ORAM方案主要有平方根方案、分層方案[4]和二叉樹方案[5]。其他ORAM實現(xiàn)方案都是基于這三種方案的改進或變形。現(xiàn)有的ORAM方案，數(shù)據(jù)的加密和解密均在用戶端進行，且均沒有將數(shù)據(jù)的加密和解密造成的復雜度放入算法復雜度的計算中。由于數(shù)據(jù)的加密和解密均在客戶端執(zhí)行，盡管保證了數(shù)據(jù)的機密性，但是大量的數(shù)據(jù)加密和解密操作對用戶端的計算負載和通信負載造成了巨大的負擔，特別是為了實現(xiàn)不經(jīng)意性，用戶和云端存在大量的I/O操作，這會造成效率的降低和資源的浪費，不能夠完全發(fā)揮云端高性能、分布式的特點。全同態(tài)加密[6]可以實現(xiàn)在不對密文數(shù)據(jù)解密的情況下操作密文數(shù)據(jù)，對計算后的密文進行解密的結(jié)果與直接對明文數(shù)據(jù)操作的結(jié)果一致。因此，本文引入全同態(tài)加密算法來構(gòu)建ORAM，在保證檢索安全、訪問模式安全的前提下，能夠提高云端計算和存儲資源的利用率，盡可能地減少用戶端負擔。

1 密文檢索模型

目前，云存儲密文檢索模型通常由用戶和云端兩部分組成，檢索模型分為初始化階段和檢索執(zhí)行階段，用戶和云端在初始化和檢索這兩個階段相互作用，實現(xiàn)用戶的密文檢索。在初始化階段，假設用戶有n個文件F={F1,…,Fn}。在云端不完全可信的情況下，為了保證數(shù)據(jù)的機密性，用戶必須在本地完成對數(shù)據(jù)的加密。假設加密算法采用對稱加密機制AES算法[7]，其對稱密鑰為k。用戶使用密鑰k對文件集合F進行加密生成密文集合C={C1,…,Cn}，其中Ci=ENk(Di)。用戶將密文集合C={C1,…,Cn}上傳至云端，初始化階段結(jié)束。

在初始化階段，用戶在本地將數(shù)據(jù)加密后再上傳至云端，云端沒有相應的密鑰，因此，基于加密算法的安全性，云端無法獲知用戶的明文信息內(nèi)容，從而保證了用戶信息的機密性。

在檢索階段，假設用戶需要云端查找并返回所有與關(guān)鍵字w相關(guān)的加密文件，為了保證檢索關(guān)鍵字的安全性，用戶使用檢索關(guān)鍵字w構(gòu)建一個安全令牌token，要保證該令牌token不會泄露任何關(guān)于關(guān)鍵字w的信息。用戶將此令牌上傳至云端，云端利用令牌token在加密數(shù)據(jù)庫中找到用戶想要的加密文件，并返回給用戶。用戶接收密文文件并在本地進行解密獲得文件明文。

至此，定義了密文檢索通用模型，通過模型可以看出，為了保證用戶數(shù)據(jù)的機密性和檢索關(guān)鍵字的安全性，模型分別采用了數(shù)據(jù)加密和構(gòu)建安全令牌機制。隨著信息安全、攻擊等信息技術(shù)的發(fā)展，對密文檢索的安全有了更高等級的定義。在對比現(xiàn)有密文檢索機制之前，先對密文檢索安全進行定義。一個密文檢索算法需要具備以下安全屬性：

(1)文件密文集合不能夠泄露任何關(guān)于文件明文集合的信息；

(2)用戶生成的令牌token不能泄露任何關(guān)于明文關(guān)鍵詞w的信息；

(3)密文的檢索不能夠泄露用戶的訪問模式[8]。

2 不經(jīng)意隨機存儲機(ORAM)模型

一個安全的ORAM模型包括三個算法[9-10]，分別是初始化算法setup，讀操作read和寫操作write。下面分別定義這三個算法。

(1)setup：初始化算法具體為：首先用戶生成一個安全參數(shù)1k，一個擁有N個數(shù)據(jù)文件的RAM集合和原始文件索引i；執(zhí)行初始化算法后，輸出一個密鑰K(可以采用對稱加密算法或公鑰加密算法)，一個經(jīng)過加密后的ORAM以及密文索引EN(i)。

(2)read：讀操作是一個兩方協(xié)議，在用戶和云端同時執(zhí)行。用戶希望獲得原始索引為i所對應的RAM文件，用戶執(zhí)行讀操作兩方協(xié)議，輸入為密鑰K和密文索引EN(i)；與此同時，云端執(zhí)行讀操作兩方協(xié)議，輸入為ORAM。讀操作兩方協(xié)議分別在用戶端和云端執(zhí)行后，用戶收到原始索引i對應的元素RAM[i]，同時云端得到重新加密后的ORAM′和⊥，其中⊥為空信息，表示云端無法獲知用戶讀取的經(jīng)意隨機存儲機ORAM的具體位置。讀操作兩方協(xié)議總結(jié)公式為：

read((K,EN(i)),ORAM)=

(1)

(3)write：寫操作同樣是一個在用戶和云端同時執(zhí)行的兩方協(xié)議。用戶希望將云端保存的原始索引i對應的數(shù)據(jù)文件更新為新的文件值v，用戶執(zhí)行寫操作兩方協(xié)議，輸入密鑰K，索引EN(i)和新的文件值v；同時云端執(zhí)行寫操作兩方協(xié)議，輸入為ORAM。寫操作兩方協(xié)議執(zhí)行后，用戶端得到⊥，同時，云端得到一個更新的ORAM′和⊥，存儲在ORAM中的索引為i的元素被更新為值v，用戶完成原始索引i對應的數(shù)據(jù)文件的更新。讀操作兩方協(xié)議總結(jié)公式為：

write((K,EN(i),v),ORAM)=

(2)

根據(jù)以上定義可以看出，ORAM模型首先利用數(shù)據(jù)加密和索引加密保證了用戶數(shù)據(jù)的機密性和索引的安全性。用戶和云端執(zhí)行讀操作和寫操作的兩方協(xié)議，實現(xiàn)用戶對數(shù)據(jù)的讀取、存儲或更新，而云端得到的都是一個經(jīng)過更新后的ORAM′。因此，在云端看來，用戶的讀操作和寫操作是同樣的過程，云端無法分辨。此外，云端得到⊥，也就是說云端無法獲取用戶的讀取或?qū)懭氲臄?shù)據(jù)位置的訪問概率。

3 基于全同態(tài)加密的不經(jīng)意隨機存儲機方案

全同態(tài)加密[6]是對同態(tài)加密算法的發(fā)展和延伸，其最主要的特性是，對密文數(shù)據(jù)進行一系列的加法操作和乘法操作后經(jīng)過解密得到的數(shù)據(jù)，與直接對原文數(shù)據(jù)進行上述操作得到的數(shù)據(jù)一樣。首先，對全同態(tài)加密[6]算法方案由四個多項式時間復雜度的子算法組成FHE=(FKeyGen,FEnc,FDec,FEval)，分別是：全同態(tài)密鑰生成算法FKeyGen，全同態(tài)加密算法FEnc，全同態(tài)解密算法FDec和全同態(tài)賦值算法FEval。假設，構(gòu)建全同態(tài)加密方案的安全參數(shù)為1k，四個子算法定義如下：

(1)全同態(tài)加密算法FKeyGen：系統(tǒng)根據(jù)用戶輸入的安全參數(shù)1k，生成全同態(tài)加密公私鑰對(pk,sk)=FKeyGen(1k)。

(2)全同態(tài)加密算法FEnc：用戶輸入數(shù)據(jù)明文m，使用全同態(tài)加密公鑰pk進行加密得到相應的密文c=FEnc(pk,m,r)，其中r為隨機數(shù)，保證使用相同的密鑰對相同的明文加密能夠得到不同的密文。

(3)全同態(tài)解密算法FDec：用戶輸入數(shù)據(jù)密文c，使用全同態(tài)加密私鑰sk進行解密得到相應的明文m=FDec(sk,c)。

(4)全同態(tài)賦值算法FEval：用戶輸入全同態(tài)加密公鑰pk，n個密文集合c={c1,c2,…,cn}(對應的明文集合為m={m1,m2,…,mn})和一個由加法門和乘法門構(gòu)成的多入多出的計算電路f，根據(jù)用戶對密文的操作需來確定計算電路的形式，如fn|1表示輸入n個密文經(jīng)過計算后輸出1個密文，fn|n表示輸入n個密文經(jīng)過計算后輸出n個密文。運行賦值算法FEval輸出計算的密文c′=FEval(c,f,pk)，其中c′是根據(jù)原密文集合c={c1,c2,…,cn}和某些參數(shù)經(jīng)過計算電路f計算后得到的新密文集合，且集合元素順序隨機變化。明文集合m和計算后的密文c′滿足公式f(m)=FDec(sk,FEval(pk,f,c′))。

通過上述定義可以看出，本文設計的全同態(tài)加密算法與傳統(tǒng)全同態(tài)加密算法在全同態(tài)密鑰生成算法FKeyGen、全同態(tài)加密算法FEnc、全同態(tài)解密算法FDec這三個算法上保持一致。對于全同態(tài)賦值算法FEval進行了擴展，將傳統(tǒng)全同態(tài)加密算法的賦值算法FEval定義為一個多入多出的計算電路。為了完成特定的計算功能，用戶設計相應的計算電路，實現(xiàn)不解密密文直接對密文進行操作，多對一或者多對多的輸入和輸出關(guān)系。使用全同態(tài)加密算法構(gòu)建ORAM的方法如下：

(1)setup(1k,RAM)：初始化階段，用戶通過計算(pk,sk)=FKeyGen(1k)，生成一個用于全同態(tài)加密算法的公私鑰對(pk,sk)。用戶生成隨機數(shù)r，并使用公鑰pk加密RAM和索引i，可以得到密文數(shù)據(jù)c=FEnc(pk,RAM,r)和密文索引EN(i)=FEnc(pk,i,r)，輸出一個ORAM并上傳到云端。

(3)write((K,EN(i),v),ORAM)：寫操作，用戶使用公鑰pk重新加密需要寫入的文件的索引i得到EN(i)=FEnc(pk,i,r)，并發(fā)送給云端。云端執(zhí)行全同態(tài)賦值算法，輸入ORAM，計算cEN(i)=FEval((ORAM,EN(i)),fn|1,pk)，并將cEN(i)返回給用戶。用戶收到cEN(i)后直接丟棄，然后用戶加密待寫入的值cv=FHE.encK(v)，并將cv上傳至云端，云端再次執(zhí)行全同態(tài)賦值算法ORAM′=FEval((ORAM,cv,EN(i)),fn|1,pk)，其中云端將ORAM′代替原來的ORAM。

4 安全性分析

分析FHE-ORAM方案的檢索安全性。在ORAM初始化階段，用戶使用全同態(tài)加密對RAM進行加密，向云端發(fā)送ORAM時不會泄露任何關(guān)于RAM的信息，因此符合密文檢索安全定義中(1)的要求。用戶在執(zhí)行讀操作和寫操作時向云端發(fā)送的令牌token為文件索引的加密值ci，不會泄露關(guān)于索引i的信息，因此，符合密文檢索安全定義的要求。用戶在執(zhí)行讀操作和寫操作時，運行兩次全同態(tài)賦值算法，利用全同態(tài)加密的性質(zhì)，直接對密文進行操作。第一次賦值算法使用戶從云端獲取索引i對應的新密文數(shù)據(jù)，新密文數(shù)據(jù)經(jīng)過全同態(tài)加密處理，和ORAM中索引i對應的密文數(shù)據(jù)在密碼學上無法分辨其聯(lián)系，從而保證云端無法獲知用戶“讀”或“寫”的位置。第二次賦值算法用戶上傳索引i對應的經(jīng)過重新加密原明文或加密新明文的密文數(shù)據(jù)，更新整個ORAM。因此，云端同樣無法獲知用戶“讀”或“寫”的位置。通過讀操作和寫操作的定義可知，在云端看來，用戶的讀操作和寫操作都是執(zhí)行兩次賦值算法，具體包括返回給用戶一個密文、用戶上傳一個密文以及云端更新整個ORAM這三個過程，云端無法分辨用戶的“讀”或“寫”，從而對用戶的訪問模式進行了保護，因此符合密文檢索安全定義的要求。綜上所述，本文設計的基于全同態(tài)加密的不經(jīng)意隨機存儲機方案滿足檢索安全的定義。

5 結(jié)論

在云服務提供商不完全可信的情況下，為了保護數(shù)據(jù)的機密性，用戶將數(shù)據(jù)在本地進行加密后傳到云端，導致無法靈活地對存儲在云端的數(shù)據(jù)進行查詢、更新等操作，云數(shù)據(jù)可用性較低?，F(xiàn)有密文檢索機制在保護用戶數(shù)據(jù)、檢索關(guān)鍵詞安全的基礎上實現(xiàn)密文的檢索，但是并不能保護密文訪問模式隱私安全。本文在研究現(xiàn)有密文檢索機制的基礎上，構(gòu)建了基于全同態(tài)加密的不經(jīng)意隨機存儲機方案，保護用戶數(shù)據(jù)、檢索關(guān)鍵詞的同時，基于其“不經(jīng)意”性實現(xiàn)訪問模式的隱藏保護。目前全同態(tài)方案算法復雜度高，加解密效率相對較低，下一步將研究降低方案的復雜度，提高可用性。