MC-ORAM: A Mask-Assisted and Counter-Based Non-Deterministic ORAM Inside VM-Based TEEs

Protecting memory access patterns is crucial for secure computation in environments where sensitive data is processed. Oblivious RAM (ORAM) offers a promising solution to safeguard against such leaks by hiding memory access patterns. However, integrating ORAM with modern Trusted Execution Environments (TEEs) introduces challenges due to the TEE's deterministic encryption, which undermines ORAM's oblivious guarantees. In this work, we present MC-ORAM, a novel mechanism to introduce non-determinism into ORAM systems running in VM-based TEEs. Traditional counter-based designs, such as those using 64-bit counters for every 64-bit data, introduce non-determinism but incur significant overheads due to increased memory traffic. In contrast, MC-ORAM employs a shorter, masking-assisted and counter-based design that ensures ciphertext freshness with minimal overhead. Our method minimizes memory traffic, achieving only a ${1. 1 2 5} \times$ increase in bandwidth, compared to the baseline, a substantial improvement over previous approaches that incur a $2 \times$ bandwidth overhead. Through experiments on PathORAM and RingORAM, we demonstrate that MC-ORAM delivers notable performance improvements, achieving end-to-end speedup of ${1. 8 2} \times$ over existing non-deterministic ORAM solutions.