Oblivious RAM (ORAM) has traditionally been defined by a fundamental trade-off: to hide which data you are accessing from an untrusted storage provider, you must pay a "bandwidth blowup" cost. For decades, researchers accepted that this cost must be at least logarithmic relative to the size of the database. However, a growing body of research demonstrates that by leveraging high degrees of parallelism, we can bypass these theoretical bottlenecks and achieve near-constant overhead for private data access.
The Parallelism-Privacy Duality
The core intuition behind this research direction is that concurrency is not just a performance optimization; it is a cryptographic tool. In a sequential ORAM, a single request must be obfuscated by performing several dummy or structural accesses. In a parallel system, we can instead use the collective distribution of many simultaneous requests to mask individual patterns.
Dana Dachman-Soled, Elaine Shi, and their colleagues introduced this as Oblivious Network RAM (O-NRAM) in Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness. They showed that if a program has sufficient inherent parallelism, multiple memory requests can be batched together and pseudorandomly assigned to different memory banks. When these batches are padded to a worst-case maximum, the sequence of bank accesses becomes statistically uniform and independent of the actual data retrieved, achieving $O(1)$ bandwidth blowup.
Overcoming Latency with Hardware Co-Design
While O-NRAM provides a theoretical framework for constant overhead, practical implementations require specialized hardware to manage the massive coordination of parallel requests.
- Secure Coprocessors: Jacob R. Lorch and Bryan Parno developed Shroud, a system that distributes ORAM operations across hundreds of low-cost secure hardware modules. As detailed in Toward Practical Private Access to Data Centers via Parallel ORAM, this architecture uses the inherent parallelism of tree-based ORAM structures to reduce access latencies from hours to seconds.
- Protocol-Hardware Co-Design: In Palermo: Improving the Performance of Oblivious Memory using Protocol-Hardware Co-Design, Haojie Ye and Yuchen Xia argue that ORAM protocols often contain "hidden" parallelism. By re-architecting the protocol to overlap recursive metadata lookups and serving multiple independent requests simultaneously via a 2D mesh of hardware controllers, they mitigate the stalls typically induced by sequential ORAM logic.
Distributed and Multi-Party Execution
Parallelism also extends to the way data is stored across multiple servers. In Multi-party Computation (MPC) settings, the goal is to execute private algorithms (like quicksort) while hiding the instructions and memory state from the computing parties themselves.
Keyu Ji and Kui Ren propose a 4-server distributed ORAM scheme in Multi-party Private Function Evaluation for RAM. This approach uses distributed point functions to enable memory reads with logarithmic communication complexity. Similarly, Xiao Wang and Chenkai Weng demonstrate in Efficient Mixed-Mode Oblivious RAMs that parallel eviction algorithms can move data blocks within a tree structure efficiently across distributed nodes, minimizing the circuit complexity required for secure computation.
Hiding Latency via Shuffling
For read-only applications, such as media hosting, the bottleneck is often the shuffling process required to reset the ORAM state. Prateek Saxena and Yaoqi Jia introduced PRO-ORAM in PRO-ORAM: Constant Latency Read-Only Oblivious RAM. By aggressively parallelizing data permutations across multiple cores within a Trusted Execution Environment (TEE) like Intel SGX, they effectively hide the computational overhead of maintaining obliviousness, providing the user with the perception of constant-latency access.