Efficient Mixed-Mode Oblivious RAMs

Wenhao Zhang, Xiao Wang, Chenkai WengIACR ePrint 2025

Abstract

Traditional Oblivious RAM (ORAM) protocols treat all memory accesses as private, incurring a significant logarithmic performance penalty even for operations that do not require secrecy. This paper introduces "Mixed-Mode" ORAM, a novel framework that supports both public and private memory accesses within a single, consistent data structure. By integrating Private Information Retrieval (PIR) and auxiliary buckets into a tree-based ORAM, the authors achieve $O(1)$ communication blowup for public accesses while maintaining $O(\log N)$ for private ones. Experimental results show that this approach can speed up secure computation tasks by up to 3x compared to state-of-the-art protocols.

Introduction

Oblivious RAM (ORAM) is a critical cryptographic primitive designed to hide access patterns to data structures. Without ORAM, an observer—such as a cloud provider—can infer sensitive information by monitoring which memory locations are accessed, even if the data itself is encrypted.

However, the standard theoretical model for ORAM assumes that every single access must be private. In practice, many operations are naturally public, such as database initialization, batch loading, or running known algorithms on confidential datasets. Currently, developers must either treat all accesses as private (sacrificing performance) or maintain separate public and private data structures (sacrificing consistency). Mixed-Mode ORAM bridges this gap by natively supporting both modes with optimal efficiency.

Methods: Integrating PIR and Tree Structures

The authors build upon the foundation of Tree-based ORAM (such as Path ORAM) but introduce a significant modification using Private Information Retrieval (PIR).

Fixed Mapping via PIR

In standard tree-based ORAM, every access requires remapping a block to a new random path to hide the access pattern. This "path refresh" is a major source of overhead. The mixed-mode approach instead uses a fixed mapping via a public Pseudo-Random Function (PRF) but utilizes PIR to retrieve the path. Since the server cannot determine which path was retrieved via PIR, the path remains hidden without needing to be changed.

Public Mode Optimization

Because the mapping is fixed, a "public read" does not require PIR; the client simply specifies the path. To handle public writes without triggering expensive security-preserving "eviction" processes, the authors add small "auxiliary buckets" to the tree structure.

Comparison between standard tree-based ORAM (a) and the proposed mixed-mode ORAM structure (b) featuring auxiliary buckets.

Three-Party Computation (3PC) Instantiation

The protocol is adapted for the 3PC setting using Distributed Point Functions (DPF) to implement efficient PIR. They also introduce a Parallel Eviction Algorithm (inspired by Onion ORAM) to reduce the circuit complexity of moving data blocks within the tree during maintenance operations.

Key Insights

  • Decoupling Access from Location: Using PIR allows the system to keep data in a fixed but hidden spot, removing the need for the logarithmic "position map" updates that characterize traditional ORAMs.
  • Consistency by Design: By using a single tree for both modes, the system maintains perfect data consistency without extra synchronization logic.
  • Metadata Efficiency: For public reads, the client downloads metadata to locate a block on a path and then uses a very small PIR to retrieve only that block, keeping bandwidth blowup at $O(1)$.

Results and Performance

The protocol was evaluated using synthetic benchmarks (RAM sizes $2^{10}$ to $2^{20}$) and real-world algorithms like Dijkstra’s and Binary Search.

  • Speedup: In LAN environments, the mixed-mode protocol is 3x faster than state-of-the-art protocols like GigaDORAM for public accesses. In WAN environments, it remains 2x faster.
  • Bandwidth Efficiency: The system achieves the theoretical best-case scenario: $O(1)$ blowup for public access and $O(\log N)$ for private access.
  • Algorithmic Gains: For tasks like oblivious binary search—which involves many public initializations followed by private searches—the mixed-mode approach significantly outperforms purely private ORAM implementations.

Limitations and Future Work

While the protocol reduces communication overhead, local computation remains a challenge. In very large RAM settings ($2^{20}$+ entries), the CPU work required to generate PIR/DPF vectors becomes a bottleneck. Future research may explore whether mixed-mode ORAM can achieve similar efficiency without relying on PIR, or how to extend these security guarantees to malicious or adaptive adversaries.

Summary updated

BibTeX
@article{zhang2025efficient,
  author = {Wenhao Zhang and Xiao Wang and Chenkai Weng},
  title = {{Efficient Mixed-Mode Oblivious RAMs}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}
Figure