DCR ⇒ constant-bandwidth ORAM (Onion ORAM)

Standard model · DDF+16

Statement

If DCR holds, Onion ORAM is an ORAM with server computation secure against a semi-honest server. Instantiated with the layered Damgård–Jurik cryptosystem of DJ01, it has $O(1)$ worst-case bandwidth blowup and uses polylogarithmic server computation to get around the logarithmic lower bound on bandwidth blowup; it is a constant-bandwidth ORAM — DDF+16. The logarithmic bound for online ORAM covers only servers that store and return data (No reduction from ORAM to sublogarithmic-overhead ORAM), so it does not apply — LN18. DDF+16 also instantiate it with a BGV-style somewhat homomorphic encryption scheme without bootstrapping, and give techniques against a malicious server that avoid SNARKs — DDF+16.

Notes

• It is the first ORAM with constant bandwidth blowup under standard assumptions, even against a semi-honest server — DDF+16.