Cryptology ePrint Archive: Report 2015/1065

Bucket ORAM: Single Online Roundtrip, Constant Bandwidth Oblivious RAM

Christopher Fletcher and Muhammad Naveed and Ling Ren and Elaine Shi and Emil Stefanov

Abstract: 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.

Category / Keywords: cryptographic protocols / Oblivious RAM, constant bandwidth blowup, single online roundtrip

Date: received 31 Oct 2015, last revised 3 Nov 2015

Contact author: elaine at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20151104:034200 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]