Small sorting circuits ⇒ sublogarithmic-overhead offline ORAM with fixed instructions

Free reduction · standard model · BN16

Statement

Suppose Boolean circuits of size $s(n,w)$ sort $n$ words of $w$ bits. Then for word size $w\in \Omega (\log n)\cap n^{o(1)}$ and a constant number of client registers, there is a secure offline ORAM with fixed instructions, which knows every instruction in advance, the value of every store included, with total bandwidth and computation $O(n\log w+s(2n/w,w))$ — BN16. Under small sorting circuits, $s(n,w)=o(n\cdot w\cdot \log n)$ for every such $w$, so $s(2n/w,w)=o(n\log n)$, and $\log w=o(\log n)$; the offline ORAM therefore has $o(\log n)$ amortized overhead and is a sublogarithmic-overhead offline ORAM with fixed instructions — BN16.

Notes

• The construction relies on the store values being fixed in advance; BN16 pose its extension to a more expressive offline class as an open question, so it is not known to give an offline ORAM that learns each written block only with its operation — BN16.
• Contrapositively, an $\Omega (\log n)$ lower bound for offline ORAM with fixed instructions and a constant number of client registers, without the balls-and-bins restriction, would show that for some word size $w\in \Omega (\log n)\cap n^{o(1)}$, sorting $n$ words of $w$ bits has no Boolean circuits of size $o(n\cdot w\cdot \log n)$, a superlinear lower bound in the input length $nw$ — BN16. No superlinear lower bound on general Boolean circuit size is known for any explicit function — standard.
• Under the balls-and-bins restriction with statistical security, offline ORAM has $\Omega (\log n)$ overhead (No reduction from ORAM to sublogarithmic-overhead balls-and-bins ORAM) — GO96, and online ORAM has it without either restriction (No reduction from ORAM to sublogarithmic-overhead ORAM) — LN18.