Oblivious Data Structures学习笔记

Refence： Oblivious Data Structures^*（Xiao Shaun Wang¹, Kartik Nayak¹, Chang Liu¹, T-H. Hubert Chan²,
Elaine Shi¹, Emil Stefanov³, and Yan Huang⁴）

Introduction

 Oblivious Data Structure在渐进性和实践中比著名的O-RAM方案好。
 对于一些对访问模式有预见性的算法，有自定义的、渐进的、更有效的结构是有利的。算法的访问模式图有存储单元作为节点，并且只有当相应节点之间存在有向边时，两个单元才能被连续访问。因此，对于一般的RAM程序，它们的访问模式可以是一个完整的图。通用数据结构具有更稀疏的访问模式图，与对数据进行任意随机访问的通用RAM程序相比。例如，对于二叉搜索树或堆，内存访问只能从一个树节点到相邻的节点，因此通过不隐藏访问模式的一些公开的方面，我们应该能够获得一些效率(与ORAM相比)。对于稀疏访问图的两种不同的刻画，与一般ORAM方案相比，Oblivious Data Structure获得了渐近性能增益。

Applications
 稀松访问模式图的这两种描述为常见的工作引起了众多的应用：

1. 常见的数据结构。一套高效的无关数据结构实现，包括常用的map/set、priority_queue、stack、queue和deque。
2. 茫然的内存分配器。使用ODS框架来设计一个高效的茫然内存分配器。茫然内存分配器每次操作需要传输O(log3n)位。与基线的方法相比，这种方法实现了指数节约。对于茫然内存的分配，茫然内存分配器算法可以在支持oram的安全处理器上使用。
3. 图算法。在具有低倍维数图的操作上实现渐进性改进，包括随机漫步和最大流。我们考虑了FordFulkerson[15]最大流量算法的一种Oblivious变体，该算法在每次迭代中使用深度优先搜索，在残差网络中找到一条增广路径。我们还考虑了平面图上的最短路径距离查询。我们利用平面分隔器定理来创建一个图数据结构，使其oblivious。

Techniques
 以下两个主要的技术来构造稀疏访问模式图的茫然数据结构。

• Pointer-based technique 基于指针的方法. 适用于有限制度的有根树。每个父节点为其子节点存放指针并且储存子节点的位置标记。这样当获取父节点时，立即获取其子节点的位置标记，从而消除了执行位置图(position map)查找的需要(因此有了对数因子的改进)。
• Locality-based technique 基于位置的技术. 适用于具有低倍维度的访问模式图。图中的节点被划分为集群，这样每个集群的指针只指向O(1)^dim的相邻集群，其中dim是倍维的上界。直觉上，每个集群包含O(log N)个节点，并且可以支持O(log ^1/dim N)个节点访问。正如我们将要看到的，每个集群的大小为Ω(log²N)位，因此每个集群可以在Path ORAM中被存储为一个块block，带宽增加到O(log N)。

Problem Definition

 数据结构D是一个支持特定类型操作(insert,del,or lookup)的数据集合。每个操作都由一些操作数参数化(例如，要查找的键)。ODS的目标是确保任意两个包含k个操作的序列，他们的访问模式必须是不可区分的。这意味着访问模式(包括访问次数)不应该泄露操作码(操作类型)和操作数(key和data)的信息。
Definition 1(Oblivious data structure)我们认为数据结构D是茫然的，设存在一个多项式时间模拟器S，这样对于任意多项式长度序列的数据结构操作 $\overrightarrow{ops}$ =( (op₁,arg₁),(op₂,arg₂),…,(op_M,arg_M) )
    addresses_D($\overrightarrow{ops}$)== S(L($\overrightarrow{ops}$ ))
其中addresses_D($\overrightarrow{ops}$)是由茫然数据结构在一系列操作$\overrightarrow{ops}$期间产生的物理地址；并且L($\overrightarrow{ops}$ )称为泄露函数。通常我们认为L($\overrightarrow{ops}$ ) = M，即操作数的数量被泄露了，但没有其他的。
 直观地说，这个定义表示由一系列数据结构操作产生的访问模式应该只显示操作的总数。也就是说，多项式时间模拟器S只知道操作的总次数，就可以模拟物理地址，这样多项式时间的识别器就无法区分被遗忘的数据结构生成的模拟地址和真实地址。
 请注意，直接使用标准ORAM可能不能满足我们的定义，因为信息可能会通过访问的数量泄露。具体来说，某些数据结构操作比其他操作需要更多的内存访问;例如，AVL树的删除可能会引起旋转操作，因此会比查找操作引起更多的内存访问。因此，即使我们使用标准的ORAM，也可能需要填充来隐藏正在执行的数据结构操作。

Building Block: Non-Recursive Position-based ORAM(构建块:非递归基于位置的ORAM)

Figure1:静态茫然二叉查找树. 左边二逻辑二叉查找树，右边是如何将这些节点非递归的存储在基于位置的ORAM上。每个位置标记指定到树中叶结点的路径。每个父类都指向其子类的位置标签，这样我们就可以省去查找position map的需要，从而与通用ORAM相比节省了O(log N)因子。

Oblivious Data Structure(茫然数据结构)

Node format. 在ODS这个数据结构中，每个节点都由标识符id和它的位置标签pos来标识，节点还存储了它所有子节点的位置标签。因此，每个节点的格式为node := (data,id,pos,childrenPos) ,特别地，childrenPos是从每个子id映射到它的位置标记。记为childrenPos[id_c] 表示以id_c标识的子类的位置标签。
 所有节点将被(加密并)存储在服务器上基于位置的ORAM(非递归)中。客户端只存储树根的位置标记和标识符。

 注意一旦一个节点被服务器获取，他的位置标记就会暴露给服务器，因此我们需要为这个节点生成一个新的位置标记。同时，这个位置标记也应该在他父节点的子类位置列表中更新。我们的关键思想是依赖O(logN)大小的客户端缓存，这样在整个插入操作中，与此操作有关的所有节点都被获取一次。在这些阶段被从服务器获取和删除后，他们将被储存在客户端缓存中。这样客户端可以在写回他们之前在本地对这些节点进行更新。这些更新可能包括插入、删除、和修改图结构(如AVL树示例中的旋转)。最后，在操作结束时，本地缓存的所有节点将被写回服务器。在回写之前，所有被获取的节点必须被随机分配新的位置标签，他们的父节点必须被适当的修改，以指向子节点的新位置标签。

B ODS数据结构和框架

B.1内存抽象

 内存为存储上述数据结构图中的节点提供了空间。该图中的每个节点(id, data)都是一个原子存储单元，其中id可以视为节点在内存中的地址。我们定义了以下四种类型的内存操作：
        Read(id), Write(id,data^*), Insert(id,data^*), Del(id)
 任何的数据结构算法可以用这四个类型的内存操作以及内存操作之间的计算步骤(例如，键值的比较)来表示。
 请注意，相比之下，标准的通用的ORAM通常只支持read(id)和write(id,data^* )操作，但不支持insert(id,data^* )和del(id)。附加的insert(id,data^*)和del(id)操作是为了方便表示动态数据结构操作，如插入和删除。

B.2 ODS架构

 ODS 客户端. 在普通的、非茫然的数据结构中，内存操作直接进入内存，从而通过访问模式泄露信息。在茫然数据结构中，我们将使用一个专门设计的“茫然内存”替换内存，称为ODS客户端。这个ODS客户端的角色类似于ORAM客户端;从数据结构程序的角度来看，它提供了与内存完全相同的接口(即支持前面提到的四种操作)。在内部，ODS客户机将逻辑内存请求转换为一系列混淆的内存访问，并将混淆的物理地址显示给不受信任的服务器。
 显然，一种简单但低效的方法是简单地使用通用ORAM客户机作为ODS客户机。但是，我们将构造一个定制的ODS客户机，它将带来渐近的加速。
 **不受信任的服务器.**不受信任的服务器支持getphys addr和putphys addr, data的简单接口。服务器不应该从被访问的物理地址序列中获得任何信息。

B.3 动态访问

  每个(动态)数据结构操作实现如下：

• 一个单独的 ODS. Start 调用。 为该操作的开始做准备。
• 一个 ODS.Access 序列调用ODS。 这将告诉ODS要从服务器获取和删除哪些节点，以及要对这些节点进行哪些本地更新。这些节点(最多为O(log N))在执行ODS.Finalize调用之前保存在ODS客户机的缓存中。
    ODS.Access调用底层的基于位置的ORAM生成的ReadAndRemove操作，因此服务器观察到的物理访问是茫然的。并不是每个ODS.Access调用都将生成一个ReadAndRemove操作，因为缓存中的节点可以直接返回。(只有在ODS.Access算法的8，17，25行生成ReadAndRemove操作，其他所有操作由缓存提供) 但是，因为在ODS.Finalize之后，这样的缓存命中/错过行为不会泄露信息，ODS客户端执行填充以确保每一个操作都会产生对底层基于位置的ORAM的相同数量的ReadAndRemove和Add调用。
• 一个单一的ODS.Finalize调用ODS。 此时，ODS客户机执行三个任务:1)为每个缓存节点生成新的pos，并根据每个节点的(id, pos)更新所有缓存节点的childrenPos(lines 1 - 3 in ODS.Finalize); 2)通过对基于位置的ORAM (line 7 in ODS.Finalize)进行Add调用，将缓存的节点写回服务器; 3)执行填充，以确保每个数据结构操作产生相同数量的ReadAndRemove(第4行ODS.Finalize)和Add操作(第9行ODS.Finalize)到底层基于位置的ORAM。