PRF ⇒ logarithmic-overhead ORAM (OptORAMa)

Fully-black-box reduction · standard model · AKL+20

Statement

If a PRF secure against every efficient adversary exists, then for all $\lambda \le N\le T\le \mathrm{poly}(\lambda )$ there is an ORAM over $N$ blocks of at least $\log N$ bits with $O(\log N)$ amortized bandwidth blowup over $T\ge N$ accesses, whose security failure probability is negligible in $\lambda$. It keeps $O(1)$ words of client state besides the PRF key and needs no large-word assumption, so it is a logarithmic-overhead ORAM — AKL+20. One-way functions suffice, by OWF ⇒ PRG and PRG ⇒ PRF — AKL+20. The overhead matches the $\Omega (\log N)$ lower bound for online ORAM (No reduction from ORAM to sublogarithmic-overhead ORAM), so it is optimal — AKL+20.

Notes

• PanORAMa earlier reached $O(\log N\cdot \log \log N)$ amortized bandwidth blowup, with client storage of $O(1)$ blocks and blocks of $\Omega (\log N)$ bits — PPRY18; OptORAMa builds on it — AKL+20.
• One building block is a deterministic linear-time oblivious algorithm for tight compaction, improving the previously best deterministic and randomized algorithms, which run in time $O(n\log n)$ and $O(n\log \log n)$ — AKL+20.
• With a private random oracle in place of the PRF, the construction is statistically secure — AKL+20.