Circuit Structures for Improving Efficiency of Security and Privacy Tools
Samee Zahur and David Evans
34th IEEE
Symposium on Security and Privacy ("Oakland")
San Francisco, CA
19-22 May 2013
Abstract
Several techniques in computer security, including generic protocols for
secure computation and symbolic execution, depend on implementing
algorithms in static circuits. Despite substantial improvements in
recent years, tools built using these techniques remain too slow for
most practical uses. They require transforming arbitrary programs into
either Boolean logic circuits, constraint sets on Boolean variables, or
other equivalent representations, and the costs of using these tools
scale directly with the size of the input circuit. Hence, techniques for
more efficient circuit constructions have benefits across these tools.
We show efficient circuit constructions for various simple but commonly
used data structures including stacks, queues, and associative
maps. While current practice requires effectively copying the entire
structure for each operation, our techniques take advantage of locality
and batching to provide amortized costs that scale polylogarithmically
in the size of the structure. We demonstrate how many common array
usage patterns can be significantly improved with the help of these
circuit structures. We report on experiments using our circuit
structures for both generic secure computation using garbled circuits
and automated test input generation using symbolic execution, and
demonstrate order of magnitude improvements for both applications.
Keywords: secure two-party computation, static circuits,
amortized analysis, privacy-preserving protocols.
Paper
Full paper (15 pages): [
PDF]
Project:
MightBeEvil.com/netlist
Code:
http://github.com/samee/netlist