Paper 2021/739

A New Approach to Garbled Circuits

Anasuya Acharya, Bar-Ilan University
Tomer Ashur, imec-COSIC, KU Leuven
Efrat Cohen, Bar-Ilan University
Carmit Hazay, Bar-Ilan University
Avishay Yanai, VMware Research

A garbling scheme is a fundamental cryptographic building block with a long list of applications. The study of different techniques for garbling a function, towards optimizing computation and communication complexity, has been an area of active research. Most common garbling techniques work by representing each gate in the circuit as a set of ciphertexts that encrypt its truth table row-by-row. In this work we present a new garbling scheme in the random oracle (RO) model that garbles circuits in the gate-by-gate paradigm by capturing the gate functionality (AND, XOR) as a whole rather than as a set of ciphertexts. The final gate garbling requires $4\kappa$ bits of communication in expectation, 4 RO calls for garbling and 1 RO call for evaluation. We prove that the scheme satisfies privacy in the non-programmable random oracle model and against PPT adversaries. We also show how this scheme can be extended to support free-XOR and garble any gate functionality over binary inputs.

Available format(s)
Publication info
Published elsewhere. ACNS2023
Garbled CircuitsGate-by-Gate GarblingRandom OracleFree-XOR
Contact author(s)
acharya @ biu ac il
tomer ashur @ esat kuleuven be
efrat choen @ biu ac il
carmit hazay @ biu ac il
yanaia @ vmware com
2023-04-05: last of 3 revisions
2021-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anasuya Acharya and Tomer Ashur and Efrat Cohen and Carmit Hazay and Avishay Yanai},
      title = {A New Approach to Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2021/739},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.