Circuit ORAM 与实际性能

电路 ORAM 由 Wang、Chan 和 Shi 于 2015 年提出，旨在最大限度地降低带宽开销，同时便于在安全计算框架（混淆电路和秘密共享）中实现。它的核心创新是将桶大小减少到 Z = 2 个块（路径 ORAM 中为 Z = 5），在保持可忽略失败概率的同时将带宽开销减半。驱逐过程经过重新设计，可以表示为一个小型布尔电路。

在 Z = 5 的路径 ORAM 中，通过让每个桶容纳多个块，可以适应将块随机分配到路径的情况，从而控制暂存区溢出的概率。电路 ORAM 证明了，与随机驱逐不同，在使用确定性驱逐过程（深度优先驱逐）时，Z = 2 就足够了。与使用相同安全参数的路径 ORAM 相比，这可以将服务器存储和通信开销减半。

电路 ORAM 专门设计了能够表示为高效布尔电路的驱逐过程。在安全计算协议（混淆电路、SPDZ）中，ORAM 访问本身必须以不经意方式求值——执行计算的服务器不能获知访问了哪个内存位置。与路径 ORAM 的驱逐过程相比，电路 ORAM 简单的确定性驱逐电路在进行混淆时效率高得多。

对于一个包含 N 个块、每个块大小为 B 字节的数据库，电路 ORAM 每次访问需要传输 2 * log N * B 字节（每个桶有 Z = 2 个块，读取并写入一条路径）。对于包含 N = 2^20 个块且每个块为 4KB 的数据库，每次访问需要传输 160KB，而路径 ORAM 需要传输 400KB（Z=5）。对于典型参数，相对于明文访问的带宽开销约为 40 倍，比路径 ORAM 的 100 倍有所降低。

Oblix（Misra、Schlegel、Sherwood、Tsudik，2018 年）使用电路 ORAM 构建高级数据结构的不经意版本：不经意链表、不经意映射（哈希表）和不经意优先队列。这些结构支持在不泄露访问模式的情况下对动态数据执行不经意计算。Oblix 运行在 Intel SGX 飞地中，面向安全的私有集合求交和私有数据库查询。

TaoStore（Sahin、Zhu、Gunter、Borisov，2016）扩展了路径 ORAM，通过并行处理多个 ORAM 请求并批量执行路径驱逐来支持高吞吐量的异步访问。通过合并对同一路径的访问，TaoStore 实现了显著高于同步 ORAM 构造的吞吐量（每秒请求数），因此适合拥有大量并发客户端的云存储服务器。

Obladi（Crooks、Park、Alvisi、Iyengar，2018）在路径 ORAM 之上构建了完整的事务存储系统。Obladi 支持在加密且隐藏访问模式的存储上执行 ACID 事务。它引入了延迟执行机制：事务会被批量组织到多个时期中，并以一种隐藏每个时期内具体访问了哪些记录的方式执行。Obladi 作为客户端与不可信云存储后端之间的可信代理运行。

对于部署在 AWS 上的 1GB ORAM（262,144 个 4KB 块），如果客户端通过互联网访问数据块，路径 ORAM 每次访问的延迟约为 50–200 毫秒（主要由 log N = 18 次桶访问的往返时间造成）。通过并行获取桶，可以进一步降低延迟。对于 ORAM 位于 RAM 中的本地 SGX 应用，每次访问的延迟为 1–10 毫秒，许多安全计算应用都可以接受。

ORAM 的带宽开销高度取决于访问模式。对于使用 1MB 数据块的 1TB 云存储 ORAM，每次访问大约传输 25MB（log N = 25 层带来的 25 倍开销）。对于较小的数据块（4KB），每次访问的绝对字节开销更低，但相对开销更高。部署 ORAM 的组织必须为 20–50 倍的带宽放大预留预算，并确保网络链路和云出站流量成本已将这一点考虑在内。

访问隐私的一种 ORAM 替代方案是可信硬件：英特尔 SGX 或 AMD SEV 提供可信执行环境，在采取适当防护措施的情况下，即使主机操作系统也无法观察计算过程或内存访问模式。未配合 ORAM 的 SGX 仍会向硬件泄露页面级访问模式，因此需要在 SGX 内使用 ORAM 才能实现完整保护。与纯 ORAM 相比，可信硬件可以降低带宽开销，但需要信任硬件制造商及其供应链。

在以下情况下，ORAM 是合适的选择：攻击者能够观察服务器端访问模式（例如云服务提供商或共租户），数据敏感性足以证明 20–50 倍带宽开销是合理的，并且访问模式本身可能泄露敏感信息。对于大多数应用，采用完善的密钥管理并配合标准加密就已足够。ORAM 是面向高安全性场景的专用工具，例如医疗数据分析、私有机器学习、金融交易系统和执法数据库。

电路 ORAM 使用多大的桶？与路径 ORAM 相比，这为什么是一项改进？

电路 ORAM 将桶大小降至 Z=2（路径 ORAM 为 Z=5），并通过确定性的深度优先驱逐将带宽开销减半。它专为在混淆电路安全计算内部使用而设计。对于典型参数，实际开销是 40 倍的带宽放大。生产系统包括 Oblix（SGX + 不经意数据结构）、TaoStore（高吞吐量批处理 ORAM）和 Obladi（事务型 ORAM）。必须在 SGX 内使用 ORAM，因为单独使用 SGX 会泄露页面级访问模式。