Paper 2023/530

Breaking and Fixing Garbled Circuits when a Gate has Duplicate Input Wires

Raine Nieminen, Technical University of Darmstadt
Thomas Schneider, Technical University of Darmstadt

Garbled circuits are a fundamental cryptographic primitive that allows two or more parties to securely evaluate an arbitrary Boolean circuit without revealing any information beyond the output using a constant number of communication rounds. Garbled circuits have been introduced by Yao (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several implementations exist. Starting with the seminal Fairplay compiler (USENIX Security’04), several implementation frameworks decoupled the task of compiling the function to be evaluated into a Boolean circuit from the engine that securely evaluates that circuit, e.g., using a secure two-party computation protocol based on garbled circuits. In this paper, we show that this decoupling of circuit generation and evaluation allows a subtle attack on several prominent garbling schemes. It occurs when violating the implicit assumption on the circuit that gates have different input wires which is most often not explicitly specified in the respective papers. The affected garbling schemes use separate calls to a deterministic encryption function for the left and right input wire of a gate to derive pseudo-random encryption pads that are XORed together. When a circuit contains a gate where the left and right input wire are the same, these two per-wire encryption pads cancel out and we demonstrate that this can result in a complete break of privacy. We show how the vulnerable garbling schemes can be fixed easily.

Note: Clarifying relation to the attack in the paper by Bellare, Hoang, Keelveedhi, and Rogaway (IEEE S&P’13). Thanks to Claudio Orlandi for pointing us to this.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in JOC 2023
Secure Multi-Party ComputationGarbled CircuitsGarbling SchemesCircuitsAttackVulnerability
Contact author(s)
nieminen @ encrypto cs tu-darmstadt de
schneider @ encrypto cs tu-darmstadt de
2023-07-06: last of 2 revisions
2023-04-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Raine Nieminen and Thomas Schneider},
      title = {Breaking and Fixing Garbled Circuits when a Gate has Duplicate Input Wires},
      howpublished = {Cryptology ePrint Archive, Paper 2023/530},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.