Circuit ORAM and Practical Performance

Circuit ORAM, proposed by Wang, Chan, and Shi (2015), was designed to minimize bandwidth overhead while being simple to implement in secure computation frameworks (garbled circuits and secret sharing). Its key innovation is reducing the bucket size to Z = 2 blocks (compared to Z = 5 in Path ORAM), halving the bandwidth while maintaining negligible failure probability. The eviction procedure was redesigned to be expressible as a small boolean circuit.

In Path ORAM with Z = 5, the stash overflow probability is controlled by having multiple blocks per bucket to accommodate the random assignment of blocks to paths. Circuit ORAM proves that Z = 2 is sufficient when using a deterministic eviction procedure (deep-first eviction) rather than random eviction. This halves the server storage and communication overhead compared to Path ORAM with the same security parameters.

Circuit ORAM was specifically designed to have an eviction procedure that can be expressed as an efficient boolean circuit. In secure computation protocols (garbled circuits, SPDZ), the ORAM access itself must be evaluated obliviously — the server performing computation must not learn which memory location is accessed. Circuit ORAM's simple deterministic eviction circuit is far more efficient to garble than Path ORAM's eviction procedure.

For a database of N blocks of size B bytes, Circuit ORAM requires 2 * log N * B bytes per access (reading and writing one path with Z = 2 blocks per bucket). For N = 2^20 blocks of 4KB each, this is 160KB per access, compared to 400KB for Path ORAM (Z=5). The bandwidth overhead versus plaintext is about 40x for typical parameters, down from 100x for Path ORAM.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) uses Circuit ORAM to build oblivious versions of high-level data structures: oblivious linked lists, oblivious maps (hash tables), and oblivious priority queues. These structures allow oblivious computation on dynamic data without revealing access patterns. Oblix runs inside Intel SGX enclaves and targets secure private set intersection and private database queries.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) extends Path ORAM to support high-throughput asynchronous access by processing multiple ORAM requests in parallel and batching path evictions. By combining accesses to the same path, TaoStore achieves significantly higher throughput (requests per second) than synchronous ORAM constructions, making it suitable for cloud storage servers with many concurrent clients.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) builds a full transactional storage system on top of Path ORAM. Obladi supports ACID transactions over encrypted, access-pattern-hiding storage. It introduces delayed execution: transactions are batched into epochs and executed in a way that hides which specific records were accessed within each epoch. Obladi runs as a trusted proxy between clients and an untrusted cloud storage backend.

For a 1GB ORAM (262,144 blocks of 4KB) deployed on AWS with a client accessing blocks over the internet, Path ORAM latency is approximately 50-200ms per access (dominated by round-trip time for the log N = 18 bucket accesses). With parallel bucket fetches, this can be reduced. For local SGX applications with ORAM in RAM, latency is in the range of 1-10ms per access, acceptable for many secure computation applications.

The bandwidth overhead of ORAM depends heavily on access patterns. For a 1TB cloud storage ORAM with 1MB blocks, each access transfers about 25MB (25x overhead for log N = 25 levels). For small blocks (4KB), the overhead per access is lower in absolute bytes but higher in relative terms. Organizations deploying ORAM must budget for 20-50x bandwidth amplification and ensure their network links and cloud egress costs account for this.

An alternative to ORAM for access privacy is trusted hardware: Intel SGX or AMD SEV provides a trusted execution environment where even the host OS cannot observe computation or memory access patterns (with appropriate defenses). SGX without ORAM still leaks page-level access patterns to the hardware, so ORAM within SGX is needed for full protection. Compared to pure ORAM, trusted hardware reduces the bandwidth overhead but requires trusting the hardware manufacturer and supply chain.

ORAM is appropriate when: the adversary observes server-side access patterns (cloud provider, co-tenant), data sensitivity justifies 20-50x bandwidth overhead, and the access pattern itself would reveal sensitive information. For most applications, standard encryption with careful key management is sufficient. ORAM is a specialized tool for high-security scenarios: medical data analysis, private machine learning, financial trading systems, and law enforcement databases.

What bucket size does Circuit ORAM use, and why is this an improvement over Path ORAM?

Circuit ORAM reduces bucket size to Z=2 (vs Path ORAM's Z=5), halving bandwidth via deterministic deep-first eviction. It is designed for use inside garbled circuit secure computation. Practical overhead is 40x bandwidth amplification for typical parameters. Production systems include Oblix (SGX + oblivious data structures), TaoStore (high-throughput batched ORAM), and Obladi (transactional ORAM). ORAM within SGX is necessary because SGX alone leaks page-level access patterns.