Oblivious RAM Study

Reference：
https://www.youtube.com/watch?v=jGr7Nj3KJ3c
https://eprint.iacr.org/2011/407.pdf

一、简单了解O-RAM

二、定义与构造

N：一个O-RAM可以存储的最大数量的数据块。我们假设数据以一个叫做block的原子单元进行获取和存储。
B：按照比特的个数表示的block大小。我们假设block的大小B>=c*logN，对于某个c > 1。请注意，这在几乎所有实际场景中都是正确的。我们假设每个block都有一个全局标识符 u ∈ U，其中U表示标识符的集合。

用丰富的操作定义O-RAM

Definition1.
Oblivious RAM是一套客户端和服务器之间的交互协议，包括以下内容：

• ReadAndRemove(u): 给定一个私有输入u∈U(block的标识符)，客户端与服务器执行一个交互协议去检索u标识的block，然后从O-RAM上删除它。如果u标识的block存在于O-RAM中，则block的内容data会返回给客户端。如果不存在，⊥被返回。
• Add(u,data): 客户端被给予私有输入u∈U和data∈{0，1}^B(块标识符和一些数据内容)。该操作必须紧跟着ReadAndRemove(u)执行，以使u标识的block已经不在O-RAM中。之后客户端和服务器执行交互协议，将内容data写入被u标识的block块，data被加到O-RAM中。

Definition2. 安全定义。

• $\vec{y}$：=( (op₁,arg₁),(op₂,arg₂),…,(op_M,arg_M) )表示长度为M的数据请求序列。每个op_i表示一个ReadAndRemove或Add操作。此外，如果op_i是一个ReadAndRemove操作，则arg_i = u_i，如果op_i是一个Add操作，则arg_i = (u_i,data_i)，其中u_i表示正在读取或添加的块的标识符，而data_i表示在第二种情况下正在写入的数据内容。
  tips：如果op_i是带参数(u_i, data_i)的Add操作，那么op_i-1必须是带参数 u_i-1 = u_i 的ReadAndRemove操作。

• 我们使用 ops( $\vec{y}$) 去表示与 $\vec{y}$ 相关的操作序列。即 ops( $\vec{y}$)：=（op₁,op₂,…,op_M）.

• 让 A($\vec{y}$) 表示对于给定的数据请求序列 $\vec{y}$ 去远程存储的访问序列（可能是随机的）。

O-RAM的构造被认为是对任何两个数据请求序列安全的 $\vec{y}$ 和 $\vec{z}$，比如 |$\vec{y}$| = |$\vec{z}$| 和 ops($\vec{y}$) = ops($\vec{z}$)，他们的访问模式 A($\vec{y}$) 和 A($\vec{z}$) 在计算上除了客户端以外的任何人都无法区分。

实现丰富的语义

从ReadAndRemove和Add原语实现Pop操作。 正如前面提到的，我们的O-RAM存储被组织成一个基于bucket的二叉树，其中每个bucket本身就是一个功能完整的ORAM，称为bucket O-RAM。每个bucket O-RAM不仅需要支持ReadAndRemove和Add操作(以及标准的O-RAM Read和Write操作)，还需要支持一个叫做Pop()的特殊用途的操作。
Pop()操作查找一个真实的数据块(real data block)，如果存在的话，就从O-RAM中删除它。否则，它就会返回一个虚拟块( dummy block ⊥)。

加密和认证

我们假设所有的数据块都使用语义安全的加密方案加密，所以同一明文的两个加密不能被链接。此外，每次一个数据块被写回，它都使用新的随机性再次加密。
我们还假设服务器不会篡改或修改数据，因为身份验证和新鲜度可以通过消息验证码、数字签名或经过验证的数据结构这样的标准技术实现。

两个简单的O-RAM结构与确定性保证

我们希望每个bucket O-RAM都能提供确定性的保证。此外，每个bucket O-RAM都需要支持非连续的block标识符空间。我们认为每个block标识符u∈{0，1}^＜B，即u可以是一个任意的字符串，只要u可以在一个block中被描述。此外，block标识符的集合在先前是未知的，而是在bucket O-RAM的有效操作中被动态确定的。

Trivial O-RAM (平凡O-RAM)
我们可以用下面的方法构建一个trivial的O-RAM来支持非连续块标识符空间。设N表示O-RAM容量。在trivial的O-RAM中，服务器端有一个存储N个block的缓冲区，每个block要么是表示为(u, data)的真实块，要么是表示为⊥的虚拟块。
在执行ReadAndRemove(u)操作时，客户端会依次扫描服务器端数组中从0到N−1的位置:如果当前块匹配标识符u，客户端会记住它的内容，并用⊥覆盖它;如果当前块与标识符u不匹配，客户端会写回原始块读。

服务器端存储层次结构

服务器端O-RAM存储被组织成数据桶(data bucket)上的二叉树，每个bucket可以容纳O(log N)个data block。当写入O-RAM时，一个data block从根桶进入，然后随着时间的推移，它会无意识地向下渗透到一个随机的叶中，直到同一个块再次被访问。
要执行Add(u, data)操作，客户端顺序扫描服务器缓冲区的位置0到N−1:客户端第一次看到一个虚拟块，客户端用(u, data)覆盖它;否则，客户端写回原始的块读。
**Note:**显然，普通的O(ram)是安全的，需要O(N)平摊和最坏情况下的代价，O(N)服务器端存储和O(1)客户端存储(因为客户端永远不会一次性下载整个数组，但会以流的方式执行读取和更新)。

Square-Root O-RAM(平方根O-RAM)
Goldreich和Ostrovsky提出了一个平方根O-RAM，它实现了O(√N log N)的平摊代价、O(N log N)的最坏情况代价、O(N)的服务器端存储和O(1)的客户端存储。

三、基础建设

二叉树结构描述

查找数据块。 在给定的时间点，一个数据块block u在逻辑上与叶节点e相关联。为了找到block u，它需要搜索在从叶子bucket e到根bucket的路径上搜索每一个bucket（如图中阴影部分所示）。每当一个block被访问，他将在逻辑上被分配到一个新的随机的叶子节点。

服务器端存储组织。 服务器存储被建立为一个深度D := log₂N的二叉树。为了便于解释，暂时假设N是2的幂。这样，树中就有N个叶节点。树上的每一个节点都是一个data bucket，它是一个容量为O(logN)的自包含O-RAM，因此称为桶O-RAM。由于后面描述的技术原因，每一个bucket O-RAM必须有以下的属性：

• 支持非连续的标识符空间
• 支持ReadAndRemove和Add原语 —— 从这些原语中我们也可以实现之前提到的Read, Write和Pop原语
• 失效概率为零

O-RAM操作
当数据块被写入O-RAM时，它们首先被添加到树的根bucket中。随着更多的数据块block被添加到一个桶bucket中，桶bucket的负载也会增加。为了避免溢出bucket O-RAM的容量，驻留在非叶节点bucket的data block周期性地被驱逐到他的children bucket。
随着时间的推移，每个block将逐渐沿着树中的路径向叶leaf bucket渗透，直到再次读取或写入相同的block。当一个block被添加到根bucket时，它将被逻辑地分配给一个随机的叶桶leaf bucket，索引是一个字符串{0,1}^D。此后，这个数据块将逐渐向下渗透到指定的叶桶leaf bucket，直到相同的数据块block再次被读取或写入。
假设在某一时刻，一个数据块当前逻辑上被分配给叶节点e∈{0,1}D。这意味着在从叶节点到根节点的路径上存在一个数据块block的新副本。要找到该数据块block，只需在指定的叶节点到根节点的路径上搜索所有桶bucket中的数据块block即可。我们假设当数据块block存储在一个bucket中时，我们单独存储标签e，并且用(data|| e)表示block的内容。

驱逐率V=2的背景驱逐。如上图所示，在每个数据访问操作中，对于层次的每个深度，V=2数量的bucket被随机选择并在此期间，一个block(真实的或虚拟的)将被驱逐到它的每个children block。如果bucket被加载(load>1)，那么一个实际block和一个虚拟block被驱逐。如果bucket未装载(load=0)，则将驱逐两个虚拟block。在这个图中，D表示一个虚拟块的驱逐，R表示一个实块的驱逐。

确保安全。 出于安全考虑，请注意以下事项:

• 每次访问一个块时，必须独立随机地选择其指定的叶节点。这对于确保同一个数据块上的两个操作是完全不可链接的是必要的。
• 在驱逐过程中被访问的bucket序列不能显示任何关于每个bucket的装载或数据访问序列的信息。在我们的构造中，哪个bucket中去驱逐的选择是随机选择的，与bucket的负载或数据访问序列无关。此外，每当选择一个bucket进行驱逐时，我们总是写入它的两个children bucket,根据是否存在要驱逐的实块real block，我们将写入一个实块real block或一个虚块dummy block到它的每个children bucket。

Client-side index (客户端索引)：
客户端指数。由于每个数据块在每次操作时都会被逻辑地分配给一个随机的叶节点，所以我们需要一些数据结构来记住每个块在任何时间点的位置。因此，客户端存储的数据结构大小为NlogN/B个block，它记录着当前与每个block相关联的叶子节点。当B>=clogN,这个索引结构的大小是一个O-RAM容量的线性分式。因此，在基本方案中，我们需要N/C个客户端存储，其中c>1.但是，在第4节稍后描述的递归构造中，我们将展示如何在索引结构上递归地应用O-RAM构造来实现O(1)客户端存储。

关于虚拟块和虚拟操作的说明
为了确保O-RAM的安全，我们经常使用虚拟块和虚拟操作对不受信任的服务器隐藏信息。如是否加载了一个bucket、一个block在树的位置。
虚拟块为常规但无用的数据块。我们指定一个特定的标识u=0作为虚拟块。

详细的构造

Algorithms for data access

ReadAndRemove
首先，客户端查找他的本地索引结构index，以找出哪一个叶子节点e与被要求的block u关联。紧接着我们从{0,1}^D生成一个新的随机的e^*，用e^* 将index[u]覆盖，即block u此后与一个新鲜的随机叶节点e^* 相关联。注意，这确保了同一数据块上的两个操作之间没有链接性。为了避免为后面的 Add操作 进行额外的index查找，e^*也被存储在一个全局变量state中。
现在，假设u目前与叶子节点e关联，这意味着block u的一个新副本必须位于沿着叶节点e到根节点路径的某个bucket中，用P(e)表示。如果u在某个bucket中被找到，我们将u从这个bucket中移除，并记住他的数据内容。无论u是否被发现，我们都继续我们的搜索一直到根节点。最后，如果找到了请求的block u, ReadAndRemove算法将返回其数据内容;否则，ReadAndRemove算法返回⊥。

Add
Add(u,data)操作从state中读取e标签，这是由前面的ReadAndRemove(u)操作生成的。客户端将block(u,data||e)写入根bucket。
注意这里的客户端用e标记data，即在block u的下一次操作之前，与block u逻辑关联的叶节点的id。当我们递归地在客户端索引结构上应用O-RAM时，被指定的叶子节点标记变得很重要，如第4节所述。具体来说，==驱逐算法将检查这个指定的叶子节点标记，以确定将这个block驱逐到哪一个children bucket中。==注意，为了在递归构造中保持所需的渐近性，eviction算法不能(递归地)查找索引结构以找到block特指的叶子节点。通过使用指定的叶标记数据，eviction算法不需要对索引结构执行递归查找。
最后，在每个Add操作结束时，客户端调用一次后台驱逐进程。

Background evictions

让v=2表示驱逐率。每当调用背景驱逐算法时，客户端在树的每一个深度随机选择v=2个bucket进行驱逐。
如果一个bucket被选中进行驱逐，客户端通过调用Pop操作从bucket O-RAM中弹出一个block。如果被选中的bucket被加载(读/写)了，那么Pop操作将返回一个真实的bolck，并从bucket的O-RAM中删除该block；否则，Pop操作将返回虚拟block。
不管Pop操作返回的是一个实块还是一个虚块，客户端总是对所选bucket的两个children bucket执行写操作:

1. 如果Pop返回一个虚拟block，客户端只需对两个children bucket执行一个虚拟写操作。
2. 如果返回一个真正的block，客户端检查其指定的叶节点标记，以找出这个block去驱逐到的正确子节点。回想一下，这个指定的叶节点标记是在block第一次写入root bucket时添加的。现在，假设该块被逐出到所选bucket的child bucket b∈{0,1}，客户端将该block写入 child b，并将一个虚拟块写入child bucket1−b。

安全分析

Theorem1： 我们的基本O-RAM结构在定义2的意义上是安全的，假设每个桶O-RAM也是安全的。
每种操作在二叉树中bucket的访问模式上独立地归纳出相同的分布;

• 对于ReadAndRemove(u) 操作，bucket沿着路径P(e)，从根到叶(以e= index(u)为索引的)被访问。观察e是从{0,1}^D均匀随机生成的。因此，被访问的bucket的分布是沿着通往随机叶子的路径上的bucket。此外，每次调用ReadAndRemove(u)时，都会生成一个新的随机的e^*并存储在index(u)中，以便下次调用ReadAndRemove(u)时将诱发一个独立的随机bucket路径。
• 对于Add(u, data) 操作，root bucket总是被访问。在Evict 子例程中更多的桶被访问。但是，注意到bucket的访问模式独立于数据结构的配置，即在每个深度上选择两个随机bucket(除了叶子)进行驱逐，然后访问两个child buckets。