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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. ACNS2023
Keywords
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
History
2023-04-05: last of 3 revisions
2021-06-03: received
See all versions
Short URL
https://ia.cr/2021/739
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/739,
      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},
      url = {https://eprint.iacr.org/2021/739}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.