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).

References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Burra, Sai Sheshank; Larraia, Enrique; Nielsen, Jesper Buus; Nordholt, Peter Sebastian; Orlandi, Claudio; Orsini, Emmanuela; Scholl, Peter; Smart, Nigel P.: High-performance multi-party computation for binary circuits based on oblivious transfer (2021)
  2. Hazay, Carmit; Venkitasubramaniam, Muthuramakrishnan: Scalable multi-party private set-intersection (2017)
  3. Mohassel, Payman; Rosulek, Mike: Non-interactive secure 2PC in the offline/online and batch settings (2017)
  4. Wang, Xiao; Malozemoff, Alex J.; Katz, Jonathan: Faster secure two-party computation in the single-execution setting (2017)
  5. Zhu, Ruiyu; Huang, Yan: JIMU: faster LEGO-based secure computation using additive homomorphic hashes (2017)
  6. Cascudo, Ignacio; Damgård, Ivan; David, Bernardo; Döttling, Nico; Nielsen, Jesper Buus: Rate-1, linear time and additively homomorphic UC commitments (2016)
  7. Frederiksen, Tore Kasper; Jakobsen, Thomas P.; Nielsen, Jesper Buus; Trifiletti, Roberto: On the complexity of additively homomorphic UC commitments (2016)
  8. Kempka, Carmen; Kikuchi, Ryo; Suzuki, Koutarou: How to circumvent the two-ciphertext lower bound for linear garbling schemes (2016)
  9. Nielsen, Jesper Buus; Orlandi, Claudio: Cross and clean: amortized garbled circuits with constant overhead (2016)
  10. Nielsen, Jesper Buus; Ranellucci, Samuel: Reactive garbling: foundation, instantiation, application (2016)
  11. Lindell, Yehuda; Riva, Ben: Cut-and-choose yao-based secure computation in the online/offline and batch settings (2014)
  12. 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)
  13. Frederiksen, Tore Kasper; Jakobsen, Thomas Pelle; Nielsen, Jesper Buus; Nordholt, Peter Sebastian; Orlandi, Claudio: MiniLEGO: efficient secure two-party computation from general assumptions (2013)