PRF ⇒ polylogarithmic-overhead ORAM (hierarchical ORAM)

Fully-black-box reduction · standard model · GO96

Statement

An arbitrary RAM can be simulated online by a probabilistic oblivious RAM with polylogarithmic slowdown, whose CPU has $O(1)$ registers and a random function only it can access: the hierarchical construction — GO96. Instantiating the private random function with a PRF under a key held by the client gives, for $\lambda \le N\le \mathrm{poly}(\lambda )$, a computationally secure ORAM with $\mathrm{polylog}(N)$ amortized bandwidth blowup and client storage of $O(1)$ blocks, a polylogarithmic-overhead ORAM — GO96. GO96 unify and extend the square-root ORAM of Gol87 and the hierarchical ORAM of Ost90.

Notes

• The square-root ORAM has $O(\sqrt{N}\cdot \log N)$ amortized overhead, with constant client memory and $O(N)$ server storage — GO96. Its one-round version is optimal, up to logarithmic factors in client state, among one-round balls-and-bins ORAMs that do not duplicate balls (No reduction from ORAM to sub-square-root one-round balls-and-bins ORAM) — CDH20.
• Statistically and perfectly secure simulations with polylogarithmic overhead exist without any assumption or random oracle — Ajt10, DMN11. The tree-based ORAM has polylogarithmic worst-case cost with constant client storage — SCSL11, and with each bucket read and rewritten in full it hides the access pattern statistically — SDS+13.
• With a PRF the overhead drops to $O(\log N)$ (PRF ⇒ logarithmic-overhead ORAM (OptORAMa)) — AKL+20.