Theory Seminar: Tore Frederiksen - MiniLEGO: Efficient Secure Two-Party Computation From General Assumptions
Info about event
Time
Location
Nygaard 295
Organizer
Abstract:
One of the main tools to construct secure two-party computation protocols are Yao garbled circuits. Using the cut-and-choose technique, one can get reasonably efficient Yao-based protocols with security against malicious adversaries. At TCC 2009, Nielsen and Orlandi suggested to apply cut-and-choose at the gate level, while previously cut-and-choose was applied on the circuit as a whole. This appealing idea allows for a speed up with practical significance (in the order of the logarithm of the size of the circuit) and has become known as the ``LEGO'' construction. Unfortunately the construction by Nielsen and Orlandi is based on a specific number-theoretic assumption and requires public-key operations per gate of the circuit.
The main technical contribution of this work is a new XOR-homomorphic commitment scheme based on oblivious transfer, that we use to cope with the problem of connecting the gates in the LEGO construction. Our new protocol has the following advantages:
- It maintains the efficiency of the LEGO cut-and-choose.
- After a number of seed oblivious transfers linear in the security parameter, the construction uses only primitives from Minicrypt (i.e., private-key cryptography) per gate in the circuit (hence the name MiniLEGO).
- On the contrary of original LEGO, MiniLEGO is compatible with all known optimization for Yao garbled gates (row reduction, free-XORs, point-and-permute).
Paper available at http://eprint.iacr.org/2013/155