Bucket ORAM: Single Online Roundtrip, Constant Bandwidth Oblivious RAM.
Christopher W. Fletcher, Muhammad Naveed, Ling Hui Ren, Elaine Shi, Emil Stefanov · 2015
Known Oblivious RAM (ORAM) constructions achieve either optimal bandwidth blowup or optimal latency (as measured by online roundtrips), but not both. We are the first to demonstrate an ORAM scheme, called Bucket ORAM, which attains the best of both worlds. Bucket ORAM simultaneously achieves a single online roundtrip as well as constant overall bandwidth blowup. 1