Paper 2021/739
A New Approach to Garbled Circuits
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
-
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},
note = {\url{https://eprint.iacr.org/2021/739}},
url = {https://eprint.iacr.org/2021/739}
}
