Paper 2017/226

JIMU: Faster LEGO-based Secure Computation using Additive Homomorphic Hashes

Ruiyu Zhu and Yan Huang


LEGO-style cut-and-choose is known for its asymptotic efficiency in realizing actively-secure computations. The dominant cost of LEGO protocols is due to wire-soldering — the key technique enabling to put independently generated garbled gates together in a bucket to realize a logical gate. Existing wire-soldering constructions rely on homomorphic commitments and their security requires the majority of the garbled gates in every bucket to be correct. In this paper, we propose an efficient construction of LEGO protocols that does not use homomorphic commitments but is able to guarantee security as long as at least one of the garbled gate in each bucket is correct. Additionally, the faulty gate detection rate in our protocol doubles that of the state-of-the-art LEGO constructions. With moderate additional cost, our approach can even detect faulty gates with probability 1, which enables us to run cut- and-choose on larger circuit gadgets rather than individual AND gates. We have implemented our protocol and our experiments on several benchmark applications show that the performance of our approach is highly competitive in comparison with existing implementations.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in ASIACRYPT 2017
maliciously secure two-party computation
Contact author(s)
yh33 @ indiana edu
2017-10-06: last of 5 revisions
2017-03-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ruiyu Zhu and Yan Huang},
      title = {{JIMU}: Faster {LEGO}-based Secure Computation using Additive Homomorphic Hashes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/226},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.