We present Burst ORAM, the first oblivious cloud storage system to achieve both practical response times and low total bandwidth consumption for bursty workloads. For real-world workloads, Burst ORAM can attain response times that are nearly optimal and orders of magnitude lower than the best existing ORAM systems by reducing online bandwidth costs and aggressively rescheduling shuffling work to delay the bulk of the IO until idle periods.

We evaluate our design on an enterprise file system trace with about 7,500 clients over a 15 day period, comparing to an insecure baseline encrypted block store without ORAM. We show that when baseline response times are low, Burst ORAM response times are comparably low. In a 32TB ORAM with 50ms network latency and sufficient bandwidth capacity to ensure 90% of requests have baseline response times under 53ms, 90% of Burst ORAM requests have response times under 63ms, while requiring only 30 times the total bandwidth consumption of the insecure baseline. Similarly, with sufficient bandwidth to ensure 99:9% of requests have baseline responses under 70ms, 99:9% of Burst ORAM requests have response times under 76ms.