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」一起探讨学术问题！~~一起进步，一起成长！