AuthOr: Lower Cost Authenticity-Oriented Garbling of Arbitrary Boolean Circuits

Osman Biçer, Ali Ajorian · 2025

Read AuthOr: Lower Cost Authenticity-Oriented Garbling of Arbitrary Boolean Circuits by Osman Biçer, Ali Ajorian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18387.txt.

Introduction

Osman Biçer and Ali Ajorian shrink encrypted circuits when only honesty, not secrecy, must be guaranteed in this 2025 cryptography paper. Garbled circuits let one party compute on another's input; privacy-free versions drop confidentiality and keep tamper evidence, cutting cost. Their scheme improves a known half-gates method.

Whenever the garbler can freely set one input of an AND gate, that gate now needs no ciphertext at all. Merged with an information-based method, the full scheme, AuthOr, beats the older design's message size by up to nearly all of it on some circuits, with no new assumptions. Tests on circuits built by other groups confirmed savings reaching about 98 percent.

Catalog record

CREATOROsman Biçer, Ali Ajorian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-18387

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

AuthOr: Lower Cost Authenticity-Oriented Garbling of Arbitrary Boolean Circuits Osman Biçer, Ali Ajorian 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%. 1 Introduction Garbled circuits. Introduced by Andrew Yao [ 35 ] , garbled circuits are an essential field of study in cryptography with applications to secure two-party computation [ 36 , 25 , 26 , 28 ] , secure multi-party computation [ 27 , 34 ] , identity-based encryption [ 12 ] , verifiable oursourced computing [ 15 , 30 ] , and zero-knowledge protocols [ 19 , 13 , 10 , 24 , 14 ] . In its generic form, a garbled circuit (GC) protocol is a two-party protocol with a garbler party and an evaluator party, such that the former garbles a boolean circuit f known to both parties and the latter evaluates it on encoded inputs to obtain encoded outputs. Classically, the garbling procedure involves assigning two \ell -bit keys 1 1 1 Throughout this work, \ell\in O(\lambda) is the key size based on the security parameter \lambda . W_{i}^{0} and W_{i}^{1} to each wire i for truth values 0 and 1 to generate the garbled circuit \hat{F} . The evaluator then obtains \hat{F} and each key W_{i} for the truth value w_{i} of the circuit input wire i . The evaluator proceeds in topological order gate-by-gate to obtain the key W_{i} for each circuit output wire i by using \hat{F} . [ 7 ] formalized the garbled circuits as a cryptographic primitive with three security notions, privacy, obliviousness, and authenticity . While privacy and obliviousness are concerned with keeping as secret the wires’ truth values from the evaluator, authenticity prevents the evaluator from forging the encodings of “fake” outputs that are not obtained by honestly evaluating the garbled circuit. The efficiency of a garbled circuit is often determined by three metrics, composed of the computation overheads to the garbler and the evaluator, and the size of the garbled circuit. The latter is considered the main bottleneck [ 37 ] in many applications as it directly affects the bandwidth overhead. Authenticity-oriented (privacy-free) garbling 2 2 2 We use “authenticity-oriented” instead of the previous naming “privacy-free” to focus on what these protocols achieve instead of what they do not. [ 13 ] showed that authen-ticity-oriented garbling schemes without the privacy and the obliviousness properties can be significantly more efficient than fully-fledged schemes. Their idea is that when the evaluator knows the truth values w_{a} and w_{b} , it can use them in the evaluation algorithm reducing the overheads. These schemes are useful for verifiable outsourced computation [ 15 , 30 ] and for efficient zero-knowledge proof protocols [ 19 , 13 , 10 , 24 , 14 ] . The latter application requires an additional verifiability property, to ensure that a verifier cannot maliciously construct a garbled circuit whose output keys may reveal the prover’s input bits, which correspond to the prover’s witness. There is a quest for achieving an optimal authenticity-oriented garbling scheme. Previous works include the authenticity-oriented schemes by [ 13 ] , i.e., GRR2 (compatible with FreeXOR), GRR1, and GRR1 with FleXOR. The most relevant techniques to our work are the authenticity-oriented version of half gates (HG) garbling [ 37 ] and the information-theoretical (IT) garbling [ 24 ] . If the circuit is a boolean formula, i.e., it consists of only fan-out 1 gates, IT garbling is optimal with a garbled circuit of size zero and no cryptographic operations. Although boolean formulas are already an important class of circuits with zero-knowledge proof of satisfiability applications [ 16 ] , this is still quite restrictive. According to the Shannon bound [ 33 , 5 ] , the great majority of circuits with n input bits have size \Theta(2^{n}/n) , whereas a boolean formula with n input bits can have a size O(n) . For fairness, we converted an example generic circuit into a boolean formula (see Appendix 0.A ), which resulted in a circuit with a size exponential in the size of the original circuit, implying that both garbling and evaluating have exponential complexity 3 3 3 The authors also acknowledge this as “not generally efficient for circuits that are not largely formulaic” in [ 24 ] . . To the best of our knowledge, before this work, HG garbling has remained the most efficient authenticity-oriented garbling scheme applicable to all boolean circuits. Our contributions. We provide a novel authenticity-oriented garbling scheme that is FreeXOR compatible and has lower AND gate costs than HG garbling. Our technique benefits from the incorporation of IT garbling and a more efficient version of HG garbling that we also propose here. More concretely, here we achieve the following: 1. In Section 3 , along with the previously developed garbling schemes that we use in our final solution, we propose an HG-based AND gate garbling scheme that is FreeXOR compatible. This scheme allows the garbler to garble an AND gate with 0 ct if one of the gate input wires is not already set by another gate that comes before it in topological order. 2. In Section 4 , we combine the scheme that we mentioned in the previous step with IT garbling to obtain our final authenticity-oriented garbling scheme AuthOr. The garbling \mathsf{Gb} algorithm of Author detects based on which gate garbling suits better for each gate and benefits from IT garbling and our proposal from the previous step as much as possible, while the evaluation algorithm \mathsf{Ev} detects for each gate which gate garbling is used and proceeds accordingly. Theoretically, for any circuit, compared to HG garbling AuthOr achieves: (i) The same computational security guarantee based on circular correlation robustness (CCR) of the hash function, (ii) 0 to 100% reduced garbled circuit size, and (iii) 0 to 100% less hash function computations for both garbler and evaluator. The exact improvement depends on the circuit. 3. In Section 5 , we provide our implementation results for both our scheme and HG garbling by testing those schemes on the boolean circuits available on [ 4 , 20 ] . While for the cryptographic circuits our efficiency improvement can be considered

Read the complete text