Minilego: efficient secure two-party computation from general assumptions. 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 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 in  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:par 1 It maintains the efficiency of the LEGO cut-and-choose.par 2 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).par 3 MiniLEGO is compatible with all known optimization for Yao garbled gates (row reduction, free-XORs, point-and-permute).
Keywords for this software
References in zbMATH (referenced in 11 articles )
Showing results 1 to 11 of 11.
- Hazay, Carmit; Venkitasubramaniam, Muthuramakrishnan: Scalable multi-party private set-intersection (2017)
- Mohassel, Payman; Rosulek, Mike: Non-interactive secure 2PC in the offline/online and batch settings (2017)
- Wang, Xiao; Malozemoff, Alex J.; Katz, Jonathan: Faster secure two-party computation in the single-execution setting (2017)
- Cascudo, Ignacio; Damgård, Ivan; David, Bernardo; Döttling, Nico; Nielsen, Jesper Buus: Rate-1, linear time and additively homomorphic UC commitments (2016)
- Frederiksen, Tore Kasper; Jakobsen, Thomas P.; Nielsen, Jesper Buus; Trifiletti, Roberto: On the complexity of additively homomorphic UC commitments (2016)
- Kempka, Carmen; Kikuchi, Ryo; Suzuki, Koutarou: How to circumvent the two-ciphertext lower bound for linear garbling schemes (2016)
- Nielsen, Jesper Buus; Orlandi, Claudio: Cross and clean: amortized garbled circuits with constant overhead (2016)
- Nielsen, Jesper Buus; Ranellucci, Samuel: Reactive garbling: foundation, instantiation, application (2016)
- Lindell, Yehuda; Riva, Ben: Cut-and-choose yao-based secure computation in the online/offline and batch settings (2014)
- Brandão, Luís T.A.N.: Secure two-party computation with reusable bit-commitments, via a cut-and-choose with forge-and-lose technique (extended abstract) (2013)
- Frederiksen, Tore Kasper; Jakobsen, Thomas Pelle; Nielsen, Jesper Buus; Nordholt, Peter Sebastian; Orlandi, Claudio: MiniLEGO: efficient secure two-party computation from general assumptions (2013)