No reduction from ORAM to sublogarithmic-overhead balls-and-bins ORAM

Unconditional · against free reductions · GO96

Statement

Every statistically secure balls-and-bins ORAM with $O(1)$ blocks of client memory at every step has amortized bandwidth blowup $\Omega (\log N_1)$ over $N_1$ blocks. The bound holds even for an offline ORAM, which knows the indices and types of the whole operation sequence before it starts — GO96. Hence no sublogarithmic-overhead balls-and-bins ORAM exists. ORAM exists unconditionally: the linear scan, which reads and rewrites every cell on each operation, is perfectly secure — folklore. Hence no reduction of any class from ORAM to such a scheme exists.

Notes

• The bound applies only to ORAMs that move blocks without encoding them and whose security is statistical — BN16, LN18. Without the balls-and-bins restriction, a lower bound for offline ORAM with fixed instructions with $O(1)$ blocks of client memory at every step would imply superlinear lower bounds on the size of sorting circuits (Small sorting circuits ⇒ sublogarithmic-overhead offline ORAM with fixed instructions) — BN16.
• For online ORAM, LN18 remove both restrictions (No reduction from ORAM to sublogarithmic-overhead ORAM) — LN18.
• The bound also extends to read-only balls-and-bins ORAM — WW18.
• For a RAM with $N$ words of $N^{\epsilon }$ bits, for a constant $0<\epsilon <1$, Circuit ORAM is statistically secure with $O(1)$ words of client storage and runs $T$ steps in time $O(T\log N)\cdot \omega (1)$, showing that the bound is tight for some parameter ranges — WCS15.
• Computationally secure balls-and-bins ORAMs come within a $\log \log N_1$ factor of the bound: PanORAMa, with $O(\log N_1\cdot \log \log N_1)$ amortized bandwidth blowup and client storage of $O(1)$ blocks, can be instantiated in the balls-and-bins model — PPRY18.