Paper 2018/743

On the Leakage of Corrupted Garbled Circuits

Aurélien Dupin, David Pointcheval, and Christophe Bidan


Secure two-party computation provides a way for two parties to compute a function, that depends on the two parties' inputs, while keeping them private. Known since the 1980s, Yao's garbled circuits appear to be a general solution to this problem, in the semi-honest model. Decades of optimizations have made this tool a very practical solution. However, it is well known that a malicious adversary could modify a garbled circuit before submitting it. Many protocols, mostly based on cut-&-choose, have been proposed to secure Yao's garbled circuits in the presence of malicious adversaries. Nevertheless, how much an adversary can modify a circuit and make it still executable has not been studied yet. The main contribution of this paper is to prove that any modification made by an adversary is equivalent to adding/removing NOT gates arbitrarily in the original circuit, otherwise the adversary can get caught. Thereafter, we study some evaluation functions for which, even without using cut-&-choose, no adversary can gain more information about the inputs by modifying the circuit. We also give an improvement over most recent cut-&-choose solutions by requiring that different circuits of the same function are used instead of just one.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ProvSec 2018
Garbled circuitsMalicious adversariesCorruption of garbled circuitsCut-and-choose
Contact author(s)
dupin aurelien @ gmail com
2018-08-15: received
Short URL
Creative Commons Attribution


      author = {Aurélien Dupin and David Pointcheval and Christophe Bidan},
      title = {On the Leakage of Corrupted Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2018/743},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.