1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 Department of Computer Science, Science and Technology, Aarhus University
This paper continues the recent line of work of making Yao’s garbled circuit approach to two-party computation secure against an active adversary. We propose a new cut-and-choose based approach called LEGO (Large Efficient Garbled-circuit Optimization): It is specifically aimed at large circuits. Asymptotically it obtains a factor improvement in computation and communication over previous cut-and-choose based solutions, where is the size of the circuit being computed. The protocol is universally composable (UC) in the OT-hybrid model against a static, active adversary.
Lecture Notes in Computer Science, 2009, Vol 5444, p. 368-386