Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary.
The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur $Theta(N)$ overhead. The previously best ORAM in terms of worst-case overhead achieves $O(log ^2 N/loglog N)$ overhead.
Technically, we design a novel de-amortization framework for modern ORAM constructions that use the “shuffled inputs” assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC ’97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.