Circuit ORAM and Secure Computation for Big Data
Elaine Shi
Abstract:
Oblivious RAM (ORAM) constructions have traditionally been measured by their bandwidth overhead. While the bandwidth overhead metric best characterizes an ORAM's performance in secure processor and cloud outsourcing scenarios, we observe that in other cryptographic applications such as secure multi-party computation, the most relevant metric is an ORAM's circuit complexity.
We propose a new tree-based ORAM scheme called Circuit ORAM. Circuit ORAM achieves omega(D log N) total circuit size (over all protocol interactions) for memory words of D = Omega(log^2 N) bits, while achieving a negligible failure probability. For reasonably large memory word sizes, Circuit ORAM outperforms all known ORAM schemes in terms of circuit complexity both asymptotically and in practice. Empirical results suggest that Circuit ORAM yields circuits that are 30x to 60x smaller than Path ORAM for datasets of roughly 8GB. The speedup will be even greater for larger data sizes. As I will elaborate in the talk, Circuit ORAM also suggests that certain stronger interpretations of the Goldreich-Ostrovsky ORAM lower bound are tight.
Finally, I will talk about the SCVM framework, where programs written by real-life, non-expert developers can be easily compiled into an efficient secure computation protocol while offering 1) formal security guarantees through new type systems; and 2) orders of magnitude potential performance gains through static optimizations.