ORAM简介

ORAM(Oblivious Random Access Machine，茫然随机访问机)是一种可以用来完全隐藏IO操作的数据访问模式的加密方案。访问模式是指IO操作访问文件的顺序、访问文件的频率、读写顺序等，当用户把数据存储在不可信的第三方时，即使数据是加密的，第三方仍能通过收集用户访问模式信息推断出用户隐私，在ORAM方案中，若两次访问序列长度相同，则其访问模式是相同的，使得第三方无法通过访问模式获取用户隐私。简单来说，ORAM将用户的一个文件访问请求转换成多个文件访问请求，从而模糊化用户访问文件的概率、模式等信息。目前ORAM研究较多的领域是云存储安全。

随着大数据和数据挖掘技术的发展，云计算环境中用户访问模式成为泄露用户隐私的一种途径[1]，用户将数据存储在第三方，通过向第三方发送关键词访问文件，即使文件是加密的，结合一些背景知识，第三方仍能根据用户请求的关键词在文件中出现的概率来推断关键词的内容，从而获取用户隐私。

ORAM通过访问与关键词无关的文件来破坏概率与关键词的关联，混淆访问模式，从而保护用户隐私。

一般假设存储用户数据的第三方是诚实但是好奇的（honest but curious，HbC），第三方可靠存储用户数据，并诚实响应用户数据请求，但是会尽可能收集用户访问数据的信息，利用这些信息获取用户隐私。发布数据的用户是可信的。

一个IO操作序列被定义为如下形式：((op1, arg1), (op2, arg2), …, (opn, argn))，其中opi（i=1,2…n）表示读或者写操作，argi为访问文件的地址和一个数据值，x和y是两个长度相同的IO操作序列，即|x| = |y|，A(x)和A(y)分别对应x和y在第三方存储上的操作序列，对于除了用户自己外的任何人，这两个操作都是计算上难以区分的，就说这个ORAM方案是茫然的（oblivious）[2]。

ORAM保证以下信息不会被泄露：（1）哪个数据被访问；（2）数据有多旧（数据最近一次被访问的时间）；（3）两次访问操作是否访问的是相同的数据（关联性）；（4）访问模式；（5）访问是读操作还是写操作。

ORAM由Goldreich和Ostrovsky在1996首次提出[2]，包括平方根ORAM（Square Root ORAM）和分层ORAM(Hierarchical ORAM)方案，随后有学者相继提出了分区ORAM(Partition ORAM)[3]，路径ORAM(Path ORAM)[4]，环ORAM(Ring ORAM)[5]，洋葱ORAM(Onion ORAM)[6]等。最初的ORAM是基于软件保护的背景，但随着云存储的流行以及云存储带来的用户隐私泄露问题，越来越多的学者将ORAM应用到云存储上保护用户隐私。

ORAM单用户模式不适合云存储的多用户访问场景，因此当前有很多关于ORAM多用户场景的研究，ORAM的性能提高也是一个研究热点，此外ORAM访问控制、数据完整性保护等也是研究点。

如下图所示，Path ORAM将用户存储在第三方的数据组织为树的形式，用户每个访问请求都是从树中读取一条路径（path）。Path ORAM将IO复杂度降到了O(logN)，大大提高了ORAM性能，是目前使用较为广泛的ORAM原型，下面将详细介绍Path ORAM。

桶（Bucket）和块（Block）：用户以块的形式将文件存储在第三方，每个块大小固定。树的节点称为桶，每个桶包含相同且固定个数的块，当用户存储的块不能填满桶的时候，桶中填充虚块（dummy block），每个block至少包含三个字段：唯一标识，叶子ID，数据，用户通过唯一标识检索块，叶子ID标记该块属于哪条路径，例如叶子ID为1时，要访问该块，需要将从根节点到叶子1的那条路径上所有桶读取到本地，然后通过唯一标识找到该块，数据是用户真正要存储的数据。

路径映射（position map）：叶子节点标记树中每条从根节点到叶子节点的路径，每个块都被随机分配一个叶子节点，表示该块位于该条路径上。块和叶子节点的映射关系被记录到position map上，position map存储在用户端，每次访问完一个块后，都要给该块重新随机分配一个叶子节点，使得每次访问相同的块时的访问位置不同。

隐私存储（stash）：stash是用户本地可信存储，用户每次从第三方读取一条完整的路径，都将路径中所有的块存储在stash中，然后扫描stash找到自己所需的块，更新该块的叶子ID，如果是写操作，更新块的数据，然后将stash中的块写回到当前读取的路径中。

具体流程：

用户要请求获取标识为i的块，首先在本地position map中找到i对应的叶子ID为pos，给i随机分配一个叶子ID并更新到position map中，然后向存储数据的第三方请求获取pos路径；

第三方收到请求后，将从根节点到ID为pos的叶子节点之间（包括根节点和叶子节点）所有的桶发送给用户；

用户收到桶后，将桶中的所有块写入到本地stash，扫描stash，找到标识为i的块，读取数据，然后更新该块的叶子ID，如果是写操作，更新块中的数据；

用户将stash中能够写回当前路径的块放入合适的桶中，如果桶未被填满，使用虚块填充，然后将所有的桶写回到第三方存储的树的pos路径中，不能写回的块将留在stash中。

ORAM目前还处于科研阶段，没有实际应用，因其性能瓶颈和存储的额外开销。以Path ORAM为例，用户访问一个文件，常规访问开销为O(1)，但是Path ORAM中用户需要获取一条path，带宽为O(logN)，而且Path ORAM需要存储额外的dummy block。但是ORAM在保护用户隐私方面还是有积极作用的。

[1] M. S. Islam, M. Kuzu, M. Kantarcioglu．Access pattern disclosure on searchable encryption: Ramification, attack and mitigation：Ndss，2012：vol. 20, 2012, p. 12．

[2] O. Goldreich, R. Ostrovsky．Software protection and simulation on oblivious rams：Journal of the ACM (JACM)，1996：vol. 43, no. 3, pp. 431–473．

[3] Emil Stefanov, Elaine Shi, Dawn Song．Towards practical oblivious RAM：arXiv preprint arXiv，2011．

[4] E. Stefanov, M. Van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, S. Devadas．Path oram: an extremely simple oblivious ram protocol：Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security，2013：pp. 299–310．

[5] Ren L, Fletcher C, Kwon A．Constants count: practical improvements to oblivious RAM：Usenix Conference on Security Symposium，2015：415-430．

[6] Devadas S, Dijk M V, Fletcher C W．nion ORAM: A Constant Bandwidth Blowup Oblivious RAM：Theory of Cryptography Conference，2016：145-174．