Paper 2013/155

MiniLEGO: Efficient Secure Two-Party Computation From General Assumptions

Tore Kasper Frederiksen, Thomas Pelle Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt, and Claudio Orlandi

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: \begin{enumerate} \item It maintains the efficiency of the LEGO cut-and-choose. \item 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). \item On the contrary of original LEGO, MiniLEGO is compatible with all known optimization for Yao garbled gates (row reduction, free-XORs, point-and-permute). \end{enumerate}

Note: Updated accordingly to the peer feedback of the extended abstract version of this work.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Extended abstract version has been accepted at EUROCRYPT 2013
Keywords
Garbled circuitscut-and-chooseerror correcting codes
Contact author(s)
jot2re @ cs au dk
History
2013-04-29: last of 3 revisions
2013-03-15: received
See all versions
Short URL
https://ia.cr/2013/155
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/155,
      author = {Tore Kasper Frederiksen and Thomas Pelle Jakobsen and Jesper Buus Nielsen and Peter Sebastian Nordholt and Claudio Orlandi},
      title = {{MiniLEGO}: Efficient Secure Two-Party Computation From General Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/155},
      year = {2013},
      url = {https://eprint.iacr.org/2013/155}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.