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

Cited in 1 Serial

1 Journal of Cryptology

Citations by Year