eprint.iacr.orgpaperOptimal Statistical Oblivious RAM and Search Tree in the External-Memory Model
ePrint paper by Andrew Krapivin and Elaine Shi that breaks the long-standing log-squared upper-bound barrier for statistically secure Oblivious RAM and for oblivious search trees in the external-memory model. It gives an optimal O(log_B N) statistically secure ORAM when B ≥ log^{1+ε} N. It also gives an optimal oblivious search tree when B ≥ log^{2+ε} N, which matches non-oblivious search trees ("obliviousness for free"). The block-size assumptions match hardware-enclave deployments that use oblivious algorithms, such as those of Signal and Meta.
TL;DR Optimal O(log_B N) statistically secure ORAM and oblivious search tree constructions that remove the long-standing log-squared overhead for wide-block parameters.
Organisations named here
- Andrew Krapivin
- Elaine Shi
- Meta
Technologies named here
- Oblivious search tree
- Signal
Related in other
eprint.iacr.orgpaperRerandomizable Garbling for Arithmetic Circuits
aseemshrey.inarticle