阅读此文前，诚邀您点击一下“关注”，方便您随时查阅一系列优质文章，同时便于进行讨论与分享，感谢您的支持~

文|三月十

编辑|hshdhdjehd

引言

当敏感数据存储在不受信任的环境中时，仅加密是不够的。对加密数据的内存访问模式可以揭示有关其内容的大量信息。在某些设置中，观察内存访问模式可以让诚实但好奇的主机服务器完全重建加密数据库的内容。

在其他情况下，测量缓存未命中可以使攻击者恢复秘密密钥材料。在许多常见场景中，对手可能能够部分或完全观察到内存访问的不受信任环境。

其中包括存储在外部云服务中的私人信息、在不受信任的计算机上运行的受信任飞地，甚至是在多个租户之间共享内存缓存的公共云。

在所有这些设置中，安全性不仅需要隐藏每个数据项的内容，还需要隐藏访问的项目，在 ORAM 的许多潜在应用中，很自然地要考虑可变大小的项目。

一、预赛

在整个工作中，内存大小将被计为内存字数。假设一个内存字足够大，可以在内存中存储任何地址。在实际应用中，人们可能会想到 64 位或 128 位字。算法将在 RAM 模型中考虑，其中访问任意内存字需要 (1) 次操作。

安全参数用λ表示。如果一个量对于每个常量 c都是 O(λ −c )，则称该量是可忽略的，表示为 negl(λ)。如果概率为 1 − negl(λ)，则称该概率是压倒性的。总是假设 ORAM 中存储的块数 n 满足 n ≥ λ，因此任何数量为 negl(n) 也为 negl(λ)。

当输入 x 的算法 A 是概率性的时，我们有时可能会显式地写出随机数引理 1 的证明。A 使用的硬币作为 A 的输入，用分号分隔，如 A(x; r)。

1.主要化和 Schur 凸性

用 v 降序表示，↓ ∈ R m具有相同分量的向量，排序在 给定 R m 中的向量 v ，我们设 v, w 是 R m中的两个向量，使得向量 w 被称为主要化 v，记为 v 。

令 f : R m → R。如果映射 f 对于主要化顺序是非递减的，则称它是 Schur 凸的。也就是说，对于任 意两个向量 v，w 。

令 f : R m → R。如果对于 R m 中的任意两个向量 v、w和 [0, 1] ⊂ R 中的任意 α，则称映射 f 是凸的，它认为：

2.加权不经意RAM

加权ORAM，也写成wORAM，是一对客户端‑服务器协议（Setup，Access），定义如下。

– Setup(N, B, D) 将数据总量的上限 N、块大小 B 和形式为 (ai , datai) 的对集合 D 作为输入，其中ai是成对的不同的地址，datai是大小为 |datai |的任意数据∈ [1, B]。安装程序输出初始客户端状态和初始服务器状态。

– Access(op, a, data) 将操作 op ∈ {read, write}、地址 a 和一些大小为 |data| 的数据数据作为输入∈ [1, B]。如果 op = read，Access 将最后写入地址 a 的数据输出到客户端。如果 op = write，Access 会用 data 替换地址 a 处写入的数据。 Access 还可以更新客户端和服务器状态。

3.树形 ORAM

我们通过改变遵循 Tree ORAM 范例的标准 ORAM 方案来构建 wORAM。在本节中，我们提供了该范例的高级算法视图。这种观点是有目的的，旨在适应多种现有的 Tree ORAM 方案。

现有的 Tree ORAM 方案是标准的 ORAM，旨在存储固定大小的项目。在 Tree ORAM 中，为了存储 n 个大小为 B 的项目，服务器创建了一个有 n 个叶子的完整二叉树，我们假设 n 是 2 的幂，必要时增加到 2 的下一个幂。

4.ORAM 模型

考虑一个 Tree ORAM 实例化 ORAMZ ← Setup[Z](N, B, D)，桶容量为 Z。如果 s 是一个访问序列，我们称 st(ORAMZ[s]) 为 stash usage，即数中的项目隐藏访问的结果。

在 Path ORAM 和许多由它派生的 Tree ORAM 方案中，正确性证明遵循类似的步骤：

二、从 Tree ORAM 到 WORAM 的通用构造

转型的一个方面的必要性可能不会立即显现出来。即，如果原始 ORAM 的存储桶容量为 Z，则其加权版本的存储桶容量将为 Z + 1。此更改对于本节的主要定理成立而言不是必需的。

然而，当将主要定理应用于特定的 ORAM 时，尤其是 Path ORAM：实际上，桶容量的这种增加可以试探性地免除。

1.加权变换，我们定义了一个通用变换

加权，将标准树 ORAM 方案 ORAMZ = (Setup, Access)作为输入，并输出加权 ORAM 方案 Weighted(ORAMZ ) = ORAM*Z = (Setup 访问)。

首先考虑设置。我们说起始方案 ORAMZ有一个常规设置，如果它的设置过程相当于创建一个包含所有项目的空树，然后做从左到右对树中的每一片叶子重复驱逐。在这里，“等效”是指这个过程的输出和正常设置过程的输出是同分布的。

尽管这种规律性的概念是非标准的，但它的好处是可以从逐出过程的行为中推断出设置过程的行为。就我们的目的而言，这意味着足以解释如何转换驱逐过程以处理可变大小的块。

2.实验结果

为了根据经验测试我们的加权 ORAM 的正确性，我们实现了路径 ORAM 结构并执行了模拟访问。做了两个实验：一个是 N 个大小相同的对象（模拟标准情况），另一个是大小可变的对象（大小均匀随机，但总和为 N）。我们的结果以图表形式呈现。如下：

三、对现有树 ORAM 的应用

1.加权简单 ORAM

每个桶的容量为 Z = O(log N)，当且仅当有一个桶包含超过 Z 个项目时 ORAM 才会溢出：没有存储。

从 Tree ORAM 框架的角度来看， stash 确实存在，但是，要求它在任何（合法）访问序列的结果中为空。也就是说，我们将 stash bound R 设置为 0。

S 定义为包含每个树节点桶的单例 {bucket} 的集合。 正确性等同于 S 中没有元素见证失败这一事实是直接的，因为 正确性恰恰要求没有节点溢出。

2.加权路径 ORAM

让 ORAMZ ← PathOram.Setup(N, Z) 成为 Path ORAM 的一个实例。 Path ORAM 的桶容量 Z 是一个小常数；该方案被证明对于 Z = 5 是正确的，我们将使用该值。存储容量为 R = O(log N)。

– ChooseEvictionPath(leaf) 简单地返回 P(leaf)。

– ChooseNextBlock(stash, bucket, path) 从缓冲区返回一个项目，这样它的关联叶在桶下面，并且项目的位置和路径之间的相遇在这些项目中最低。

3.加权不经意并行 RAM

Circuit ORAM 是 Path ORAM 的变体，其中客户端只需要本地空间来容纳一个块。为实现这一点，驱逐算法略有不同，存储由服务器（作为根节点的父节点）而不是本地存储。

函数 Weighted 在这里也产生了正确的 ORAM。为了证明这一点，我们只需要展示我们如何适应存储存储在树顶的事实。找出哪种方法并不明显，因为由于块大小不同，客户端不能简单地逐块流式传输存储内容：它会泄漏块大小信息。

四、来自加权 ORAM 的可搜索加密

使用可搜索对称加密 (SSE)，客户端可以将数据库的存储委托给诚实但好奇的服务器。然后，客户端可以通过向服务器发出搜索查询来对数据库执行搜索。

在动态 SSE 的情况下，客户端还可以通过向服务器发出更新查询来更新数据库。安全目标是在这些操作期间泄漏到服务器的信息应该是有限的，在某种意义上将很快被定义。

SE 通常不寻求最小泄漏，而是通过允许受控的泄漏年龄在安全性和性能之间取得折衷。在安全模型中，方案允许的泄漏由泄漏函数L = {LSetup,LSearch,LUpdate}表示。

结语

个有趣特性是更新与搜索无法区分。事实上，添加和删除列表中任意数量的文档都可以在一次交互中执行，无需额外费用。

然而，这也意味着将单个文档添加到关键字会导致 O(U log2 U) 带宽成本。如果希望对单个文档进行更便宜的更新，则另一种解决方案是使用较小的块大小。

较小的块大小（线性地）降低了更新成本，同时（对数地）增加了搜索成本。通过将反向索引存储在具有可参数化最大块大小 B 的 wORAM 中来提供这种权衡。

为了减小位置图的大小，我们借用了介绍的指针思想。也就是说，属于同一列表 DB(w) 的每个块都包含前一个块的位置。这允许存储在客户端上的位置图仅存储最后一个块的位置，从而导致 O(W) 存储。

参考文献：

1、Gilad Asharov、Ilan Komargodski、Wei‑Kai Lin、Kartik Nayak、Enoch Peserico 和 Elaine Shi。

OptORAMa：最佳不经意的 RAM。 Anne Canteaut 和 Yuval Ishai，编辑，EURO CRYPT 2020，第二部分，LNCS 第 12106 卷，斯普林格，海德堡，2020 年 。

2、Ang`ele Bossuat、Raphael Bost、Pierre‑Alain Fouque、Brice Minaud 和 Michael Reichle。 SSE 和 SSD：页面高效的可搜索对称加密。 Tal Malkin 和 Chris Peikert，编辑，CRYPTO 2021，第三部分，LNCS 第 12827 卷，虚拟活动，2021 年。

3、Petra Berenbrink、Tom Friedetzky、Zengjian Hu 和 Russell Martin。在加权球入箱游戏中。在 Volker Diekert 和 Bruno Durand 的编辑中，STACS 2005，柏林，海德堡，2005 年。

4、David Cash、Paul Grubbs、Jason Perry 和 Thomas Ristenpart。针对可搜索加密的泄漏滥用攻击。 Indrajit Ray、Ninghui Li 和 Christopher Kruegel 编辑，ACM CCS 2015，ACM 出版社，2015 年 。

5、Paul Grubbs、Marie‑Sarah Lacharit´e、Brice Minaud 和 Kenneth G. Paterson。 Pump up the volume：从范围查询的体积泄漏中重建实用数据库。摘自 David Lie、Mohammad Mannan、Michael Backes 和 XiaoFeng Wang，编辑，ACM CCS 2018，ACM Press，2018 年。