Paper 2025/775
AuthOr: Lower Cost Authenticity-Oriented Garbling of Arbitrary Boolean Circuits
Abstract
Authenticity-oriented (previously named as privacy-free) garbling schemes of Frederiksen et al. Eurocrypt ’15 are designed to satisfy only the authenticity criterion of Bellare et al. ACM CCS ’12, and to be more efficient compared to full-fledged garbling schemes. In this work, we improve the state-of-the-art authenticity-oriented version of half gates (HG) garbling of Zahur et al. Crypto ’15 by allowing it to be bandwidth-free if any of the input wires of an AND gate is freely settable by the garbler. Our full solution AuthOr then successfully combines the ideas from information-theoretical garbling of Kondi and Patra Crypto ’17 and the HG garbling-based scheme that we obtained. AuthOr has a lower communication cost (i.e. garbled circuit or GC size) than HG garbling without any further security assumption. Theoretically, AuthOr’s GC size reduction over HG garbling lies in the range between 0 to 100%, and the exact improvement depends on the circuit structure. We have implemented our scheme and conducted tests on various circuits that are constructed by independent researchers. Our experimental results show that in practice, the GC size gain may be up to roughly 98%.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Garbled circuitsPrivacy-free garblingVerifiable computingZero-knowledge proofs
- Contact author(s)
-
osman bicer @ unibas ch
ali ajorian @ unibas ch - History
- 2025-04-30: approved
- 2025-04-30: received
- See all versions
- Short URL
- https://ia.cr/2025/775
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2025/775,
author = {Osman Biçer and Ali Ajorian},
title = {{AuthOr}: Lower Cost Authenticity-Oriented Garbling of Arbitrary Boolean Circuits},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/775},
year = {2025},
url = {https://eprint.iacr.org/2025/775}
}
