Burst ORAM: Minimizing ORAM Response Times for Bursty Access Patterns

We present Burst ORAM, the first oblivious cloud stor-age system to achieve both practical response times and low total bandwidth consumption for bursty work-loads. For real-world workloads, Burst ORAM can at-tain response times that are nearly optimal and orders of magnitude lower than the best existing ORAM sys-tems by reducing online bandwidth costs and aggres-sively 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 compa-rably low. In a 32TB ORAM with 50ms network latency and sufficient bandwidth capacity to ensure 90 % of re-quests have baseline response times under 53ms, 90 % of Burst ORAM requests have response times under 63ms, while requiring only 30 times the total bandwidth con-sumption of the insecure baseline. Similarly, with suffi-cient bandwidth to ensure 99.9 % of requests have base-line responses under 70ms, 99.9 % of Burst ORAM re-quests have response times under 76ms.