Circuit ORAM and Practical Performance
Examine Circuit ORAM improvements and the real-world performance overhead of ORAM constructions.
Circuit ORAM Design Goals
Circuit ORAM, proposed by Wang, Chan, and Shi (2015), was designed to minimize bandwidth overhead while being simple to implement in secure computation frameworks (garbled circuits and secret sharing). Its key innovation is reducing the bucket size to Z = 2 blocks (compared to Z = 5 in Path ORAM), halving the bandwidth while maintaining negligible failure probability. The eviction procedure was redesigned to be expressible as a small boolean circuit.
Bucket Size Reduction
In Path ORAM with Z = 5, the stash overflow probability is controlled by having multiple blocks per bucket to accommodate the random assignment of blocks to paths. Circuit ORAM proves that Z = 2 is sufficient when using a deterministic eviction procedure (deep-first eviction) rather than random eviction. This halves the server storage and communication overhead compared to Path ORAM with the same security parameters.
All lessons in this course
- The Access Pattern Leakage Threat
- Path ORAM: Hiding Memory Access
- Circuit ORAM and Practical Performance
- ORAM in Cloud Storage and Secure Processors