Computer Science Colloquia
Monday, January 21, 2013
Samee Zahur Al Islam
Advisor: Dave Evans
Attending Faculty: Gabriel Robins (Chair), abhi shelat, Wes Weimer
3:30 PM, Rice Hall, Rm. 242
Ph.D. Quals Presentation
Circuit Structures for Improving Efficiency of Security & Privacy Tools
Several tools in computer security depend on implementing algorithms in static circuits. Such tools include generic protocols for secure computation and symbolic execution of programs. Although they have both seen rapid improvement in recent years, for most practical purposes they remain notoriously slow. They require transforming arbitrary programs into either Boolean logic circuits, constraint sets on boolean variables, or other equivalent representations. Hence, techniques for optimizing circuit constructions will have benefits across these tools.
We show efficient circuit constructions for various simple but commonly used data structures such as stacks, queues, and associative maps. While current practice requires O(n) gates per operation on all these data structures in the general case, our amortized gate count is O(log n) per operation for stacks and queues, and at most O(log^2 n) per element for batched operations on associative maps. We also show how many common array usage patterns can be significantly optimized with the help of these circuit structures. We report on experiments using our circuit structures for both generic secure computation and for symbolic execution for automated test input generation, and demonstrate order of magnitude improvements for both applications.