ORAM被譽為保護訪問模式中最有前途的密碼協議之一，其餘的保護訪問模式也有Private Information Retrieval（PIR）和Oblivious Transfer（OT）兩種密碼協議等。但ORAM不僅可以保護訪問模式，還有更新數據功能，現在還在研究增加和刪除數據塊的功能，這是其他保護訪問模式的密碼協議所不具備的。

既然我們說其功能是保護訪問模式，那我們首先肯定想知道啥是訪問模式呢？在ORAM的發明者Goldreich和Ostrovsky的論文中是這樣定義的，將一個訪問序列引起的訪問行為稱為訪問模式。接著就是定義ORAM的安全性，便是：兩個相同長度的訪問序列引起的訪問模式是不可區分的，則ORAM協議是安全的。訪問模式泄露的危害也有專門的研究者在網路與信息安全的四大頂級會議上發表，如2012年NDSS上的paper，此研究結果表明在可搜索加密中藉助訪問模式泄露可以導致敵手能推斷出近80%的密文關鍵詞對應的明文關鍵詞。

ORAM協議用途非常廣泛，可以應用在保護訪問模式的諸多應用中，如前面提到的可搜索加密，還有外包的安全雲存儲，安全處理器的構造，安全多方計算，動態的數據審計協議等場景中。

說完ORAM的功能，定義和安全性之後，下面我們說說ORAM的研究現狀。1987年Goldreich，1990年Ostrovsky，以及1996年Goldreich與Ostrovsky合作一起完善了ORAM的定義，並給出了兩種ORAM的經典構造，分別是平方根-ORAM和分層結構的ORAM，兩種方案都因為最差情況下的bandwidth blowup過大而沉寂了很多年，雖然也有些許優化，但改變不了最差情況下代價過大的硬傷，這會導致周期性的大延遲。他們的工作還證明了ORAM在標準模型下（Server僅僅是個簡單的存取設備，無計算能力）的G-O lower bound：O(1) Client Storage條件下至少有O(log N) bandwidth blowup。這裡解釋下bandwidth blowup指的是Client為了訪問（read或write）一個目標數據塊，而與Server交互所需要的數據塊的數目（這個方向在今年2018年連續出了兩篇頂會文章，分別是2018Crypto和2018FOCS，這個方向偏重於純理論的構造方案，已經距離1996年過去了22年，可見此基礎理論突破的難度，而且也僅僅是構造了一個接近此下界的ORAM協議，還有很多需要改進的地方）。

至此之後，bandwidth blowup一直就成為ORAM研究者們儘力優化的目標，很多學者卻忽視了bandwidth blowup只是組成Client與Server之間帶寬的一部分，卻忘了還有一個因素也不容忽視，那就是數據塊的大小（in bits），因為bandwidth cost=banwidth blowup*block size。目前client與server之間的帶寬代價是主要的瓶頸之一，這是研究們都花大力氣在優化bandwidth blowup上的主要原因。

自從2011年AsiaCrypt（三大密碼頂會之一）提出了一種優化的基於二叉樹的ORAM方案，再接著2013年CCS上提出的Path-ORAM方案作為種子級別的工作點燃了整個ORAM研究者們的熱潮，之後每年在網路與信息安全的四大頂會（CCS、S&P、USENIX Security、NDSS）上都有文章而且不少是best paper。這四大頂會上的ORAM方案更加關注於ORAM的實用性能而不是asymptotic cost（可以理解為理論上的代價），有些方案增加少量的client storage來換取bandwidth blowup的降低，有些方案增加server computation來換取bandwidth blowup的降低，還有些方案引入多個servers嚴重增加Server Storage來換取bandwidth blowup的降低，總之都是朝著降低bandwidth blowup的目標進行優化ORAM的性能的。在這些方案當中有些極端的方案就是將bandwidth blowup降低到O(1)，但ORAM的其他代價卻高的離譜，比如有些採用同態加密優化ORAM的，但計算代價太大會使得ORAM請求的時間延遲太大，因此脫離了實用；有些增加Client Storage=O(根號N) blocks來降低bandwidth blowup，這種方案不利於採用在主流的智能設備如手機，iPad等終端上；還有些採用簡單計算但必須多個Servers同時參與到方案中，每個Server都必須存儲一份Server Storage，Server Storage在每個server上本來就較大，如果採用多個servers將導致總的Server Storage太大而使用戶花銷過高，因此也脫離了實用。

目前來說，最實用ORAM方案依然是2013年ccs上的種子級別的工作Path-ORAM方案以及其後面對其改進的2015年USENIX Security上的Ring ORAM，最實用的ORAM方案一定是ORAM的各種性能代價達到比較均衡的方案。最後期待自己能在這個領域內繼續耕耘，早日也能在計算機頂會上發個paper！

PS：歡迎志同道合的各位朋友們加「微信號g2551008365」一起探討學術問題！~~一起進步，一起成長！