隨著云存儲(chǔ)技術(shù)的發(fā)展，越來(lái)越多的客戶(hù)將數(shù)據(jù)存儲(chǔ)在云服務(wù)器上，數(shù)據(jù)的安全也越來(lái)越受到重視。數(shù)據(jù)加密技術(shù)可以保護(hù)數(shù)據(jù)的內(nèi)容，但無(wú)法隱藏客戶(hù)對(duì)數(shù)據(jù)的訪(fǎng)問(wèn)模式，攻擊者通過(guò)分析數(shù)據(jù)的訪(fǎng)問(wèn)模式可能獲得存儲(chǔ)數(shù)據(jù)的信息。例如，攻擊者獲知醫(yī)生在診斷患者患有某種疾病時(shí)需要訪(fǎng)問(wèn)某些記錄，當(dāng)某人就診時(shí)，醫(yī)生對(duì)這些記錄進(jìn)行了訪(fǎng)問(wèn)，攻擊者即可推斷出該人患有某種疾病。為了保護(hù)客戶(hù)的隱私，需要隱藏客戶(hù)對(duì)存儲(chǔ)系統(tǒng)的訪(fǎng)問(wèn)模式，實(shí)現(xiàn)數(shù)據(jù)訪(fǎng)問(wèn)的無(wú)關(guān)性(obliviousness)。所謂數(shù)據(jù)訪(fǎng)問(wèn)的無(wú)關(guān)性是指對(duì)任意兩次數(shù)據(jù)訪(fǎng)問(wèn)(不管是讀還是寫(xiě))，所訪(fǎng)問(wèn)的存儲(chǔ)位置的序列是等同的[1]。一種最簡(jiǎn)單的解決方法就是每訪(fǎng)問(wèn)一個(gè)數(shù)據(jù)時(shí)讀寫(xiě)所有數(shù)據(jù)。每讀一個(gè)數(shù)據(jù)時(shí)先解密，寫(xiě)回時(shí)再加密，每次加密所用的密鑰均不相同，使得攻擊者無(wú)法識(shí)別寫(xiě)回的數(shù)據(jù)是原數(shù)據(jù)還是修改后的數(shù)據(jù)。但該方法的代價(jià)太大，因此，GOLDREICH O提出了無(wú)關(guān)RAM模型機(jī)(Oblivious RAM，簡(jiǎn)稱(chēng)O-RAM)[2]并解決這一問(wèn)題。隨著云計(jì)算的飛速發(fā)展，在數(shù)據(jù)外包中O-RAM的應(yīng)用有著重要作用。

1 相關(guān)研究
    參考文獻(xiàn)[1]提出最有效的隱藏訪(fǎng)問(wèn)模式是采用分層結(jié)構(gòu)算法。在分層結(jié)構(gòu)算法中，如果洗牌算法采用AKS網(wǎng)絡(luò)排序[3]算法，則平均時(shí)間復(fù)雜度為O(clog4N)，其常數(shù)項(xiàng)c大約為6 000。當(dāng)采用巴切排序網(wǎng)絡(luò)算法[4]時(shí)平均時(shí)間復(fù)雜度為O(clog4N)，其常數(shù)項(xiàng)c大小較為合理[5]。

    以上所提算法均由兩個(gè)階段構(gòu)成，即訪(fǎng)問(wèn)階段和洗牌階段，算法的瓶頸就在洗牌階段。在洗牌時(shí)，客戶(hù)與服務(wù)器之間需要進(jìn)行大量的數(shù)據(jù)交換，使得客戶(hù)無(wú)法忍受洗牌過(guò)程占用的大量時(shí)間。如果能把洗牌過(guò)程分解到每次訪(fǎng)問(wèn)操作中，對(duì)服務(wù)器的訪(fǎng)問(wèn)時(shí)間保持在常數(shù)量級(jí)，這樣就能將理論應(yīng)用于實(shí)踐中。因此，本文提出一種新的結(jié)構(gòu)，在需要少量客戶(hù)端存儲(chǔ)空間和線(xiàn)性級(jí)服務(wù)器存儲(chǔ)容量的情況下，使得每次操作的代價(jià)為O(1)。典型算法的性能比較[9]如表1所示。

2 常量級(jí)訪(fǎng)問(wèn)模式
    本文假設(shè)客戶(hù)端可信而服務(wù)器端不可信。O-RAM的目標(biāo)就是對(duì)服務(wù)器完全隱藏?cái)?shù)據(jù)訪(fǎng)問(wèn)模式，即從服務(wù)器角度觀察，客戶(hù)端每次讀或?qū)憯?shù)據(jù)塊請(qǐng)求將產(chǎn)生一個(gè)完全隨機(jī)的數(shù)據(jù)訪(fǎng)問(wèn)序列。
2.1 數(shù)據(jù)結(jié)構(gòu)
    假設(shè)客戶(hù)的數(shù)據(jù)大小為N塊，每塊大小為L(zhǎng)字節(jié)，在云存儲(chǔ)中，L的典型值一般為64 KB～256 KB。本方案需要占用服務(wù)器存儲(chǔ)容量為3N塊，利用均勻隨機(jī)函數(shù)將N個(gè)數(shù)據(jù)塊均勻隨機(jī)地分布到3N個(gè)存儲(chǔ)塊中，其余2N個(gè)存儲(chǔ)塊存放啞元塊。
    在客戶(hù)端設(shè)置一個(gè)緩存隊(duì)列Q、兩張數(shù)據(jù)表SerMap和PosMap。
    緩存隊(duì)列Q用來(lái)管理從服務(wù)器讀取的數(shù)據(jù)塊，本文假定最多可存儲(chǔ)32個(gè)數(shù)據(jù)塊。對(duì)緩存隊(duì)列的操作有：Q.in(b)將數(shù)據(jù)塊b插入隊(duì)尾；Q.out()從隊(duì)首移出數(shù)據(jù)塊；Q.remove(b)將數(shù)據(jù)塊b從緩存隊(duì)列中移出；Q.getLen()返回緩存隊(duì)列中存放的數(shù)據(jù)塊數(shù)；Q.getSit(b)返回?cái)?shù)據(jù)塊b在緩存隊(duì)列中的位置；Q.getSitF()返回隊(duì)首數(shù)據(jù)塊的塊號(hào)。
    SerMap[3N]用來(lái)表示存儲(chǔ)在服務(wù)器上各數(shù)據(jù)塊的存儲(chǔ)位置，它有3個(gè)域，分別是FlData、FlAcc和Fresh。FlData表示存儲(chǔ)類(lèi)型，其值為1表示該塊為數(shù)據(jù)塊，否則為啞元塊；FlAcc表示其對(duì)應(yīng)的存儲(chǔ)塊最近是否被訪(fǎng)問(wèn)過(guò)。當(dāng)讀/寫(xiě)存儲(chǔ)塊后，該變量的值設(shè)置為1。在查找一個(gè)啞元塊時(shí)，若其值為0則選中該塊，若其值為1則改為0，繼續(xù)查找下一個(gè)啞元塊；Fresh表示服務(wù)器存儲(chǔ)塊的新鮮度，在對(duì)服務(wù)器的每次讀操作后都會(huì)使該變量的值增1，以保證相同數(shù)據(jù)在加密后結(jié)果不一樣。
    PosMap[N]用來(lái)表示用戶(hù)數(shù)據(jù)塊在服務(wù)器中存放的位置映射，包括flag和blockAdd兩個(gè)域。flag表示數(shù)據(jù)塊存放在服務(wù)器/本地的標(biāo)志，若其值為1時(shí)，則表示數(shù)據(jù)塊存放在服務(wù)器端，否則存放在Q中；blockAdd指數(shù)據(jù)塊在SerMap/Q中的位置。
2.2 訪(fǎng)問(wèn)模式
    定義1：設(shè)客戶(hù)對(duì)服務(wù)器的操作為(op，u，data)，其中，op表示read(u)或者write(u，data)操作，u表示將要讀或?qū)懙臄?shù)據(jù)塊標(biāo)識(shí)，data表示要寫(xiě)的數(shù)據(jù)塊。
    無(wú)論op是讀操作還是寫(xiě)操作，其訪(fǎng)問(wèn)服務(wù)器的序列由Lookup算法決定。
2.2.1 Lookup算法
    Lookup算法描述如下：
    Lookup(op,u,data*);
        1：Random read n ( n <= 6)
blocks from server;
        2：if (PosMap[u].flag=0) then
{//所讀塊在Q中
        3：ReadDummy();//隨機(jī)
讀一啞元塊
        4：Q.remove(u); Q.in(u);  //將該塊從Q中移出
再插入隊(duì)尾
        5：} else
        6：ReadBlock(u);  //從服務(wù)器端讀數(shù)據(jù)塊u
并插入Q中
        7：Random read 6-n blocks from server;
        8：if (op=write) then
        9：Q.bufs[PosMap[u].blockAdd]&larr;data*;
//將要寫(xiě)的數(shù)據(jù)保存在Q中相應(yīng)的緩沖區(qū)中
        10：Evict( ); //為避免Q溢出，將部分?jǐn)?shù)據(jù)塊
寫(xiě)入服務(wù)器
        11：return (PosMap[u].blockAdd);
    在該算法中第1行和第7行共讀服務(wù)器6次，其中隨機(jī)讀取2個(gè)數(shù)據(jù)塊和4個(gè)啞元塊，需要把所讀的數(shù)據(jù)塊保存在Q中。第2行至第6行讀取指定的數(shù)據(jù)塊u并保存在Q中。如果數(shù)據(jù)塊u已在Q中，則隨機(jī)讀一啞元塊。根據(jù)程序局部性原理可知，最近訪(fǎng)問(wèn)的數(shù)據(jù)塊在最近的將來(lái)仍有可能再被訪(fǎng)問(wèn)到，因此對(duì)Q的管理并不按照嚴(yán)格意義上的先進(jìn)先出策略，而是當(dāng)訪(fǎng)問(wèn)的數(shù)據(jù)塊在Q中時(shí)，將該塊從Q中移出并放到隊(duì)尾，以保證從Q中踢出的數(shù)據(jù)塊是不常用的數(shù)據(jù)塊。
    當(dāng)op是寫(xiě)操作時(shí)，將要寫(xiě)的內(nèi)容覆蓋Q中保存數(shù)據(jù)塊u的緩沖區(qū)(第9行)。在每一次Lookup調(diào)用中，不停地有數(shù)據(jù)塊存入Q中，Q總會(huì)變滿(mǎn)，因此需要定期將Q中的數(shù)據(jù)塊寫(xiě)入服務(wù)器以防止Q溢出，第10行是調(diào)用Evict將Q中的最久未用的數(shù)據(jù)塊寫(xiě)入服務(wù)器。
2.2.2 Evict算法
    Q中最多可存放32個(gè)數(shù)據(jù)塊，調(diào)用一次Lookup最多有3個(gè)數(shù)據(jù)塊進(jìn)入Q中。因此，在Evict算法中，當(dāng)Q的長(zhǎng)度超過(guò)29時(shí)，則將超出的數(shù)據(jù)塊寫(xiě)入服務(wù)器以保證Q在下一次Lookup操作時(shí)不會(huì)溢出。Evict算法描述如下：
    Evict( )    //寫(xiě)數(shù)據(jù)塊或啞元塊到服務(wù)器
        1:m&larr;0
        2:while (Q.getLen()>29) do {
        3:WriteBlock(); //將Q中隊(duì)首數(shù)據(jù)塊寫(xiě)入服務(wù)器
        4:m&larr;m+1
        5:}
        6:for i=m+1 to 6 do
        7:WriteDummy( ); //隨機(jī)寫(xiě)啞元塊到服務(wù)器中
        8:return;
    第1行至第5行將數(shù)據(jù)塊寫(xiě)入服務(wù)器。Evict踢出算法每次寫(xiě)6次服務(wù)器，先將緩存隊(duì)列中的數(shù)據(jù)塊寫(xiě)入服務(wù)器，然后用啞元塊補(bǔ)足6塊（第6行至第7行）。
2.3 洗牌
    每執(zhí)行一次Lookup都會(huì)將任意兩個(gè)數(shù)據(jù)塊讀入Q中，當(dāng)Q長(zhǎng)度超過(guò)29時(shí)，就將超出的數(shù)據(jù)塊寫(xiě)到服務(wù)器端的任意位置，實(shí)現(xiàn)洗牌操作，這樣可將整個(gè)洗牌操作分?jǐn)偟矫看蜭ookup中，避免了集中洗牌造成的突發(fā)訪(fǎng)問(wèn)。
2.4 性能
    假定存儲(chǔ)塊大小為64 KB，參考文獻(xiàn)[9]與本文性能對(duì)比如表2所示。當(dāng)數(shù)據(jù)文件小于等于16 TB時(shí)，所用客戶(hù)存儲(chǔ)空間小于參考文獻(xiàn)[9]，當(dāng)數(shù)據(jù)文件大于16 TB時(shí)，所需客戶(hù)存儲(chǔ)量超過(guò)參考文獻(xiàn)[9]。本文算法的優(yōu)勢(shì)在于所需服務(wù)器存儲(chǔ)空間較少，實(shí)際性能恒定。參考文獻(xiàn)[9]采用集中洗牌，當(dāng)洗牌時(shí)需要大量的數(shù)據(jù)交換，當(dāng)客戶(hù)在讀寫(xiě)操作時(shí)，若正好遇上洗牌操作，則需要等待很長(zhǎng)時(shí)間。

2.5 安全
    定義2：設(shè)y=((op1，u1，data1)，(op2，u2，data2)，&hellip;，(opM，uM，dataM))是客戶(hù)請(qǐng)求訪(fǎng)問(wèn)數(shù)據(jù)塊的一個(gè)序列，其長(zhǎng)度為M。設(shè)A(y)表示存取訪(fǎng)問(wèn)模式，當(dāng)客戶(hù)的請(qǐng)求序列是y時(shí)，用A(y)表示存取訪(fǎng)問(wèn)服務(wù)器的序列。如果對(duì)于任何兩個(gè)客戶(hù)訪(fǎng)問(wèn)序列y和y&prime;，只要其長(zhǎng)度相等，對(duì)任何人（除客戶(hù)本人）來(lái)說(shuō)A(y)和A(y&prime;)都是計(jì)算上不可區(qū)分的，則稱(chēng)該O-RAM結(jié)構(gòu)是安全的。
    在Lookup中，數(shù)據(jù)塊u在服務(wù)器上的存儲(chǔ)位置是隨機(jī)分布的，讀取u和6次隨機(jī)讀數(shù)據(jù)塊操作混在一起，攻擊者很難猜到哪一塊是真實(shí)的塊，并且攻擊者很難知道下一次它將存放在哪一個(gè)位置。
    在訪(fǎng)問(wèn)服務(wù)器的過(guò)程中可能出現(xiàn)剛被淘汰出的數(shù)據(jù)塊又要被訪(fǎng)問(wèn)的情況。這種情況下，攻擊者仍然無(wú)法獲取有用的信息，因?yàn)橹辽儆?/3的數(shù)據(jù)塊是隨機(jī)選取讀到Q中的，最多有1/3的數(shù)據(jù)塊是客戶(hù)所讀的數(shù)據(jù)塊，但Evict算法采用最久未用塊淘汰策略，攻擊者無(wú)法知道所讀的塊是否為所需的數(shù)據(jù)塊，也無(wú)法知道什么時(shí)間該塊會(huì)寫(xiě)入服務(wù)器，即攻擊者從被踢出后又要被訪(fǎng)問(wèn)的數(shù)據(jù)塊中無(wú)法獲取有用的信息，因此系統(tǒng)是安全的。
    本文提出的常量級(jí)訪(fǎng)問(wèn)模式僅需占用線(xiàn)性級(jí)服務(wù)器存儲(chǔ)量就可實(shí)現(xiàn)無(wú)關(guān)訪(fǎng)問(wèn)服務(wù)器，但它需要占用客戶(hù)端存儲(chǔ)空間，當(dāng)文件長(zhǎng)度超過(guò)16 TB時(shí)，比參考文獻(xiàn)[9]的算法占用更大的客戶(hù)端存儲(chǔ)空間。下一步工作將在減少占用客戶(hù)端存儲(chǔ)空間方面進(jìn)行研究，找到一個(gè)需求客戶(hù)空間更少的算法。
參考文獻(xiàn)
[1] GOLDREICH O，OSTROVSKY R.Software protection and  simulation on oblivious RAMs[J].Journal of the ACM，1996，43(3)：431-473.
[2] GOLDREICH O.Towards a theory of software protection and  simulation by oblivious RAMs[C].New York：STOC，1987.
[3] AJTAI M，KOLMOS J，SZEMEREDI E.An O(nlogn) sorting  network[C].Boston：STOC，1983.
[4] BATCHER K.Sorting networks and their applications[C]. NJ：AFIPS Spring Joint Computing Conference.1968.
[5] PINKAS B，REINMAN T.Oblivious ram revisited[C].California：CRYPTO.2010.
[6] GOODRICH M T，MITZENMACHER M.  Privacy-preserving access of outsourced data via oblivious ram simulation[J]. Automata，Languagesand Programming，2011(6756)：576-587.
[7] BONEH D，MAZIERES D，POPA R A.Remote oblivious storage：Making oblivious ram practical[EB/OL].[2011-3-30].http：//dspace.mit.edu/bitstream/handle/1721.1/62006/MIT-CSAIL-TR-2011-018.pdf.
[8] STEFANOV E，SHI E，SONG D.Towards practical oblivious ram[C].California:NDSS，2012.
[9] SHI E，CHAN T H H，STEFANOV E，et al.Oblivious RAM with o((logn)3) worst-case cost[C].Seoul：ASIACRYPT，2011.