Paper 2025/593

Oblivious Immutable Memory

Abstract

An oblivious RAM (ORAM) compiler is a cryptographic tool that transforms a program $P$ running in time $n$ into an equivalent program $\tilde{P}$, with the property that the sequence of memory addresses read from/written to by $\tilde{P}$ reveal nothing about $\tilde{P}$'s data (Goldreich and Ostrovsky, JACM'96). An efficient ORAM compiler $C$ should achieve some combination of the following: - Low bandwidth blow-up: $$ should read/write a similar amount of data as does P. - Low latency: $$ should incur a similar number of roundtrips to the memory as does P. - Low space complexity: $$ should run in as few words of local memory as possible. It is well known that for a generic compiler (i.e. one that works for any RAM program $$), certain combinations of efficiencies are impossible. Any generic ORAM compiler must incur $$ bandwidth blow-up, and any ORAM compiler with no latency blow-up must incur either $$ bandwidth blow-up and/or local space. Moreover, while a $$ bandwidth blow-up compiler is known, it requires the assumption that one-way functions exist and incurs enormous constant factors. To circumvent the above problems and improve efficiency of particular ORAM programs, we develop a compiler for a specific class of programs. Let $$ be a program that interacts with an immutable memory. Namely, $$ may write values to memory, then read them back, but it cannot change values that were already written. Using only information-theoretic techniques, we compile any such $$ into an oblivious form $$ with a combination of efficiencies that no generic ORAM compiler can achieve: - $$ incurs $$ amortized bandwidth blow-up. - $$ incurs $$ amortized latency blow-up. - $$ runs in $$ words of local space ($$ incurs an error with probability $$). We show that this, for instance, implies that any pure functional program can be compiled with the same asymptotics. Our work builds on and is compatible with prior work (Appan et al., CCS'24) that showed similar results for pointer machine programs that manipulate objects with constant in-degree (i.e., the program may only maintain a constant number of pointers to any one memory cell; our immutable memory approach does not have this limitation). By combining techniques, we can consider programs that interact with a mixed memory that allows each memory cell to be updated until it is frozen, after which it becomes immutable, allowing further reads to be compiled with the above asymptotics, even when in-degree is high. Many useful algorithms/data structures can be naturally implemented as mixed memory programs, including suffix trees (powerful data structures used in computational biology) and deterministic finite automata (DFAs).