一種基于ORAM的數(shù)據(jù)可恢復(fù)性證明與訪問模式的隱藏*

李紅衛(wèi) ，葉飛躍 ，陳 丹

（1.江蘇理工學(xué)院計(jì)算機(jī)工程學(xué)院 常州 213001；2.江蘇理工學(xué)院云計(jì)算與智能信息處理常州市重點(diǎn)實(shí)驗(yàn)室 常州 213001)

1 引言

云計(jì)算的發(fā)展極大地滿足了客戶對(duì)計(jì)算的需求，云存儲(chǔ)的應(yīng)用使得用戶可以將數(shù)據(jù)存儲(chǔ)在云中，以一種靈活、按需的方式使用和管理云中的數(shù)據(jù)。云存儲(chǔ)的使用不但減輕了用戶對(duì)存儲(chǔ)管理的負(fù)擔(dān)，而且對(duì)數(shù)據(jù)的訪問不再受限于地理位置，并可降低硬件、軟件、人力資源等方面的投資成本[1]。但云存儲(chǔ)的安全性與可靠性仍是制約云存儲(chǔ)服務(wù)快速發(fā)展的關(guān)鍵問題。這主要體現(xiàn)在兩方面：一是云服務(wù)提供商(cloud service provider，CSP)能否有效地保證數(shù)據(jù)的完整性。例如，由于管理不當(dāng)或設(shè)備故障造成數(shù)據(jù)損壞或丟失時(shí)，CSP能否盡快恢復(fù)數(shù)據(jù)。二是來自敵手的攻擊，敵手可以通過某種途徑篡改數(shù)據(jù)，CSP能否及時(shí)發(fā)現(xiàn)并恢復(fù)數(shù)據(jù)。另外，敵手還可以從用戶訪問數(shù)據(jù)的模式中間接地獲知用戶的操作信息[2]。例如，敵手獲知用戶對(duì)數(shù)據(jù)的訪問為某一序列時(shí)將做出某項(xiàng)決策，當(dāng)類似的訪問序列再次出現(xiàn)時(shí)，敵手可以推測到用戶的活動(dòng)。本文從云存儲(chǔ)中數(shù)據(jù)的可恢復(fù)性和隱藏?cái)?shù)據(jù)訪問模式展開研究，提出了證明數(shù)據(jù)的可持有性，實(shí)現(xiàn)數(shù)據(jù)的可恢復(fù)性，并且隱藏了數(shù)據(jù)的訪問模式。

2 相關(guān)研究

Juels和Kaliski[3]最先提出了可恢復(fù)性證明(proof of retrievability,POR)，并提出基于哨兵的方案。其基本思想是先對(duì)原文件F加密，再用糾錯(cuò)碼對(duì)加密后的文件F’進(jìn)行編碼形成文件F”，然后在F”中隨機(jī)選取若干哨兵，每一個(gè)哨兵可監(jiān)測一部分?jǐn)?shù)據(jù)，并將這些哨兵的值存儲(chǔ)在客戶端，然后把文件F”存儲(chǔ)在云端。客戶可以利用哨兵質(zhì)詢服務(wù)器，驗(yàn)證文件的可恢復(fù)性。與此同時(shí)，Ateniese等人[4]提出了可證明數(shù)據(jù)擁有 (provable data possession,PDP)模型，并提供了基于RSA模指運(yùn)算構(gòu)造同態(tài)標(biāo)簽以實(shí)現(xiàn)數(shù)據(jù)持有性證明。這兩種模型的主要區(qū)別是PDP只驗(yàn)證了數(shù)據(jù)是否完整，而沒有考慮遭到破壞后的數(shù)據(jù)是否可恢復(fù)。在他們研究的基礎(chǔ)上，又有很多研究者提出了一些改進(jìn)方法和新的方案[5～9]。其中，陳蘭香[9]提出一種基于同態(tài)散列的數(shù)據(jù)持有性證明方法，利用同態(tài)散列算法的同態(tài)性，即兩數(shù)據(jù)塊之和的散列值與它們散列值的乘積相等，驗(yàn)證數(shù)據(jù)的持有性。但這兩種模型有一個(gè)共同缺點(diǎn)，它們只考慮了數(shù)據(jù)的持有性或可恢復(fù)性，沒有對(duì)客戶訪問數(shù)據(jù)模式進(jìn)行隱藏，使得敵手可以跟蹤客戶對(duì)數(shù)據(jù)訪問的模式，從中獲取信息。另外，在POR模型中，如果數(shù)據(jù)所在的磁盤存儲(chǔ)塊受到物理損傷，或敵手大量篡改數(shù)據(jù)，即使使用糾錯(cuò)碼也無法恢復(fù)原有數(shù)據(jù)。

Goldreich最早提出 ORAM （oblivious random access machine），并與Ostrovsky[10]提出了隱藏客戶對(duì)存儲(chǔ)器的訪問模式以防止軟件逆向工程。隨著云計(jì)算的發(fā)展，ORAM在云存儲(chǔ)隱私保護(hù)方面也有著重要的應(yīng)用[11]。在參考文獻(xiàn)[10]中提出的最有效的算法是金字塔形分層算法，它對(duì)數(shù)據(jù)所占用的存儲(chǔ)塊按金字塔形狀管理，該算法分為訪問和洗牌兩個(gè)階段。訪問階段又分為讀和寫兩部分，在讀部分，ORAM順序讀取金字塔形第1層所有盒子中的數(shù)據(jù)塊，然后再讀其他每一層中的某一個(gè)盒子（由散列函數(shù)決定）中的數(shù)據(jù)塊。在整個(gè)讀過程中，如果找到了目標(biāo)數(shù)據(jù)塊，則后繼選擇啞元塊讀取。寫部分比較簡單，對(duì)目標(biāo)塊進(jìn)行處理后寫入第1層中的空位置即可。但由于客戶的每一次請求都會(huì)將數(shù)據(jù)塊寫入第1層，當(dāng)?shù)?層放滿數(shù)據(jù)塊后需要將第1層和第2層的數(shù)據(jù)塊重新排列后存放到第2層中，第1層清空。類似地，在第2i次數(shù)據(jù)訪問之后，第i層的數(shù)據(jù)塊和第i+1層的數(shù)據(jù)塊重新排列后存儲(chǔ)到第i+1層，前i層清空，這個(gè)過程稱作洗牌。洗牌是分層算法中最復(fù)雜的階段，它是該算法性能的瓶頸。洗牌的關(guān)鍵操作是無關(guān)地排序數(shù)據(jù)塊。若采用AKS網(wǎng)絡(luò)排序算法時(shí)，平均時(shí)間復(fù)雜度為O(clog3N)，若采用巴切排序算法時(shí)，平均時(shí)間復(fù)雜度為O(dlog4N)(c>>d)。在洗牌階段若客戶訪問數(shù)據(jù)，客戶可能會(huì)等待較長時(shí)間。因此，這樣的算法若應(yīng)用于實(shí)際環(huán)境中則無法讓人容忍它的低效率。許多研究者[11～16]在分層算法的基礎(chǔ)上又提出了一些新的算法，旨在降低存儲(chǔ)空間占有量和平均訪問時(shí)間復(fù)雜度。但這些算法均由訪問和洗牌兩個(gè)階段構(gòu)成，洗牌仍是算法的瓶頸。

本文提出一種ORAM結(jié)構(gòu)，在需要少量客戶端存儲(chǔ)空間和線性級(jí)服務(wù)器存儲(chǔ)容量的情況下，把洗牌過程均攤到每次訪問操作中，使得對(duì)服務(wù)器的訪問時(shí)間可保持在常量級(jí)。同時(shí)結(jié)合同態(tài)散列算法驗(yàn)證數(shù)據(jù)的可持有性并利用副本實(shí)現(xiàn)數(shù)據(jù)的可恢復(fù)性。

3 ORAM結(jié)構(gòu)

ORAM模型機(jī)可以隱藏客戶對(duì)服務(wù)器的訪問模式，即除客戶外，其他任何角色每次看到客戶對(duì)數(shù)據(jù)的訪問序列都是相似的。本文假定ORAM模型機(jī)是由可信任的客戶端和不可信的服務(wù)器端構(gòu)成。

3.1 服務(wù)器中文件的結(jié)構(gòu)

假設(shè)客戶文件是由N個(gè)數(shù)據(jù)塊組成，每個(gè)數(shù)據(jù)塊在服務(wù)器端存儲(chǔ)兩份，并增加2N個(gè)啞元塊使得敵手觀察客戶的訪問模式時(shí)無法確認(rèn)哪個(gè)是真實(shí)的數(shù)據(jù)塊。在本方案中總共需要4N個(gè)服務(wù)器存儲(chǔ)塊，利用隨機(jī)均勻函數(shù)將2N個(gè)數(shù)據(jù)塊映射到4N個(gè)存儲(chǔ)塊中，剩余存儲(chǔ)塊存放啞元塊。

為了提高數(shù)據(jù)存儲(chǔ)的可靠性，可將一個(gè)大數(shù)據(jù)文件分割成若干大小為S個(gè)存儲(chǔ)塊的文件存儲(chǔ)。由于客戶的一個(gè)數(shù)據(jù)塊在服務(wù)器中有兩個(gè)備份，且隨機(jī)均勻地分布在不同的文件中，當(dāng)一個(gè)文件損壞時(shí)，該文件中的所有數(shù)據(jù)塊均可從其他的文件中恢復(fù)。

3.2 客戶端數(shù)據(jù)結(jié)構(gòu)

在客戶端設(shè)置BufM和BufA兩個(gè)緩沖器，兩張數(shù)據(jù)表SerMap[4N]和 PosMap[N]。

BufM是一個(gè)可存放6個(gè)存儲(chǔ)塊的緩沖器。采用FIFO算法對(duì)BufM進(jìn)行管理，將每次客戶所訪問的數(shù)據(jù)塊存放到該緩沖器中。

BufA的大小與BufM相等，每次讀/寫數(shù)據(jù)塊時(shí)，將隨機(jī)讀的數(shù)據(jù)塊和啞元塊存放到該緩沖器中；當(dāng)客戶是寫操作時(shí)，會(huì)把一個(gè)備份放到該緩沖器中；當(dāng)BufM滿時(shí)會(huì)將其中一個(gè)最久未用的數(shù)據(jù)塊移到BufA中，以保證每次客戶在訪問云存儲(chǔ)時(shí)，BufM至少有一個(gè)空閑塊。如果BufA不滿則用啞元塊填滿。最后將BufA中的數(shù)據(jù)塊寫回云存儲(chǔ)器中。

數(shù)據(jù)表SerMap描述存儲(chǔ)在服務(wù)器上各數(shù)據(jù)塊的屬性，每次訪問服務(wù)器時(shí)均需要調(diào)整該表內(nèi)容，以適應(yīng)ORAM的變化。該表有6個(gè)域，分別是FlagD、FlagA、Fresh、PdpG[8]、PdpA[8]和 PdpH[8]。FlagD 為數(shù)據(jù)塊標(biāo)識(shí)，其值為1表示該塊為數(shù)據(jù)塊，否則為啞元塊。FlagA標(biāo)識(shí)存儲(chǔ)塊最近是否被訪問過。每當(dāng)一個(gè)存儲(chǔ)塊讀到緩沖器中時(shí)，設(shè)置該塊對(duì)應(yīng)的FlagD為0；FlagA為1，表示該存儲(chǔ)塊為啞元塊且最近被訪問過。當(dāng)一個(gè)數(shù)據(jù)塊被寫入服務(wù)器時(shí)，會(huì)隨機(jī)找一個(gè)最近沒被訪問過的啞元塊寫入，并修改該塊對(duì)應(yīng)的FlagD為1。在查找啞元塊的過程中，若其對(duì)應(yīng)的FlagA為1，則修改其值為0，以便下次查找到該塊時(shí)能被選中。Fresh表示服務(wù)器存儲(chǔ)塊的新鮮度，初值為隨機(jī)數(shù)，用于數(shù)據(jù)的加解密，在對(duì)存儲(chǔ)塊的每次讀操作后其值加 1；PdpG[8]、PdpA[8]和 PdpH[8]與驗(yàn)證 數(shù)據(jù)的持有性有關(guān)，參見第3節(jié)。

數(shù)據(jù)表PosMap表示用戶數(shù)據(jù)塊在服務(wù)器中存放的位置映射，每次讀寫數(shù)據(jù)塊時(shí)均需對(duì)該表進(jìn)行修改。該表有3個(gè)域，分別是SaveF、Addr1和Addr2。Addr1和Addr2分別表示一個(gè)數(shù)據(jù)塊在服務(wù)器中的兩個(gè)備份位置，也是數(shù)據(jù)表SerMap的索引。SaveF表示數(shù)據(jù)塊存放在服務(wù)器/本地的標(biāo)識(shí)，當(dāng)其值為0時(shí)，表示數(shù)據(jù)塊的兩個(gè)備份都在服務(wù)器中存放；當(dāng)其值為1或2時(shí)，表示數(shù)據(jù)塊在BufM中，且一個(gè)備份在服務(wù)器上 （SaveF=1時(shí)，Addr2有效，SaveF=2時(shí)，Addr1有效）；當(dāng)其值為3時(shí)，表示數(shù)據(jù)塊同時(shí)在BufM和BufA中，且服務(wù)器中的備份失效。

4 數(shù)據(jù)可持有性證明

4.1 同態(tài)散列算法

本文借鑒參考文獻(xiàn)[9]選擇同態(tài)散列算法驗(yàn)證數(shù)據(jù)的持有性。假設(shè)在存儲(chǔ)塊大小為128 KB的空間中隨機(jī)選取8個(gè)片段，每個(gè)片段4 KB。用1 024×8矩陣表示8個(gè)片段則為：

其中 bi=(bi,0,bi,1,…,bi,1023)(0≤i≤7）表示片段，bi,j∈Zp（0≤i≤7,0≤j≤1 023），Zp是以足夠大的正素?cái)?shù) p 為模的有限域，兩個(gè)片段相加規(guī)則定義為：

同態(tài)散列計(jì)算過程如下。

（1）計(jì)算每個(gè)片段的散列值

其中，g=（g0,g1,…,g7）是 1×8 的向量，gi∈Zp（0≤i≤7）。

（2）所有片段的散列值構(gòu)成一個(gè)1×8的向量h

（3）散列同態(tài)性質(zhì)

4.2 數(shù)據(jù)持有性證明

在存儲(chǔ)數(shù)據(jù)塊時(shí)，先對(duì)數(shù)據(jù)塊進(jìn)行加密處理后，隨機(jī)產(chǎn)生向量g,在數(shù)據(jù)塊中任意選擇8個(gè)位置a（數(shù)據(jù)片段的起始位置），并計(jì)算各片段的散列值h。最后將g、a和h分別保存到 SerMap表中的 PdpG[8]、PdpA[8]和 PdpH[8]數(shù)組中。

可以選擇3種方法對(duì)數(shù)據(jù)進(jìn)行持有性證明：客戶自己審計(jì)；服務(wù)器審計(jì)；第三方審計(jì)。以服務(wù)器審計(jì)為例介紹審計(jì)步驟。

算法1 審計(jì)算法 Boolean Audit（M）

輸入：M，對(duì)服務(wù)器中M個(gè)數(shù)據(jù)塊進(jìn)行驗(yàn)證

輸出：布爾值，若為真則表示審計(jì)通過，否則失敗

Boolean Audit（M）

（1）for（i=0;i

（2）u=RandBlock（）;//隨機(jī)選擇一個(gè)存儲(chǔ)塊號(hào)

（3） Addr1=SerMap[u].PdpA[Rand（）];//在 SerMap[u]表項(xiàng)中隨機(jī)選擇一個(gè)片段的起止

（4） Addr2=SerMap[u].PdpA[Rand（）];//在 SerMap[u]表項(xiàng)中隨機(jī)選擇另一個(gè)片段的起止

（5） value=Challenge（u/S,u%S,//對(duì)云存儲(chǔ)文件[u/S]中的第u%S塊進(jìn)行質(zhì)詢

SerMap[u].PdpG,Addr1,Addr2）;//向量 g和兩個(gè)片段地址

（6） if （value!=SerMap[u].PdpH.Addr1*SerMap[u].PdpH.Addr2）{//判斷驗(yàn)證是否失敗

（7） Alert（u,“Bad”）;//失敗時(shí)，發(fā)出警報(bào)

（8） return false;}

（9）}

（10）return true//驗(yàn)證成功，返回

算法1隨機(jī)選擇M個(gè)存儲(chǔ)塊進(jìn)行驗(yàn)證，由質(zhì)詢函數(shù)Challenge（）向服務(wù)器提出質(zhì)詢，服務(wù)器根據(jù)提供的參數(shù)計(jì)算兩個(gè)片段之和的散列值，并返回該值。如果該值與本地儲(chǔ)存的兩個(gè)片段的散列值之乘積相等則說明數(shù)據(jù)是完整的，驗(yàn)證成功。否則，說明數(shù)據(jù)塊已遭到破壞，需要報(bào)警處理并從另一個(gè)備份中恢復(fù)數(shù)據(jù)。

每次審計(jì)均隨機(jī)選擇M個(gè)數(shù)據(jù)塊進(jìn)行驗(yàn)證，而N遠(yuǎn)大于M，所以，每次審計(jì)時(shí)選擇相同序列的數(shù)據(jù)塊的概率極小，并且，在驗(yàn)證某一個(gè)數(shù)據(jù)塊時(shí)僅向服務(wù)器提供向量a中的任意兩個(gè)地址，服務(wù)器無法一次獲取a中的所有地址。另外，在ORAM模型中，所訪問過的存儲(chǔ)塊將會(huì)動(dòng)態(tài)地遷移到新的位置，需要重新計(jì)算該塊的向量g和a，因此，服務(wù)器很難偽造各存儲(chǔ)塊的審計(jì)結(jié)果，系統(tǒng)安全性可以得到保障。

5 訪問模式

客戶讀/寫數(shù)據(jù)塊只需執(zhí)行LookUp（）即可，通過LookUp（）可以隱藏?cái)?shù)據(jù)的訪問模式。

5.1 LookUp算法

算法 2 void LookUp（op,u,data）

輸入：op，表示客戶對(duì)服務(wù)器的訪問操作，read/write

u,表示客戶需要訪問的數(shù)據(jù)塊

data,客戶數(shù)據(jù)存儲(chǔ)地址

輸出：無

void LookUp（op,u,data）

（1）RandRead（data）;//隨機(jī)從服務(wù)器讀一個(gè)數(shù)據(jù)塊，并存放到BufA中

（2）RandRead（DUMMY）;//隨機(jī)讀一個(gè)啞元塊，并存放到BufA中

（3）if（ExistBuf（u））{//如果 u 已在 BufM/BufA 中

（4）RandRead （DUMMY）;//則隨機(jī)讀一個(gè)啞元塊，并存放到BufA中

（5）RemoveBuf（u）;//將u從 BufA/BufM 移出

（6）}else Read（u）;//否則讀指定的數(shù)據(jù)塊u

（7）if（op==write）{//如果是寫操作

（8）copy（data,u）;//將數(shù)據(jù)復(fù)制到u中，修改 PosMap中第u表項(xiàng)中的 SaveF為 3；//并將 Addr1、Addr2所指SerMap對(duì)應(yīng)項(xiàng)中的FlagD設(shè)置為0。

（9）copy（data,BufA）;將 data 復(fù)制到 BufA 中的一個(gè)緩沖區(qū)中，以備寫入云存儲(chǔ)中

（10）}else copy（u,data）;

（11）EnterBufM（u）;//將 u插入 BufM 的隊(duì)尾

（12）RandRead（DATA）;//隨機(jī)從服務(wù)器讀取一個(gè)客戶數(shù)據(jù)塊，并存放到BufA中

（13）RandRead （DUMMY）;//隨機(jī)讀一個(gè)啞元塊，并存放到BufA中

（14）Update（）;//將數(shù)據(jù)塊和啞元塊寫入服務(wù)器

（15）return

在該算法中步驟（1）和步驟（11）任意讀兩個(gè)客戶數(shù)據(jù)塊，步驟（2）和步驟（12）任意讀兩個(gè)啞元塊。當(dāng)所需要訪問的數(shù)據(jù)塊不在BufM或BufA中時(shí)，則讀取并放到BufM的隊(duì)尾，否則隨機(jī)讀一個(gè)啞元塊，并將數(shù)據(jù)塊從BufM或BufA中移出再插入BufM的隊(duì)尾。

當(dāng)op是寫操作時(shí)，則將內(nèi)容寫入u緩沖區(qū)中 （步驟（8）），并將一個(gè)備份存放到 BufA（步驟（9））中。步驟（14）將BufA中的存儲(chǔ)塊寫回服務(wù)器，實(shí)現(xiàn)數(shù)據(jù)的更新。

RandRead（）可隨機(jī)讀取一個(gè)數(shù)據(jù)塊/啞元塊，Read（u）讀取指定的數(shù)據(jù)塊u，在讀數(shù)據(jù)塊或啞元塊后，需要調(diào)整兩張數(shù)據(jù)表PosMap和SerMap的相關(guān)內(nèi)容，并且，每讀一個(gè)存儲(chǔ)塊，都可以選擇使用驗(yàn)證數(shù)據(jù)的可持有性。

5.2 Update算法

在Update算法中，當(dāng)BufM已滿時(shí)，則將最久未用的數(shù)據(jù)塊移入BufA中，以保證在每次執(zhí)行LookUp操作之前，BufM中最少有一個(gè)緩沖區(qū)是空的。在執(zhí)行LookUp操作時(shí)，最多有6個(gè)數(shù)據(jù)塊/啞元塊進(jìn)入BufA中，可能是3個(gè)數(shù)據(jù)塊和3個(gè)啞元塊的組合，也可能是4個(gè)數(shù)據(jù)塊和2個(gè)啞元塊的組合；最多有1個(gè)數(shù)據(jù)塊進(jìn)入BufM中。Update只將BufA中的內(nèi)容寫入服務(wù)器。Update算法描述如下。

算法3 淘汰數(shù)據(jù)塊算法void Update(void)

void Update(void)

（1）if（BufM滿）將最久未用緩沖區(qū)數(shù)據(jù)移到BufA中；

（2）if（BufA 未滿）以啞元塊填滿；

（3）for（i=0;i<6;i++）給 BufA 中的每一個(gè)緩沖區(qū)隨機(jī)分配一個(gè)標(biāo)簽；

（4）對(duì)BufA中的緩沖區(qū)按標(biāo)簽值大小排序，形成一個(gè)新的緩沖序列；

（5）for（i=0;i<6;i++）{//為 BufA 中的 6個(gè)數(shù)據(jù)塊/啞元塊尋找存儲(chǔ)位置

（6）在SerMap中隨機(jī)找一個(gè)最近未被訪問過的啞元塊x，即FlagA值為0的啞元塊，若FlagA值為1時(shí)，將其值設(shè)置為0，繼續(xù)隨機(jī)查找下一個(gè)啞元塊；

（7）if（BufA[i]是數(shù)據(jù)塊）

設(shè)BufA[i]對(duì)應(yīng)的數(shù)據(jù)塊號(hào)為u,訪問PosMap中第u表項(xiàng)，若SaveF的值為 1或2，則用有效項(xiàng)Addr2或Addr1減去x，若其值的絕對(duì)值小于S，則轉(zhuǎn)到步驟（6）重新選擇啞元塊x，此步可保證客戶數(shù)據(jù)塊的兩個(gè)備份存放在不同的文件中；否則，若 SaveF的值為 3，則修改 Addr1或 Addr2為x,且修改SaveF為1或2；否則，修改Addr1或Addr2為x,且修改SaveF為0；

（8）加密，產(chǎn)生向量g及隨機(jī)選取片段地址a，計(jì)算其散列值，然后將數(shù)據(jù)塊寫入文件[x/S]的第[x%S]塊中，修改SerMap中第x表項(xiàng)中的FlagD為1，F(xiàn)lagA為1，將向量g、片段的起止地址a及其散列值存入相應(yīng)位置；}

（9）return

5.3 性能與安全分析

假定一個(gè)存儲(chǔ)塊大小為128 KB，需要服務(wù)器的存儲(chǔ)容量是實(shí)際數(shù)據(jù)量的4倍，當(dāng)數(shù)據(jù)文件很大時(shí)，客戶端數(shù)據(jù)結(jié)構(gòu)所需容量是服務(wù)器存儲(chǔ)容量的0.07%左右。客戶每訪問一個(gè)數(shù)據(jù)塊，均需要讀/寫11塊服務(wù)器的存儲(chǔ)塊，其中讀5次寫6次。

安全定義[11]：設(shè) y=（（op1,u1,data1）,（op2,u2,data2）,…，（opM,uM,dataM））是客戶請求訪問某一數(shù)據(jù)塊時(shí)ORAM訪問服務(wù)器存儲(chǔ)塊的一個(gè)序列，其長度為M。其中op表示R（讀）或W（寫）操作，u表示服務(wù)器虛擬存儲(chǔ)地址，data表示客戶存儲(chǔ)器地址，當(dāng)op為read操作時(shí)，data指從服務(wù)器讀取的數(shù)據(jù)存放在客戶端的地址，當(dāng)op為write操作時(shí)，data指寫往服務(wù)器的數(shù)據(jù)在客戶端存放的地址。用A（y）=（op1,op2,…,opM）表示客戶訪問服務(wù)器的操作序列。如果對(duì)于任何兩個(gè)客戶訪問序列y和y’，只要其長度相等，訪問服務(wù)器的操作序列一樣，對(duì)任何人（除客戶本人）來說 A（y）和 A（y’）都是在計(jì)算上不可區(qū)分的，則稱該ORAM結(jié)構(gòu)是安全的。

本文客戶訪問服務(wù)器的操作序列是A（y11）=（R1,R2,R3,R4,R5,W6,W7,W8,W9,W10,W11）,客戶不論是讀還是寫數(shù)據(jù)塊，其訪問服務(wù)器的操作均為A（y11），因此，本文所提ORAM結(jié)構(gòu)是安全的。

在LookUp算法中，數(shù)據(jù)塊u在服務(wù)器上的存儲(chǔ)位置是隨機(jī)分布的，讀取u和4次隨機(jī)讀服務(wù)器存儲(chǔ)操作混在一起，敵手很難辨認(rèn)哪一塊是客戶需要的，并且敵手很難知道下一次它將存放在哪一個(gè)位置。在訪問服務(wù)器的過程中不會(huì)出現(xiàn)剛被存儲(chǔ)到服務(wù)器上的數(shù)據(jù)塊又要被訪問的現(xiàn)象。因?yàn)椋總€(gè)數(shù)據(jù)塊都有兩個(gè)備份，如果在訪問中發(fā)現(xiàn)所訪問的數(shù)據(jù)塊是剛剛寫入服務(wù)器的數(shù)據(jù)塊，則可以通過訪問該數(shù)據(jù)塊的另一個(gè)備份來獲取數(shù)據(jù)塊。因此，敵手無法從訪問服務(wù)器的序列中獲取有用的信息，系統(tǒng)是安全的。

6 結(jié)束語

本文提出的常量級(jí)訪問模式僅需占用線性級(jí)服務(wù)器存儲(chǔ)容量，實(shí)現(xiàn)無關(guān)訪問服務(wù)器。將大的文件分割成小文件存放，每個(gè)數(shù)據(jù)塊都有兩個(gè)備份，且存放在不同的文件中，使得數(shù)據(jù)的可恢復(fù)性得到保障。利用同態(tài)散列算法實(shí)現(xiàn)數(shù)據(jù)可持有性證明。但該方法需要占用客戶端存儲(chǔ)空間，當(dāng)數(shù)據(jù)文件超大時(shí)，所需客戶存儲(chǔ)空間也隨著增大，因此，需要進(jìn)一步探索減少客戶端存儲(chǔ)空間的使用量。

1 Wang C,Ren K,Lou W J,et al.Toward publicly auditable secure cloud data storage services.IEEE Network,2010,24（ 4）:19～24

2 李紅衛(wèi),古春生,白鳳娥.安全訪問外包數(shù)據(jù)的研究.電子技術(shù)應(yīng)用,2013,39（7）:54～56

3 Uels A,Kaliski B S.Pors:proofs of retrievability for large files.Proceedings of the 14th ACM Conference on Computer and Communications Security,Alexandria,USA,2007:584～597

4 Ateniese G,Burns R,Curtmolar R,etal.Provable data possession at untrusted stores.Proceedings of the 14th ACM Conference on Computer and Communications Security，Alexandria,USA,2007:598～609

5 Shacham H,Waters B.Compact Proofs of Retrievability.Proceedings of Asiacrypt’08,Melbourne,Australia,2008

6 Dodis Y,Vadhan S P,Wichs D.Proofs of retrievability via hardness amplitication.Proceedings of the 6th Theory of Cryptography Conference,San Francisco,2009:109～127

7 朱巖,王懷習(xí),胡澤行等.數(shù)據(jù)可恢復(fù)性的零知識(shí)證明.中國科學(xué):信息科學(xué),2011,41(10):1227～1237

8 梁彪,曹宇佶,秦中元等.云計(jì)算下的數(shù)據(jù)存儲(chǔ)安全可證明性綜述.計(jì)算機(jī)應(yīng)用研究,2012,29（7）:2416～2421

9 陳蘭香.一種基于同態(tài)Hash的數(shù)據(jù)持有性證明方法.電子與信息學(xué)報(bào),2011,33（9）:2199～2204

10 Goldreich O,Ostrovsky R.Software protection and simulation on oblivious RAMs.Journal of the ACM,1996,43（3）:431～473

11 Elaine S T H,Chan H,Stefanov E,et al.Oblivious RAM with O（（logn）3） worst-case cost.Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security,Seoul,South Korea,2011

12 Pinkas B,Reinman T.Oblivious ram revisited.Proceedings of CRYPTO,California,USA,2010

13 Goldreich O.Towards a theory of software protection and simulation by oblivious RAMs.Proceedings of STOC 1987,New York,1987

14 Damgard I,Meldgaard S,Nielsen J B.Perfectly secure oblivious RAM without random oracles.Proceedings of TCC 2011,Rhode Island,USA,2011

15 Goodrich M T,Mitzenmacher M.Privacy-preserving access of outsourced data via oblivious ram simulation. Automata,Languages and Programming,2011(5)

16 Kushilevitz E,Lu S,Ostrovsky R.On the（in） security of hash-based oblivious ram and a new balancing scheme.Proceedings of SODA,Kyoto Japan,2012