MiniLEGO swMATH ID: 9866 Software Authors: Frederiksen, Tore Kasper; Jakobsen, Thomas Pelle; Nielsen, Jesper Buus; Nordholt, Peter Sebastian; Orlandi, Claudio Description: 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 [28] 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 [28] 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). Homepage: http://link.springer.com/chapter/10.1007%2F978-3-642-38348-9_32 Related Software: TinyLEGO; FleXOR; TASTY; EMP-toolkit; JustGarble; VMCrypt; FairplayMP; VIFF; GraphSC; ObliVM; JIMU; GitHub; RELIC; MinT Cited in: 13 Publications all top 5 Cited by 31 Authors 6 Nielsen, Jesper Buus 3 Orlandi, Claudio 2 Frederiksen, Tore Kasper 2 Jakobsen, Thomas Pelle 2 Nordholt, Peter Sebastian 1 Brandão, Luís T. A. N. 1 Burra, Sai Sheshank 1 Cascudo, Ignacio 1 Damgård, Ivan Bjerre 1 David, Bernardo Machado 1 Döttling, Nico 1 Hazay, Carmit 1 Huang, Yan 1 Katz, Jonathan N. 1 Kempka, Carmen 1 Kikuchi, Ryo 1 Larraia, Enrique 1 Lindell, Yehuda 1 Malozemoff, Alex J. 1 Mohassel, Payman 1 Orsini, Emmanuela 1 Ranellucci, Samuel 1 Riva, Ben 1 Rosulek, Mike 1 Scholl, Peter 1 Smart, Nigel Paul 1 Suzuki, Koutarou 1 Trifiletti, Roberto 1 Venkitasubramaniam, Muthuramakrishnan 1 Wang, Xiao 1 Zhu, Ruiyu Cited in 1 Serial 1 Journal of Cryptology Cited in 2 Fields 13 Information and communication theory, circuits (94-XX) 2 Computer science (68-XX) Citations by Year