@inproceedings{KSS12,
	title="Billion-Gate Secure Computation with Malicious Adversaries",
	author="Ben Kreuter and Chih-hao Shen and Abhi Shelat",
	year="2012",
	booktitle="USENIX Security 2012"
}

A secure computation protocol for a function $f(x,y)$ must leak no information about inputs $x,y$ during its execution; thus it is imperative to compute the function $f$ in a data-oblivious manner. Traditionally, this has been accomplished by compiling $$f$$ into a boolean circuit. Previous approaches, however, have scaled poorly as the circuit size increases. We present a new approach to compiling such circuits that is substantially more efficient than prior work. Our approach is based on online circuit compression and lazy gate generation. We implemented an optimizing compiler for this new representation of circuits, and evaluated the use of this representation in two secure computation environments. Our evaluation demonstrates the utility of this approach, allowing us to scale secure computation beyond any previous system while requiring substantially less CPU time and disk space. In our largest test, we evaluate an RSA-1024 signature function with more than 42 billion gates, that was generated and optimized using our compiler. With our techniques, the bottleneck in secure computation lies with the cryptographic primitives, not the compilation or storage of circuits.