Cloak: Heuristic ORAM Optimization Through Fixed Temporal Distribution
For cloud storage users needing access pattern privacy, Cloak makes ORAM practical by dramatically reducing overhead for real-world workloads with temporal locality.
Cloak improves ORAM performance by exploiting temporal locality in workloads, achieving overheads as low as 1.1x over a non-oblivious baseline while maintaining security, with throughputs of 165,000 and 157,000 ops/s on Netflix and Ethereum traces.
Encrypted cloud storage can hide data contents but still leak sensitive information through access patterns. ORAM addresses this by hiding access patterns, but existing ORAM systems are too inefficient to deploy in practice. We present Cloak, an oblivious storage system that dramatically improves performance by leveraging a simple, widely observed property of real workloads: temporal locality, where recently accessed items are more likely to be accessed again soon. Instead of trying to make server accesses look perfectly uniform, Cloak makes server traffic follow a fixed, "recentness-biased" pattern and then uses real queries to fill as much of that traffic as possible. When the workload exhibits temporal locality, Cloak achieves overheads as low as $1.1\times$ over a non-oblivious and unencrypted baseline. Importantly, this heuristic affects only performance, not security. We evaluate Cloak on Netflix click-stream and Ethereum transaction traces, achieving 165,000 and 157,000 operations per second, respectively, on a single machine.