# $\omega(1/\lambda)$-Rate Boolean Garbling Scheme from Generic Groups

Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar

► To cite this version:

Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar. $\omega(1/\lambda)$-Rate Boolean Garbling Scheme from Generic Groups. CRYPTO 2025, Aug 2025, Santa Barbara, United States. pp.489-521, 10.1007/978-3-032-01884-7_16. hal-05376902

HAL Id: hal-05376902

https://hal.science/hal-05376902v1

Submitted on 21 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# $\omega(1/\lambda)$-Rate Boolean Garbling Scheme from Generic Groups

Geoffroy Couteau

Carmit Hazay

Aditya Hegde

Université Paris Cité, CNRS, IRIF

Bar-Ilan University

Johns Hopkins University

Naman Kumar

Oregon State University

## Abstract

Garbling schemes are a fundamental cryptographic tool for enabling private computations and ensuring that nothing leaks beyond the output. As a widely studied primitive, significant efforts have been made to reduce their size. Until recently, all such schemes followed the Lindell and Pinkas paradigm for Boolean circuits (JoC 2009), where each gate is represented as a set of ciphertexts computed using only symmetric-key primitives. However, this approach is inherently limited to $O(\lambda)$ bits per gate, where $\lambda$ is the security parameter. Recently, it has been shown that achieving smaller garbled circuit size is possible under stronger assumptions, such as variants of Learning with Errors (LWE) or Indistinguishability Obfuscation (iO). In addition to requiring high-end cryptography, none of these constructions is black-box in the underlying cryptographic primitives, a key advantage of prior work. In this paper, we present the first approach to garbling Boolean circuits that makes a black-box use of a group and uses $o(\lambda)$ bits per gate.

Building on a novel application of the Reverse Multiplication-Friendly Embeddings (RMFE) paradigm (Cascudo et al., CRYPTO 2018), we introduce a new packing mechanism for garbling schemes, that packs boolean values into integers and leverage techniques for arithmetic garbling over integer rings. Our results introduce two new succinct schemes that achieve improved rates by a factor of $\sqrt{\log \lambda}$, retaining the black-box usage. (1) Our first scheme is proven in the Generic Group model (GGM) for circuits with $\Omega(\sqrt{\log \lambda})$ width, obtaining a garbled circuit size of $\lambda \cdot |C|/\sqrt{\log(\lambda)}$. (2) Our second scheme is proven in the plain model under the Power-DDH assumption, attaining a garbled circuit size of $\lambda \cdot (|C|/\sqrt{\log(\lambda)} + \text{poly}(\lambda) \cdot \text{depth}(C))$, but is restricted to layered circuits. *Our schemes are the first to achieve sublinear (in $\lambda$) cost per gate under assumptions that do not imply fully homomorphic encryption;* in addition, our scheme is also the first to achieve this while making a black-box use of cryptography.

## 1 Introduction

Garbling schemes [Yao86, LP09] are a cryptographic object that enables the oblivious evaluation of computations, ensuring that nothing beyond the output is revealed from the computation's flow. This strong privacy guarantee has established garbling schemes as a fundamental cryptographic tool with a wide range of applications. One of their most prominent applications is in secure two-party computation. In this setting, a garbler creates an encoded version of the function along with encoded inputs. It provides these to an evaluator, who privately evaluates the encoded computation and learns only the output. The correctness property of the garbling scheme guarantees that the right output is obtained. The ability to implement garbling schemes using only symmetric-key cryptography, combined with the garbling algorithm's depth complexity independent of the computed circuit's depth complexity, has made them a highly competitive technique for achieving constant round secure computation.
Since their introduction by Yao [Yao86] and formalization by Lindell and Pinkas [LP09], extensive research has focused on understanding the concrete efficiency of Boolean circuit garbling, e.g., [KS08, PSSW09, KMR14, ZRE15, RR21]. Building on the gate-by-gate approach introduced in [LP09], this research culminated in achieving 1.5 times $\lambda$ bits per AND gate [RR21], with no communication cost for XOR gates [KS08], where $\lambda$ is the security parameter. This resulted in an $O(\lambda)$ inflation between the circuit representation $C$ and the length of the garbled circuit $\hat{C}$. An important feature of this line of work is the black-box access to the underlying symmetric-key primitive. This abstraction treats cryptographic operations as an oracle, allowing them to be instantiated with a pseudorandom function (PRF) or a hash function, resulting in highly practical schemes.

Using black-box access to the underlying cryptographic primitive allows for a modular design approach, ensuring that the constructions remain independent of specific implementations and rely only on the input-output behavior of the primitive. This flexibility allows for improved instantiations under different hardness assumptions. As a result, the construction of black-box schemes is both theoretically appealing and practically beneficial and has therefore been extensively studied with the goal of understanding its power and limitations; see [DI05, PW09, HIMV19, IKSS22] for a few examples. This feature is also at the focus of our work.

Attempts to explore the limitations of these constructions have provided evidence that current techniques have reached their limits, suggesting that breaking these barriers will require entirely new approaches [ZRE15]. The source of this limitation lies in the technique from [LP09], which assigns two labels to each wire and treats each gate as a set of four ciphertexts encrypting the labels associated with the output wire. Since each label functions as a key to the symmetric-key primitive, its length must scale with the security parameter to maintain privacy; otherwise, the scheme's security would be compromised. Therefore, the question of reducing the rate, the ratio between $C$ and $\hat{C}$, while basing security only on symmetric key primitives, remained unresolved until recently.

A recent and exciting result by Liu et al. [LWYY24] presents the first rate-1 Boolean garbling scheme based on the Ring Learning with Errors (RLWE) or NTRU assumption, leveraging these to define a somewhat homomorphic encryption scheme. This encryption scheme is used to evaluate a low-depth pseudorandom generator (PRG) seed, which is subsequently used to derive the garbling material for each gate. The ciphertext is then decrypted using a key-dependent message (KDM)-secure encryption scheme. The bulk of the computational complexity arises from homomorphically evaluating the PRG seed, necessitating the use of a low-depth PRG. Additionally, the scheme is inherently non-black-box in its reliance on the details of the underlying PRG construction.

Leveraging stronger primitives allows for improved garbling schemes using laconic function evaluation (LFE), a dual primitive to fully homomorphic encryption (FHE), achieving sublinear rates, dependent on circuit depth, based on LWE or subexponential indistinguishability obfuscation (iO). This is done by adding a garbling layer on top of the LFE protocol, garbling the LFE encoding function. The combination of LFE's succinctness and the privacy of garbling results in a succinct garbling scheme. Recent advancements in LFE [DGM23] eliminate the dependency on the circuit's depth. This is achieved through standard (polynomially secure) iO and somewhere statistically binding (SSB) hash functions, instantiated from various number-theoretic assumptions. In another recent work [HLL23], Hsieh et al. introduced a compact reusable garbling scheme based on a new circular-secure variant of LWE. Unlike previous constructions, which are limited to one-time use, their approach enables multiple uses, making it a stronger form of garbling. Finally, succinct randomized encoding for Turing machines [BGL+15], based on iO for P/poly and one-way functions, grows only polylogarithmically with the program's running time. However, extending this technique to a circuit representation of the computed function remains unclear. In Table 1, we
summarize the current landscape of Boolean garbling schemes.

<table><thead><tr><th>Ref.</th><th>|Ĉ|</th><th>Hardness Assumption</th><th>Black-Box</th></tr></thead><tbody><tr><td>[ZRE15]</td><td>2λ · |C|</td><td>RO / RTCCR</td><td>✓</td></tr><tr><td>[RR21]</td><td>1.5λ · |C|</td><td>RO / RTCCR</td><td>✓</td></tr><tr><td>[QWW18]</td><td>poly(λ) · depth(C)</td><td>LWE / Subexponential iO</td><td>✗</td></tr><tr><td>[DGM23]</td><td>poly(λ)</td><td>iO + SSB</td><td>✗</td></tr><tr><td>[HLL23]</td><td>poly(λ)</td><td>circular LWE<fnref n="1" /></td><td>✗</td></tr><tr><td>[LWYY24]</td><td>(1 + o(1)) · |C|</td><td>RLWE / NTRU</td><td>✗</td></tr><tr><td>This Work</td><td>λ · O(|C|)/√log(λ) + poly(λ)</td><td>GGM / ap-eTCCR<fnref n="3" /></td><td>✓</td></tr><tr><td>This Work<fnref n="2" /></td><td>λ · O(|C|)/√log(λ) + poly(λ) · depth(|C|)</td><td>Power-DDH + eTCR<fnref n="4" /></td><td>✓</td></tr></tbody></table>

<caption>Table 1: The landscape of garbling schemes for Boolean circuits.</caption>

As it stands today, our understanding of Boolean garbling schemes with $\omega(1/\lambda)$ rates, based on assumptions that do not imply FHE, remains highly limited, even without the black-box requirement. This paper seeks to advance research in this direction by presenting two new sublinear-rate schemes that are black-box in their use of cryptographic primitives and rely on group-based assumptions for security, reducing the gap toward existing non-succinct schemes.

It is worth noting that when going beyond Boolean computations into the arithmetic regimes, the problem becomes simpler for the bounded setting, where the computation is performed over the integers while a bound $B$ bounds the length of the wire values [BLLL23, MORS24, CHHK25]. This simplification arises from using stronger (non-symmetric-key) tools such as constant-rate additive encryption schemes or Homomorphic Secret Sharing (HSS). Specifically, the gap between the plain and the encoded data becomes smaller for larger computation domains, facilitating the construction of primitives with smaller rates. Our techniques are inspired by this sequence of works for designing arithmetic garbling [BLLL23, MORS24, CHHK25], building on [AIK11]. In particular, we demonstrate that the techniques developed in [CHHK25] can also be applied to Boolean circuits when packing the gates into batches of size $\sqrt{\log \lambda}$. Our packing mechanism is based on a novel application of the Reverse Multiplication-Friendly Embeddings (RMFE) paradigm from [CCXY18] that supports computations over tuples of binary values, where addition and multiplication are performed coordinate-wise, to be embedded into computations over an extension field. This technique has previously been only used in secure multi-party computation (MPC) e.g., [CG20, PS21, EHL$^{+}$23], which is inherently interactive. To the best of our knowledge, our work is the first to apply RMFE-based embedding techniques to garbling schemes, which are non-interactive primitives.

More concretely, our first construction is proven under an assumption that is reminiscent of the Tweakable Circular Correlation Robust (TCCR) assumption used in [RR21] except that it considers exponential correlations [BCM$^{+}$24, CHHK25] (namely, $s^x$ where $s \in \mathbb{G}$ and $x \in \mathbb{Z}_{\text{ord}(\mathbb{G})}$). We prove our construction in the generic group model (GGM) and the random oracle. Given that the random oracle can be instantiated in the GGM setting, our result presents the first succinct garbling scheme in the GGM model that retains

<footnote n="1">¹ Requires a new circular variant of LWE.</footnote>

<footnote n="2">² Restricted to layered circuits.</footnote>

<footnote n="3">³ ap-eTCCR stands for Tweakable Circular Correlation Robustness for exponential correlations with auxiliary powers.</footnote>

<footnote n="4">⁴ eTCR stands for Tweakable Correlation Robustness for exponential correlations.</footnote>
black-box usage, reducing the garbling size by a factor of $O(\sqrt{\log(\lambda)})$. This scheme is proven for circuits that are not too narrow, requiring a width of $\sqrt{\log(\lambda)}$, a milder restriction than prior MPC work, which requires in some settings greater width to support packed secret sharing or is restricted to SIMD circuits<fnref n="1" />. Informally, we prove that,

**Theorem 1 (Informal).** In the generic group model, there exists a Boolean garbling scheme GC that garbles any Boolean circuit C into a garbling $\hat{C}$ such that

$$|\hat{C}| = \frac{\lambda}{\sqrt{\log(\lambda)}} \cdot O(|C|) + \text{poly}(\lambda).$$

Our second construction is proven in the standard model under the power-DDH hardness assumption together with the existence of tweakable correlation robust hash functions for a family of exponential correlations, which implies a layered version of the TCCR assumption. This variant applies to layered circuits, where the gate set is partitioned into D levels such that gates at level i receive inputs from level i - 1. Such circuits have been previously studied in the context of HSS [BGI16] and shown to be effective in overcoming communication barriers. Informally, we prove that.

**Theorem 2 (Informal).** If there exists a TCR hash for the exponential correlation with respect to a group over which the power-DDH assumption holds, then there exists a Boolean garbling scheme that garbles layered circuits C into a garbling $\hat{C}$ such that

$$|\hat{C}| = \frac{\lambda}{\sqrt{\log(\lambda)}} \cdot O(|C|) + \text{poly}(\lambda) \cdot \text{depth}(C).$$

# 2 Technical Overview

## 2.1 Overview of [CHHK25]

Our starting point is the recent work of [CHHK25], that described the first construction (without resorting to FHE or iO) of a garbling scheme for arithmetic circuits over a small (polynomial) integer ring $\mathbb{Z}_B$ with $O(\lambda)$ bits per gate (independently of B). At the heart of their construction are two efficient one-round protocols for computing on authenticated shares.

Concretely, fix a group $\mathbb{G}$ of prime order p with $|p| = O(\lambda)$ and assume that the following assumption holds: pick a random (secret) $h \leftarrow \mathbb{G}$, a secret exponent $\alpha \leftarrow \mathbb{Z}_p$, and compute $h^{\alpha^i}$ for all nonzero i from $-B$ to B. Then no efficient adversary should, given these values, be able to distinguish h from random. Under this variant of the power-DDH assumption, [CHHK25] showed the following:

**Lemma 3 (informal).** Let G and E be two parties holding additive shares of $\Delta \cdot x$ over $\mathbb{Z}_{p-1}$, where $\Delta$ is a random MAC key (from $\mathbb{Z}_{p-1}$) known to G, and $x \in \{0, \dots, B\}$ is a value known to E. Fix any (public) function $f: \{0, \dots, B\} \to \mathbb{Z}_{p-1}$. Then there exists a one-message secure protocol where G, holding an input $y \in \mathbb{Z}_{p-1}$, sends $O(\lambda)$ bits to E, and both parties obtain additive shares of $y \cdot f(x) \bmod p - 1$.

Let us overview briefly how [CHHK25] uses this protocol to garbled a circuit C over $\mathbb{Z}_B$. The parties always maintain the following invariant: for any gate u of C carrying a value $x_u$ during the computation of C on an input x, the parties will hold

<footnote n="1">¹Circuits that possess multiple repetitions of smaller subcircuits.</footnote>
• shares $k_u$, $\ell_u$ of $x_u$ over $B$ ($\ell_u \in \{0, \dots, B\}$ is E's share), and

• shares $K_u$, $L_u$ of $\Delta \cdot \ell_u$ over $\mathbb{Z}_{p-1}$.

Now, let us look at a multiplication gate $w$ (additions are simpler). Let $x_u$ and $x_v$ denote the values on the wires entering the gate, with respective garbler shares (the keys) $(k_u, K_u)$, $(k_v, K_v)$ and evaluator shares (the labels) $(\ell_u, L_u)$, $(\ell_v, L_v)$. We have:

$$x_u x_v = k_u k_v + \ell_u \ell_v + k_u \ell_v + k_v \ell_u.$$

Above, the values in blue are known to one party and can be locally added to their share; the important terms are the cross terms in red. Given that they hold (by assumption) shares of $\Delta \cdot \ell_u$ and of $\Delta \cdot \ell_v$, the parties will simply use two invocations of the protocol from Lemma 3 (setting $f$ to the identity function). The two messages from $G$ will be part of the garbling material attached to this gate in the garbled circuit. Let us write $(\langle k_u \ell_v \rangle_G, \langle k_v \ell_u \rangle_G)$ and $(\langle k_u \ell_v \rangle_E, \langle k_v \ell_u \rangle_E)$ the shares obtained by $G$ and $E$ respectively. We define

$$k_w := \langle k_u \ell_v \rangle_G + \langle k_v \ell_u \rangle_G + k_u k_v$$

$$\ell_w := \langle k_u \ell_v \rangle_E + \langle k_v \ell_u \rangle_E + \ell_u \ell_v.$$

We now turn our attention to the task of building shares of $\Delta \cdot \ell_w$. We have

$$\begin{aligned}
\Delta \cdot \ell_w &= \Delta \cdot (\langle k_u \ell_v \rangle_E + \langle k_v \ell_u \rangle_E + \ell_u \ell_v) \\
&= \Delta \cdot (k_u \ell_v - \langle k_u \ell_v \rangle_G + k_v \ell_u - \langle k_v \ell_u \rangle_G) + (K_u + L_u) \ell_v \\
&= (\Delta k_u) \cdot \ell_v + (\Delta k_v) \cdot \ell_u + K_u \cdot \ell_v + L_u \ell_v - \Delta \cdot (\langle k_u \ell_v \rangle_G + \langle k_v \ell_u \rangle_G),
\end{aligned}$$

where again the terms in blue are known to one of the parties, while the terms in red are the product of a value known to $G$ with a value in $\{0, \dots, B\}$ ($\ell_u$ or $\ell_v$) known to $E$. Hence, these three cross terms are shared using three more instances of the protocol of Lemma 3. Then, $G$ defines $K_w$ as the sum of the shares of these cross terms minus $\Delta \cdot (\langle k_u \ell_v \rangle_G + \langle k_v \ell_u \rangle_G)$, and $E$ defines $L_w$ as the sum of its shares plus $L_u \ell_v$, giving $K_w + L_w = \Delta \cdot \ell_w$, as required.

This overview overlooks important technicalities, which we briefly sketch as they will also show up in our work. First, there is a size issue: the value $\ell_w$ computed above does not belong to $\{0, \dots, B\}$, which is crucial (otherwise, $\ell_w$ cannot be used as input in the protocol of Lemma 3). Of course, a simple fix is to reduce it modulo $B$ (it is not too hard to guarantee that the shares of the cross terms are shares over the integers). The problem is that now, denoting $\tilde{\ell}_w$ the original value (before reduction modulo $B$) and $\ell_w = [\tilde{\ell}_w \mod B]$ the reduced value, we have a modulus mismatch: $K_w, L_w$ form shares of $\Delta \cdot \tilde{\ell}_w$, while we need them to form shares of $\Delta \cdot \ell_w = \Delta \cdot [\tilde{\ell}_w \mod B]$.

This is where the protocol of Lemma 3 comes to the rescue: the parties will use one last invocation of this protocol, where $E$ inputs $\tilde{\ell}_w$ and $G$ inputs $\Delta$, setting $f$ to be the function “reduction mod $B$”, to obtain shares of $\Delta \cdot f(\tilde{\ell}_w) = \Delta \cdot \ell_w$. However, for this to work, we crucially need $\tilde{\ell}_w$ to be small in the first place! In [CHHK25], this is solved by introducing a (more complex) variant of the protocol that guarantees that the shares of $k_u \ell_v$ and $k_v \ell_u$ are actually small integers (roughly bounded by $B^3$). This requires care, as $G$'s message will now contain its input (say, $k_u$) masked over the integers by small values, which introduces some leakage on $k_u$. A core technical contribution of [CHHK25] is a way to add a carefully crafted noise to $k_u$ to guarantee that the leakage remains harmless with overwhelming probability while letting the function $f$ evaluated on $\tilde{\ell}_w$ remove the noise in the end.
## 2.2 Computing on Batches via RMFE

Unfortunately, the methodology of [CHHK25] does not improve over traditional garbling schemes (such as Yao's) when the ring is $\mathbb{Z}_2$, since it still requires $\Omega(\lambda)$ bits for each gate of the circuit. To improve the garbled circuit size over $\mathbb{Z}_2$, our high-level approach is the following: we devise a methodology to *pack* the bits carried on multiple values into a single element of a larger ring, and rely on the approach of [CHHK25] to operate on these “packed ring elements”. Then, to ensure that the computation proceeds according to the topology of the circuit, we also devise methods to efficiently *unpack* a batch of wire values and reorder them cheaply into new batches.

The core ingredient of our approach is the notion of Reverse Multiplication-Friendly Embeddings (RMFE) [CCXY18]. A $(t, m)$-RMFE is a pair of $\mathbb{F}_2$-linear maps $\Phi: \mathbb{F}_2^t \to \mathbb{F}_{2^m}$ and $\Psi: \mathbb{F}_{2^m} \to \mathbb{F}_2^t$ satisfying $x \odot y = \Psi(\Phi(x) \cdot \Phi(y))$ for all $x, y \in \mathbb{F}_2^t$, where $\odot$ denotes the component-wise product. It is not too hard to see that RMFEs also come with an inverse map $\Phi^{-1}$ (which is not the same as $\Psi$). The main result on RMFE that we use is a central lemma from [CCXY18] (restated here as Lemma 4): there exists a family of $(t, m)$-RMFE where $m = \Theta(t)$.

For the sake of exposition, assume that we have at hand a “magic protocol” identical to that of Lemma 3, but that would operate natively over elements of any (small) extension field of $\mathbb{F}_2$, such as $\mathbb{F}_{2^\lambda}$. That is, given inputs $x \in \mathbb{F}_{2^m}$ from E and $y \in \mathbb{F}_{2^\lambda}$ from G, a public function $f$, and shares of $\Delta \cdot y$ with $\Delta \in \mathbb{F}_{2^\lambda}$ known to G (we stress that this is a thought experiment – we do not actually have such a scheme), the parties could, using one $O(\lambda)$-bit message from the garbler to the sender, obtain shares of $y \cdot f(x)$. Then, we could apply the following approach:

First, divide the Boolean circuit into layers, such that each layer contains gates of a single type (either AND or XOR) and takes its inputs from previous layers. Any Boolean circuit can be converted into one of this form with a constant factor blowup [DIK10]. Fix a batch size $t$ and break each layer into blocks of $t$ bits. Assume that the parties maintain the following invariant: for any gate $u$ with a bit $x_u$, they will hold shares $k_u \oplus \ell_u = x_u$ and shares $K_u + L_u = \Delta \cdot \ell_u$. Now, consider a layer of AND gates. For a given batch $\mathcal{B}$ of $t$ gates in the layer, let Left and Right denote the size-$t$ subset of the left-parents and right-parents of the node in $\mathcal{B}$. The parties G, E execute the following steps:

**Packing.** Aggregate the shares of $x_u$ for $u \in \text{Left}$ into a share of an element $x_l \in \mathbb{F}_{2^l}$ whose bits are the $x_u$'s, and the shares of $\Delta \cdot \ell_u$ into a share of $\Delta \cdot \ell_l$, where the bits of $\ell_l \in \mathbb{F}_{2^l}$ are the $\ell_u$'s. Do the same thing for Right, getting shares of $x_r$ and $\Delta \cdot \ell_r$.

**RME Encoding.** Compute the RMFEs $\Phi(x_l), \Phi(x_r)$. Using (two calls to) the “magic protocol” with input $\Delta$ from G and $\ell_l, \ell_r$ from E and function $f = \Phi$, the garbler adds $O(\lambda)$ bits to the garbling material of the batch $\mathcal{B}$ and the parties obtain shares $(K_l, L_l), (K_r, L_r)$ of $\Delta \cdot \Phi(\ell_l)$ and $\Delta \cdot \Phi(\ell_r)$.

**Product.** The parties use the same equations as before:

$$ \Phi(x_l) \cdot \Phi(x_r) = \Phi(\ell_l) \cdot \Phi(\ell_r) + \Phi(k_l) \cdot \Phi(k_r) + \Phi(\ell_l) \cdot \Phi(k_r) + \Phi(k_l) \cdot \Phi(\ell_r). $$

The red cross terms are computed via two calls to the “magic protocol” (with $O(\lambda)$ bits of added material) and the evaluator sets

$$ \tilde{\ell} := \langle \Phi(\ell_l) \cdot \Phi(k_r) \rangle_E + \langle \Phi(k_l) \cdot \Phi(\ell_r) \rangle_E + \Phi(\ell_l) \cdot \Phi(\ell_r). $$

The garbler computes a corresponding $\tilde{k}$. Then, the parties compute shares of $\Delta \cdot \tilde{\ell}$ using

$$ \Delta \cdot \tilde{\ell} = (\Delta\Phi(\ell_l)) \cdot \Phi(k_r) + (\Delta\Phi(\ell_r)) \cdot \Phi(k_l) + K_l \cdot \Phi(\ell_r) \\ - \Delta \cdot (\langle\Phi(\ell_l) \cdot \Phi(k_r)\rangle_G + \langle\Phi(k_l) \cdot \Phi(\ell_r)\rangle_G) + L_l\Phi(\ell_r), $$
using three calls to the magic protocol to share the cross terms.

**Unpacking.** Eventually, the parties compute the shares $(k_u, \ell_u)$ for $u \in \mathcal{B}$ by using the RMFE mapping $\Psi(\tilde{k}), \Psi(\tilde{\ell})$ (recall that the mapping is $\mathbb{F}_2$-linear), obtaining shares of $(x_u)_{u \in \text{Left}} \odot (x_u)_{u \in \text{Right}}$ (which form the $t$ outputs of the batch of gates). It remains to obtain shares of $\Delta \cdot \ell_u$ for each $u \in \mathcal{B}$; this is done using more calls to the magic protocol with input $\Delta$ from $\mathbb{G}$, $\tilde{\ell}$ from $\mathbb{E}$, and for all functions $f_i = \text{Bit}_i \circ \Psi$, where $\text{Bit}_i$ outputs the $i$-th bit of its input.

The above high-level description successfully maintains the invariant, and circumvents the issue of handling the topology of the circuit, since all shares are projected back to bitwise-authenticated shares after each batch of operations. Nevertheless, it suffers from two annoying downside:

1. We are not aware of any "magic protocol" satisfying the requirements listed above, and

2. The projection of $\Delta \cdot \tilde{\ell}$ to $\Delta \cdot \ell_u$ for all $u \in \mathcal{B}$ requires $t$ calls to the protocol, which incurs an $\Omega(t \cdot \lambda)$ overhead in the size of the garbling material, which is too much (as it does not improve over classical Yao-style garbling).

Below, we explain how to deal with each issue in turn.

## 2.3 Replacing the “Magic Protocol”

Our strategy is to emulate the features of the magic protocol while relying instead on the protocol from Lemma 3 (since we do know of an instantiation of this one). The core component of our strategy is the following (natural) embedding of $\mathbb{F}_{2^k}$ over the integers (for any $k$): view $\mathbb{F}_{2^k}$ as $\mathbb{F}_2[X]/P(X)$ where $P$ is an irreducible polynomial of degree $k$, and parse elements of $\mathbb{F}_{2^k}$ as $\mathbb{F}_2$-polynomials of degree at most $k$ (we write $\mathbb{F}_2[X;k]$ to denote this set). For any $x = \sum_{i=0}^{k-1} x_i \cdot X^i \in \mathbb{F}_2[X;k]$, we embed $x$ over the integers by computing $x(N) = \sum_{i=0}^{k-1} x_i \cdot N^i \in \mathbb{N}$ (for an integer $N$ to be specified later), and we further view $x(N)$ as an element of $\mathbb{Z}_{p-1}$ via the canonical embedding.

A useful feature of this embedding is that it preserves operations over $\mathbb{F}_{2^k}$ to some extent. Given $x, y \in \mathbb{F}_{2^k}$, if $N > k$, then $x(N) \cdot y(N)$ encodes $x \cdot y$ in the following sense: denote $\text{Mod}_N(n, 2)$ the function that, on an integer $u$, writes $u$ in $N$-arry as $u = \sum_i u_i \cdot N^i$ and returns $\sum_i [u_i \text{ mod } 2] \cdot N^i$ (that is, it reduces each coefficient of the $N$-ary decomposition of $u$ modulo 2). Then, provided that $N > k$, we have $x \cdot y = \text{Mod}_N(x(N) \cdot y(N), 2)$. Using this embedding, our strategy to emulate the magic protocol is the following:

* For each gate $u$, in addition to XOR-share $(k_u, \ell_u)$ of $x_u$, the parties will hold shares of $\Delta \cdot \ell_u$ over $\mathbb{Z}_{p-1}$.

* When packing, the parties will compute linear combinations of their shares of values $\Delta \cdot \ell_i$ with powers of $N$, to obtain shares of $\Delta \cdot (\sum_i \ell_i \cdot N^i)$.

* We will make heavy use of the fact that the one-message protocol from Lemma 3 can evaluate arbitrary functions. For instance, the parties will use an invocation of this protocol to get $\Delta \cdot f(\sum_i \ell_i \cdot N^i)$, where $f$ is the function that (1) extracts all the bits $(\ell_i)_i$ from this encoding; (2) compute $\Phi((\ell_i)_i)$; (3) re-embed this value onto $\mathbb{Z}_{p-1}$ by viewing it as a polynomial and computing $\Phi((\ell_i)_i)(N)$. After computing a product of embedded values, the parties will again use this feature to evaluate the $\text{Mod}_N(\cdot, 2)$ function, but also to reduce the (embedded) polynomial modulo $P$ (in order to obtain an embedding of the correct product over $\mathbb{F}_{2^m}$).
The above sketch hides some very important technicalities. The most important one is the fact that, as in [CHHK25], maintaining the invariant requires ensuring that the shares of the (embeddings of the) cross terms $\Phi(\ell_i) \cdot \Phi(k_r)$, $\Phi(k_i) \cdot \Phi(\ell_r)$ are small, but also, crucially, that the sharing produced by the protocol of Lemma 3 remains compatible with the (limited) homomorphic properties of the embedding. For instance, given

$$ \Phi(x_i) \cdot \Phi(x_r) = \Phi(\ell_i) \cdot \Phi(\ell_r) + \Phi(k_i) \cdot \Phi(k_r) + \Phi(\ell_i) \cdot \Phi(k_r) + \Phi(k_i) \cdot \Phi(\ell_r), $$

The parties will operate only on integer embeddings $(\Phi(\ell_i)(N), \Phi(\ell_r)(N), \text{etc})$ and will apply the $\text{Mod}_N(\cdot, 2)$ and the $\text{mod } P$ operations on the shares of the red terms via calls to the protocol. But for this to work, we need that the outputs indeed sum to (the integer embedding of) $\text{ModP}(\text{Mod}(\Phi(x_i)(N) \cdot \Phi(x_r)(N), 2))$ (where $\text{ModP}$ is the function that extracts the embedded polynomials, reduces it modulo $P$, and embeds the result). This, in turn, depends on how much the protocol from Lemma 3 blows up the size of the shares.

In fact, the protocol does incur a significant blowup – the shares are computed as a sum of $2^m$ terms, where each term is a product of embeddings, and one of the embeddings has been perturbated with noise to protect against leakage. Nevertheless, a careful choice of $N$ ensures that the homomorphic properties are sufficient to support these computations. Increasing the size of $N$ this much has a cost, though: the computational complexity of the protocol will grow as much as $2^{m^2}$ (instead of the naive $2^m$ one could have hoped for). This is the main reason why our result is limited to batching up to $t = \sqrt{\log \lambda}$ since $2^{m^2}$ must remain polynomial (and $m = O(t)$). We defer the remaining technical details on these issues to the main body.

## 2.4 Batch Function Evaluation

We now turn our attention to the second downside of our template: the unpacking procedure has a cost scaling as $O(t \cdot \lambda)$. Here, we make a simple but crucial observation: in the protocol from [CHHK25], when computing shares of $y \cdot f(x)$ the message from the garbler to the evaluator depends solely on $y$, and not on the function $f!$ The only dependency on $f$ appears in the local computation of the parties. A consequence of this observation is that when $y$ stays the same across multiple instances, $G$ and $E$ can reuse the same $O(\lambda)$-bit message to compute shares of $y \cdot f_i(x)$ for an arbitrary number of functions $f_i$. This simple but powerful observation immediately allows to reduce the cost of unpacking from $O(t\lambda)$ to $O(\lambda)$.

## 2.5 Dealing with Circular Security

We now discuss an important aspect that we have glossed over so far. The protocol claimed in Lemma 3 can be proven secure under power-DDH only if the garbler input $y$ is independent of $\Delta$. Indeed, abstracting out some details, recall that power-DDH says that given a secret $h \leftarrow_S G$, a secret exponent $\alpha \leftarrow_S Z_p$, no efficient adversary should, given the $h^{\alpha^i}$ for all nonzero $i$ from $-B$ to $B$, be able to distinguish $h$ from random. In the protocol of [CHHK25], the evaluator will learn a value of the form $y + H(h^z)$, where $z$ is some value known to the evaluator and $H$ is a suitable hash function from $G$ to $Z_{p-1}$. Then, security is shown by using power-DDH to replace $h$ with a random group element, effectively replacing $H(h^z)$ with a random value, hence hiding $y$. However, the secret exponent $\alpha$ is tied to the MAC $\Delta$ used in the protocol: given a generator $G$ of $Z_p$, they satisfy the relation $\alpha = G^\Delta \mod p$. Hence, whenever we decide to set the garbler's input to $\Delta$ in this protocol (which we do in several steps), we leak $\Delta + H(h^z)$ to the evaluator, where the masked value is now a function of the secret exponent $\alpha$ itself, making it impossible to invoke power-DDH to randomize this term!
We provide two alternatives to deal with this issue. First, we formalize the exact security notion required to prove the security of our schemes. In essence, the notion states that terms of the form $H(h^z) + \Delta \cdot v$ for known $(z, v)$ should look jointly indistinguishable from random to an adversary knowing the $h^{\alpha^i}$ for $i \neq 0$. Then, we prove that when modeling the group as a generic group (in Shoup's variant of the GGM) and the hash function $H$ as a random oracle, this assumption holds unconditionally. Because a random oracle can be constructed from Shoup's GGM, this implies that our entire garbling scheme can be proven secure in the GMM.

Second, we use the same strategy as [CHHK25]: we rely instead on a leveled version, where we use a different $\Delta_j$ for each layer and only use the secret $h_j$ associated with the $\Delta_j$ from a layer to mask $\Delta_{j+1}$. With this change, security can be proven under the power-DDH assumption and the (non-circular) correlation robustness of the hash function for a suitable family of “exponential correlations”. The price to pay is twofold: first, we must now include in the garbled circuit a tuple of the form $(h^{\alpha^i})_i$ for each layer, adding a term depth$(C) \times \text{poly}(\lambda)$ to the size of the garbled circuit. Second, and more annoyingly, our packing procedure crucially requires that all the values being packed are authenticated under the same $\Delta$. This constrains us to restrict our attention to layered Boolean circuits, where all the parent nodes of a layer are in the previous layer, ensuring that when evaluating the $j$-th layer, all the nodes to be packed are authenticated with the same $\Delta_{j-1}$.

# 3 Preliminaries

We begin by introducing the notation that will be used throughout the subsequent sections.

**General notation.** Given a distribution $\mathcal{D}$ (resp. a set $S$), we write $x \leftarrow \mathcal{D}$ (resp. $x \leftarrow S$) to denote that $x$ is sampled from $\mathcal{D}$ (resp. that $x$ is sampled uniformly over $S$). Given an integer $B$, we denote by $[B]$ the set $\{0, \dots, B\}$, by $[\pm B]$ the set $\{-B, -B+1, \dots, 0, \dots, B-1, B\}$, and by $[B]^*$, $[\pm B]^*$ the sets $[B]$, $[\pm B]$ without $0$. When convenient, we let poly denote an unspecified polynomial.

**Arithmetic.** Given integers $u, n$, we write $[u \bmod n]$ to denote the representative of $u \bmod n$ as an element of $[n-1] \subset \mathbb{N}$. More generally, if $u$ denotes a polynomial, $n$ an integer, and $P$ a polynomial, we write $[u \bmod 2, P]$ to denote the representative of $(u \bmod 2) \bmod P$ as an element of $\mathbb{N}[X]$ of degree at most $\deg(P) - 1$ and with coefficients in $[n-1]$.

**Polynomials.** Given a parameter $m$, we let $P_m$ denote an irreducible degree-$m$ over $\mathbb{F}_2$. We view elements of $\mathbb{F} = \mathbb{F}_{2^m}$ as polynomials over $\mathbb{F}_2[X]/P_m(X)$. For any ring $\mathcal{R}$, we write $\mathcal{R}[X; m]$ to denote the set of polynomials $a \in \mathcal{R}[X]$ with $\deg(a) \le m$. Given a polynomial $r = \sum_i r[i] \cdot X^i$, let $\text{Eval}_N$ denote the procedure that, on input $r$, returns $r(N) = \sum_i r[i] \cdot N^i$. By default, addition ("+") refers to the addition over the structure the operands live in. As we often switch between interpretations (e.g., viewing an element of $\mathbb{F}_{2^m} \equiv \mathbb{F}_2[X]/P(X)$ as an element of $\mathbb{Z}[X]$), we add clarification whenever there is an ambiguity. We also sometimes write $\oplus$ to denote the bitwise-XOR to make it clear that the coefficient-wise addition is done modulo 2.

**Garbling.** Throughout this paper, we let $G$ denote the garbler, and $E$ denote the evaluator. We use the notation $\langle x \rangle$ for additive (or subtractive) shares of $x$. Since this sharing is frequently between a garbler and an evaluator, we will use $\langle x \rangle_G$ to denote the garbler's share of $x$ and $\langle x \rangle_E$ to denote the evaluator's share of $x$.

We use the standard definition of garbling schemes from [BHR12], specialized as in previous works [ZRE15], to the setting of Boolean circuits.
**Definition 1 (Garbling Scheme).** A garbling scheme GC for Boolean circuits consists of the following algorithms.

* GC.Garble(1^λ, C): A PPT algorithm that on input 1^λ and a Boolean circuit C, outputs (Ĉ, e, d) where Ĉ is a garbled circuit, e is an encoding information, and d is a decoding information.

* GC.Enc(e, x) : A polynomial time algorithm that on input e and x ∈ {0, 1}^{|I(C)|}, output a garbled input ˆx.

* GC.Eval(Ĉ, ˆx) : A polynomial time algorithm that on input a garbled circuit and a garbled input, outputs a garbled output p.

* GC.Dec(d, ˆy) : A polynomial time algorithm that on input the decoding information and the garbled output, outputs y ∈ {0, 1}^{|O(C)|}.

A garbling scheme is correct if for every Boolean circuit C, every (Ĉ, e, d) in the support of GC.Garble(1^λ, C), and every input x ∈ {0, 1}^{|I(C)|}, it holds that

$$GC.Dec(d, GC.Eval(Ĉ, GC.Enc(e, x))) = C(x).$$

Furthermore, a garbling scheme is private if there exists a simulator SimGC such that for every infinite family {C_λ}λ∈N of Boolean circuits with |C_λ|≤ poly(λ) and every infinite family of inputs {x_λ}λ∈N with |x_λ|= |I(C_λ)| for every λ ∈ N, the following distribution families (parameterized with λ) are indistinguishable:

$$ \{(Ĉ, ˆx, d) \leftarrow \text{SimGC}(1^\lambda, C_\lambda, C(x_\lambda))\} \\ \{(Ĉ, ˆx, d) : (Ĉ, e, d) \leftarrow \text{GC.Garble}(1^\lambda, C), ˆx \leftarrow \text{GC.Enc}(e, x_\lambda)\} $$

## 3.1 Generic Group Model

We rely on Shoup's generic group model [Sho97] (GGM). For simplicity, we restrict our attention to prime order groups.

**Definition 2 (Shoup's GGM).** Let p denote a prime. Fix a set G of cardinality p and let σ denote a random bijective mapping from Z_p to G. Given p (available to all parties), in Shoup's GGM, all parties have access to a group oracle O_G with the following queries:

* Encode(x): given x ∈ Z_p, return σ(x).

* Add(a, b, σ(x), σ(y)): given a, b ∈ Z_p and σ(x), σ(y) ∈ G, set z := a ⋅ x + b ⋅ y mod p and return σ(z).

We let g := Encode(1) denote a fixed generator of G. Note that any party can sample uniformly from G given one call to Encode. As a shorthand for exponentiations, given x ∈ Z_p and h ∈ G, we write x ⋅ h to denote Add(x, 0, h, Encode(0)) = Encode(x ⋅ y) where h = Encode(y).
## 3.2 Boolean Circuits

A circuit is a directed acyclic graph. Internal nodes are called *gates*, nodes of indegree 0 are called *input gates*, and nodes of outdegree 0 are called *output gates*. Edges are called *wires*. In this work, we consider polynomial-size Boolean circuits of fan-in 2 over the basis {$\oplus, \land$}. Given a circuit *C*, we let $D := \text{depth}(C)$ denote the depth of *C* (the length of the longest path from an input to an output), $I(C)$ denote the set of input wires, $W(C)$ denote the set of all wires, $O(C)$ denote the set of output wires, and $\Gamma(C)$ denote the set of gates. We write $|C|$ to denote the size of *C* (the number of gates in *C*).

**Layered circuits.** In a layered boolean circuit *C*, the set of gates $\Gamma(C)$ can be partitioned into $D = \text{depth}(C)$ layers ($L_1, \dots, L_D$) such that every wire connects adjacent layers i.e., every edge $(u, v) \in C$ is such that $u \in L_i$ and $v \in L_{i+1}$ for some $i \in [D-1]$. Thus, the inputs to gates in $L_1$ consist only of the circuit inputs. Any boolean circuit of size *s* and depth *D* can be computed by a layered circuit of size $sD$, with a lower bound of *s* log *s*.

**Rate of Boolean garbling.** The rate of a boolean garbling scheme is a measure of the efficiency of the scheme.

**Definition 3 (Rate of a boolean garbling scheme).** Let *C* be a class of boolean circuits, and let *GC* be a boolean garbling scheme for *C*. The rate of *GC* is defined as

$$ \liminf_{C \in \mathcal{C}} \min_{\hat{C} \in \mathcal{S}} \min_{x} \frac{|C| + |I(C)|}{|\hat{C}| + |e|} $$

where $\mathcal{S} = \text{Sup}(\text{GC}.\text{Garble}(1^{\lambda}, C))$, the minimum is taken over all admissible inputs to *C*, and the limit infimum is taken over *C* partially ordered by subcircuit inclusion.

For garbling schemes in this work, the size of the garbled circuit $\hat{C}$ primarily depends on the size (and depth) of the circuit *C* and the size of the encoding information *e* is $O(\lambda \cdot I(C))$. In this case, it suffices to consider the rate as

$$ \min_{C \in \mathcal{C}} \frac{|C|}{|\hat{C}|} $$

where $\hat{C}$ is the size of the garbled circuit corresponding to *C*.

## 3.3 Preliminaries on Power-DDH

We let $\text{GrpGen}(1^{\lambda})$ denote a deterministic algorithm that, on input $1^{\lambda}$, outputs a tuple $(\mathbb{G}, p, g)$ where $\mathbb{G}$ is a cyclic group of order a prime $p$ of length $O(\lambda)$ bits, and $g$ is a generator of $\mathbb{G}$. We recall the variant of power-DDH introduced in [CHHK25]:

**Definition 4 (B-power-DDH assumption).** Let $B = B(\cdot)$ be a polynomial. The B-power-DDH assumptions holds with respect to $\text{GrpGen}$ if for all large enough security parameter $\lambda$, denoting $(\mathbb{G}, p, g) := \text{GrpGen}(1^{\lambda})$, the following distributions are computationally indistinguishable:

$$ \mathcal{D}_0 := \{ (g_i)_{i \in [\pm B(\lambda)]} : \alpha \leftarrow \mathbb{Z}_p^*, h \leftarrow \mathbb{G}, (g_i)_{i \in [\pm B(\lambda)]} \leftarrow (h^{\alpha^i})_{i \in [\pm B(\lambda)]} \} $$

$$ \mathcal{D}_1 := \{ (g_i)_{i \in [\pm B(\lambda)]} : \alpha \leftarrow \mathbb{Z}_p^*, h, g_0 \leftarrow \mathbb{G}, (g_i)_{i \in [\pm B(\lambda)]^*} \leftarrow (h^{\alpha^i})_{i \in [\pm B(\lambda)]} \} $$

As shown in [CHHK25], this formulation of power-DDH is equivalent to the other traditional formulation of the power-DDH assumption [GJM03, CNs07] (where the last term $h^{\alpha^B}$ is the one that should be indistinguishable from random), and more generally to the variant where all terms $h^{\alpha^i}$ are replaced by random, up to a factor-2 loss in the size of *B*.
## 3.4 Reverse Multiplication-Friendly Embeddings

Reverse Multiplication-Friendly Embeddings (RMFE) [CCXY18] allow computations over tuples of binary values, where addition and multiplication are performed coordinate-wise, to be embedded into computations over an extension field. Ideally, such an embedding would be a ring isomorphism that preserves both addition and multiplication i.e., the embedding would be a map $\Phi : \mathbb{F}_2^t \to \mathbb{F}_{2t}$ such that $\Phi(x+y) = \Phi(x)+\Phi(y)$ and $\Phi(x \cdot y) = \Phi(x) \cdot \Phi(y)$. However, such an isomorphism cannot exist: while $\mathbb{F}_2^t$ and $\mathbb{F}_{2t}$ are isomorphic as additive groups, their multiplicative structures differ (e.g., $\mathbb{F}_2^t$ has zero divisors while $\mathbb{F}_{2t}$ does not). To circumvent this issue, RMFEs provide a mapping $\Phi : \mathbb{F}_2^t \to \mathbb{F}_{2m}$ with a weaker guarantee: it allows embedding a single multiplication over $\mathbb{F}_2^t$ as multiplication over $\mathbb{F}_{2m}$. After each multiplication, the result in $\mathbb{F}_{2m}$ must be mapped back to $\mathbb{F}_2^t$ using $\Psi : \mathbb{F}_{2m} \to \mathbb{F}_2^t$, then re-embedded into $\mathbb{F}_{2m}$ using $\Phi$ before another multiplication can be performed. We next recall the definition of RMFEs.

**Definition 5** (Reverse Multiplication Friendly Embeddings [CCXY18]). Let $q$ be a prime power, $\mathbb{F}_q$ be a field of $q$ elements, and let $m, t \ge 1$ be integers. A pair $(\Phi, \Psi)$ is called a $(t, m)_q$-reverse multiplication friendly embedding (RMFE) if $\Phi : \mathbb{F}_q^t \to \mathbb{F}_{q^m}$ and $\Psi : \mathbb{F}_{q^m} \to \mathbb{F}_q^t$ are two $\mathbb{F}_q$-linear maps satisfying

$$x \cdot y = \Psi(\Phi(x) \cdot \Phi(y))$$

for all $x, y \in \mathbb{F}_q^t$.

Let $1 = (1, \dots, 1) \in \mathbb{F}_2^t$ and let $\Phi^{-1} : \mathbb{F}_{2m} \to \mathbb{F}_2^t$ be defined as $\Phi^{-1}(x) = \Psi(\Phi(1) \cdot x)$. It then follows that for all $x \in \mathbb{F}_2^t$, $\Phi^{-1}(\Phi(x)) = \Psi(\Phi(1) \cdot \Phi(x)) = x$, and thus, $\Phi^{-1}$ can be used for decoding an embedded value $x \in \mathbb{F}_{2m}$. Moreover, it is easy to see that $\Phi^{-1}$ is also $\mathbb{F}_2$-linear.

Our use of RMFEs is motivated by the fact that computation over the extension field $\mathbb{F}_{2m}$ can be expressed as an arithmetic circuit, making it compatible with efficient techniques for arithmetic garbling. Consequently, the rate of the embedding, $t/m$, is crucial for ensuring that the efficiency of computation over $\mathbb{F}_{2m}$ translates to computation over $\mathbb{F}_2^t$. The following lemma from [CCXY18] establishes the existence of constant rate RMFEs.

**Lemma 4** (Constant rate RMFE [CCXY18]). For every finite prime power $q$, there exists a family of $(t, m)_q$-RMFE where $m = \Theta(t)$.

## 4 Correlation-Robustness for Exponential Correlations

Given a secret $s$, a hash function $H$ is said to be correlation-robust for a class of correlations $C$ if (informally) samples of the form $H(C(x, s))$ for public inputs $x$'s are indistinguishable from random. Several classes of correlations have been commonly used in the literature, such as additive correlations [IKNP03] ($C(x, s) = x+s$), affine correlations [SS24] ($C((x_0, x_1), s) = x_0 \cdot s + x_1$), group-induced correlations [AMN$^{+}$18] ($C(x, s) = x \cdot s$ where $x, s$ belong to some group $(\mathbb{G}, \cdot)$) and exponential correlations [BCM$^{+}$24, CHHK25] ($C(x, s) = s^x$ where $s \in \mathbb{G}$ and $x \in \mathbb{Z}_{\text{ord}(\mathbb{G})}$).

**Tweakable circular correlation-robustness (TCCR).** Previous works on garbled circuit typically require a strengthening of the notion of correlation-robustness:

* A hash function $H$ is *tweakable* correlation-robust for a class of correlations $C$ if (informally) samples of the form $H(C(x, s), y)$ are indistinguishable from random given public inputs $x$'s and public *tweaks* $y$'s (where all pairs $(x, y)$ are distinct).
* A hash function H is circularly correlation-robust for C if (informally) samples of the form H(C(x, s))+L(s) are indistinguishable from random, where the x's are public inputs and the L's are public linear functions. In other words, the hash outputs can be used to mask (linear functions of) the secret key s. If the hash can additionally take a tweak y and samples of the form H(C(x, s), y) + L(s) are indistinguishable from random, we say that H is tweakable circular correlation-robust (TCCR) for the correlation C.

Circular correlation-robustness was first defined and studied in [CKKZ12]. Several variants have been used and refined in subsequent works [ZRE15, GKWY20]. The variant used in our work is closer in spirit to the notion of tweakable circular correlation-robustness (TCCR) used in [RR21].

**Tweakable correlation-robust hashing for exponential correlations.** Given a security parameter $\lambda$, fix group parameters $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$ (recall that $g$ generates $\mathbb{G}$, and $G$ generates $\mathbb{Z}_p^*$). We start by defining the simplest variant of correlation-robustness considered in this work, where no circular security is required, and where the adversary is not given access to auxiliary inputs.

**Definition 6** (Tweakable correlation-robust hashing for exponential correlations over $\mathbb{G}$). Given a security parameter $\lambda$, let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$. Let $H = \{H_{\lambda}\}_{\lambda \in \mathbb{N}}$ be a family of hash functions $H_{\lambda}: \mathbb{G} \to \mathbb{Z}_{p-1}$. Given $h \in \mathbb{G}$, let $O_{H,h}$ denote the oracle that, on input $(x, y) \in \mathbb{Z}_{p-1} \times \{0, 1\}^*$, returns $H(h^x, y)$.

We say that the hash family $H = \{H_{\lambda}\}_{\lambda \in \mathbb{N}}$ is a TCCR hash for exponential correlations over $\mathbb{G}$ if for every probabilistic polynomial-time adversary $\mathcal{A}$, it holds that

$$ \left| \Pr[\mathcal{A}^{H, O_{H,h}}(1^{\lambda}) = 1] - \Pr[\mathcal{A}^{H, \mathcal{R}}(1^{\lambda}) = 1] \right| \le \text{negl}(\lambda), $$

where the probability is taken over the random choice of $h \leftarrow \mathbb{S} \mathbb{G}$ and of a random oracle $\mathcal{R}: \mathbb{Z}_{p-1} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}$.

The above assumption refers to (tweakable) correlation-robustness for the same correlation as [CHHK25], where the secret is a random $h \leftarrow \mathbb{S} \mathbb{G}$, and the correlation is given by $C(x, h) = h^x$ for $x \in \mathbb{Z}_{p-1}$. We call this correlation the exponential correlation over $\mathbb{G}$.

## 4.1 Circular Correlation-Robustness in the Generic Group Model

In this work, we rely on (a form of) tweakable circular correlation-robust hash for the exponential correlation over $\mathbb{G}$. In addition, we need a strengthening of the notion where the adversary is given auxiliary information in the form of group elements $h_i := h^{G^{i-\Delta}}$ for a random $\Delta \leftarrow \mathbb{S} \mathbb{Z}_{p-1}$ and various $i \neq 0$, and where circular security must hold with respect to linear functions of $\Delta$.

**Definition 7** (TCCR hashing for exponential correlation with auxiliary powers over $\mathbb{G}$). Given a security parameter $\lambda$, let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$. Let $H = \{H_{\lambda}\}_{\lambda \in \mathbb{N}}$ be a family of hash functions $H_{\lambda}: \mathbb{G} \to \mathbb{Z}_{p-1}$. Given $\Delta \in \mathbb{Z}_{p-1}$ and $h \in \mathbb{G}$, let $O_{H,h,\Delta}$ denote the oracle that, on input $(x, y, z) \in \mathbb{Z}_{p-1} \times \{0, 1\}^* \times \mathbb{Z}_{p-1}$, returns $H(h^x, y) + z \cdot \Delta \bmod p - 1$. We say that a list of queries to $O_{H,h,\Delta}$ is admissible if for every pair of queries $(x, y, z)$, $(x', y', z')$, if $(x, y) = (x', y')$, then $z = z'$.

Given a polynomial bound $B = B(\lambda)$, we say that the hash family $H = \{H_{\lambda}\}_{\lambda \in \mathbb{N}}$ is a TCCR hash for exponential correlation with $2B - 1$ auxiliary powers over $\mathbb{G}$, denoted $(B, \mathbb{G})$-ap-eTCCR, if for every probabilistic polynomial-time adversary $\mathcal{A}$ that makes admissible queries, it holds that

$$ \text{Adv}_{\mathcal{A}, 1^{\lambda}}^{\text{ap-eTCCR}} := \left| \Pr[\mathcal{A}^{H, O_{H,h,\Delta}}((h_i)_{i \in [\pm B] \setminus \{0\}}) = 1] - \Pr[\mathcal{A}^{H, \mathcal{R}}((h_i)_{i \in [\pm B] \setminus \{0\}}) = 1] \right| $$
is negligible, where the probability is taken over the random choice of $(\Delta, h) \leftarrow \mathbb{Z}_{p-1} \times \mathbb{G}$ and of a random oracle $\mathcal{R}: \mathbb{Z}_{p-1} \times \{0, 1\}^* \times \mathbb{Z}_{p-1} \to \mathbb{Z}_{p-1}$, and where the $h_i$'s are defined as follows: set $\alpha := G^\Delta \mod p$ and define $h_i := h^{\alpha^i}$ for all $i \in [\pm B]$.

The theorem below shows that, when modeling H as a random oracle and $\mathbb{G}$ as a generic group, the assumption of Definition 7 holds unconditionally:

**Theorem 5.** Let $\mathbb{G}$ be modeled via a generic group oracle $O_{\mathbb{G}}$ (Definition 2), H be modeled as a random oracle, and $\mathcal{A}$ be an adversary making at most $Q_{\mathbb{G}}$ queries to $O_{\mathbb{G}}$, $Q_H$ queries to H, and $Q_O$ queries to $O_{H,h,\Delta}$. Then

$$ \mathrm{Adv}_{\mathcal{A},1^{\lambda}}^{\mathrm{ap-eTCCR}} \le \frac{(Q_{\mathbb{G}} + Q_O)^2 + (Q_O + 1) \cdot (2B \cdot (Q_{\mathbb{G}} + 1)^2 + (Q_O - 1) \cdot Q_H/2)}{p} $$

We note that since a random oracle can be implemented unconditionally in Shoup's GGM, one can choose a H such that the resulting assumption can be proven solely in Shoup's GGM.

*Proof.* We prove Theorem 5 via a sequence of hybrids.

**Hybrid$_0$.** This is the real game (in the GGM): the experiment samples $\Delta \leftarrow \mathbb{Z}_{p-1}$ and $h \leftarrow \mathbb{G}$. It sets $\alpha := G^\Delta \mod p$ and defined $h_i := \alpha^i \bullet h$ for all $i \in [\pm B]$. We let the experiment sample the random oracle H lazily upon queries of either $\mathcal{A}$ or $O_{H,h,\Delta}$ to H. On input $(h_i)_{i \in [\pm B] \setminus \{0\}}$, $\mathcal{A}$ makes queries to $O_{\mathbb{G}}$, H, and $O_{H,h,\Delta}$, and returns a bit $b$. We let $\mathrm{Pr}[\mathrm{Hybrid}_0]$ denote the probability that $b = 1$ in this hybrid.

**Hybrid$_1$.** In this game, we modify the sampling of $\sigma$ (see Definition 2). Instead of sampling an injective mapping $\sigma$ before the game, the experiment maintains a list $L$ of pairs $(x, \sigma(x))$. Upon receiving any query Encode($x$) from either $\mathcal{A}$ or $O_{H,h,\Delta}$, if $L$ contains a pair $(x, \sigma(x))$, the experiment returns $\sigma(x)$. Otherwise, the experiment samples $y \leftarrow \mathbb{S}$, adds $(x, y)$ to $L$, and returns $y$. Conditioned on no collision occurring during this process, the mapping $\sigma$ sampled this way is a uniform injective mapping, and this hybrid is perfectly indistinguishable from the previous one. Bounding the probability of collisions (pairs $(x, x')$ with $\sigma(x) = \sigma(x')$), we have:

$$ |\mathrm{Pr}[\mathrm{Hybrid}_1] - \mathrm{Pr}[\mathrm{Hybrid}_0]| \le \frac{(Q_{\mathbb{G}} + Q_O)^2}{p}. $$

**Hybrid$_2$.** In this game, we slightly modify the sampling of the $h_i$'s. Namely, we let the experiment sample $h_{-B} \leftarrow \mathbb{G}$ and define $h_i := (\alpha^{B+i}) \bullet h_{-B}$ for $i = -B + 1$ to $B$. For convenience, we rename $h_{-B}$ as $f$ and $h_i$ as $f_{B+i}$, so that $f_i = \alpha^i \bullet f$ for $i = 0$ to $2B$. Note that $h = f_B$ is the secret group element. This change is purely syntactical, and we have

$$ \mathrm{Pr}[\mathrm{Hybrid}_2] = \mathrm{Pr}[\mathrm{Hybrid}_1]. $$

**Hybrid$_3$.** In this game, we delay the choice of $\Delta$ (and $\alpha$) until the first query of $\mathcal{A}$ to $O_{H,h,\Delta}$. This is achieved by simulating the generic group via symbolic computations. At the start of the game, the experiment defines a formal variable $X$. It samples $(f_0, f_1, \dots, f_{B-1}, f_{B+1}, \dots, f_{2B}) \leftarrow \mathbb{G}^{2B+1}$ (note that $f_B$ is not sampled) and stores the pairs $(X^i, f_i)$ for all $i \ne B$, as well as the pair $(1, g)$ (recall that $g$ is defined as Encode(1)) in the list $L$. Then, it proceeds as follows:

**Before the first query to $O_{H,h,\Delta}$.** The experiment maintains the invariant that $L$ is a list of pairs $(P, u \in \mathbb{G})$ where $P$ is a multivariate polynomial (with coefficients over $\mathbb{Z}_p$) of the form $P'(X, X_1, \dots, X_n) = \sum_{i=0}^{2B} c_i \cdot X^i + \mathrm{Lin}(X_1, \dots, X_n)$, where $c_B = 0$ and $\mathrm{Lin}$ is a linear multivariate polynomial.
* Upon receiving a query Encode(x), it behaves as in Hybrid₂: if L contains a pair (x, σ(x)), it returns σ(x); else, it returns y $\leftarrow$ G and adds (x, y) to L.

* Upon receiving a query Add(a, b, u, v) with a, b $\in$ Zₚ and u, v $\in$ G, if L does not contain a pair (P_u, u) (resp. a pair (P_v, v)), it defines a new formal variable X_u and adds (P_u := X_u, u) to L (resp. it defines X_v and stores (P_v := X_v, v)). If L contains a pair (a $\cdot$ P_u + b $\cdot$ P_v, w), it returns w. Else, it returns w $\leftarrow$ G and adds (a $\cdot$ P_u + b $\cdot$ P_v, w) to L.

**Upon receiving the first query to O<sub>H,h,Δ</sub>.** Upon receiving a query (x, y, z) to O<sub>H,h,Δ</sub>, the experiment samples $\Delta \leftarrow$ Z<sub>p-1</sub> and sets $\alpha := G^\Delta \bmod p$. Then, it does the following:

**Storing $x \cdot f_B$.** The experiment samples $v \leftarrow$ G and adds $(x \cdot X^B, v)$ to L.

**Collapsing L.** Let X, X₁, ..., Xₙ denote all formal variables appearing in L (where $n \le Q_G$). The experiment samples $(x_1, \dots, x_n) \leftarrow$ Zₚⁿ and substitutes $P_u(X, X_1, \dots, X_n)$ with $P_u(\alpha, x_1, \dots, x_n)$ across all pairs $(P_u, u)$ in L. If a collapse happens, i.e. $P_u(\alpha, x_1, \dots, x_n) = P_v(\alpha, x_1, \dots, x_n)$ for two distinct polynomials $P_u, P_v \in L$, it raises a flag Fail<sub>α</sub>.

**Sampling the answer.** If a previous query to H of the form H(v, y) had been made, it raises a flag Fail<sub>H</sub> and returns this answer. Else, it sample $a \leftarrow$ Z<sub>p-1</sub>, returns a, and stores H(v, y) := a - z $\cdot \Delta \bmod p - 1$.

**For all subsequent queries.** The experiment behaves as in Hybrid₂.

We prove the following:

**Lemma 6.**

$$|\Pr[\text{Hybrid}_3] - \Pr[\text{Hybrid}_2]| \le \frac{2B \cdot (Q_G + 1)^2 + Q_H}{p}.$$

*Proof.* First, we observe that conditioned on Hybrid₃ not failing (i.e. not raising a flag Fail<sub>α</sub> or Fail<sub>H</sub>), Hybrid₂ and Hybrid₃ are perfectly indistinguishable: all answers of the experiment to queries to O<sub>G</sub>, H before the first query to O<sub>H,h,Δ</sub> are distributed identically to Hybrid₂ conditioned on Fail<sub>α</sub> not being raised, and the distribution of H(v, y) := a - z $\cdot \Delta \bmod p - 1$ for a uniform a (conditioned on Fail<sub>H</sub> not being raised) is identical to the distribution of H(v, y) in Hybrid₂. It remains to bound the probability of the failure events.

First, note that $\alpha = G^\Delta \bmod p$ for $\Delta \leftarrow$ Z<sub>p-1</sub> is uniformly distributed over Zₚ. Fix two distinct polynomials $P_u, P_v$ from L. Write

$$\begin{align*} P_u(X, X_1, \dots, X_n) &= P'_u(X) + \mathrm{Lin}_u(X_1, \dots, X_n), \\ P_v(X, X_1, \dots, X_n) &= P'_v(X)d_i \cdot X^i + \mathrm{Lin}_v(X_1, \dots, X_n), \end{align*}$$

where $P'_u, P'_v$ are univariate polynomials of degree at most 2B. Then, let $P' := P'_u - P'_v$ and $\mathrm{Lin} := \mathrm{Lin}_v - \mathrm{Lin}_u$. We have

$$\begin{align*} P_u(\alpha, x_1, \dots, x_n) &= P_v(\alpha, x_1, \dots, x_n) \\ &\iff P'(\alpha) = \mathrm{Lin}(x_1, \dots, x_n). \end{align*}$$

Now, two cases can occur: either $P' = 0$ (as a polynomial), in which case $\mathrm{Lin} \ne 0$ (as $P_u \ne P_v$) and the probability (over a random choice of $(x_1, \dots, x_n)$) that $\mathrm{Lin}(x_1, \dots, x_n) = 0$ is exactly $1/p$. Or $P' \ne 0$, in which case $P'$ has at most 2B roots (as it has degree at most 2B) and for any $(x_1, \dots, x_n)$, the probability (over the random choice of $\alpha$) that $P'(\alpha) = \mathrm{Lin}(x_1, \dots, x_n)$ is at most $2B/p$. Given that L contains at most $Q_G + 1$
entries (one for each query of $\mathcal{A}$ to $\mathbb{G}$, and the pair $(x \cdot X^B, v)$), it follows from a straightforward union bound that $\Pr[\text{Fail}_\alpha] \le (Q_{\mathbb{G}} + 1)^2 \cdot 2B/p$. For $\text{Fail}_H$, observe that $v$ is sampled uniformly at random from $\mathbb{G}$, and the probability that any query of $\mathcal{A}$ to $H$ is of the form $(v, y)$ is therefore at most $Q_H/p$. This concludes the proof. ■

**Hybrid$_{3,2}$**. This hybrid is defined identically to Hybrid$_3$, except that it uses symbolic computations before the second query to $O_{H,h,\Delta}$. Upon receiving the first query $(x_1, y_1, z_1)$ to $O_{H,h,\Delta}$, it does the following:

* It samples $v_1 \leftarrow \mathbb{G}$ and adds $(x_1 \cdot X^B, v_1)$ to $L$.

* It returns $a_1 \leftarrow \mathbb{Z}_{p-1}$ and proceeds with the symbolic emulation of the generic group as before.

Upon receiving the second query $(x_2, y_2, z_2)$ to $O_{H,h,\Delta}$, it samples $\Delta \leftarrow \mathbb{Z}_{p-1}$ and executes the steps **storing $x_2 \cdot f_B$, collapsing $L$, and sampling the answers** from Hybrid$_3$, with the following modification to the first and last steps:

* In the first step, if $x_2 = x_1$, it simply sets $v_2 = v_1$.

* In the last step, if $(x_1, y_1) = (x_2, y_2)$, it sets $a_2 := a_1$ (note that the security game forces $z_1 = z_2$ in this case, as $\mathcal{A}$ is restricted to making admissible queries).

It behaves as Hybrid$_2$ (and Hybrid$_3$) for all subsequent queries. Until (and including) the first query to $O_{H,h,\Delta}$, the answers of Hybrid$_{3,2}$ are distributed identically to that of Hybrid$_3$ (in particular, the answer $a_1$ to the first query is sampled uniformly in both hybrids). The event $\text{Fail}_\alpha$ is defined as in Hybrid$_3$. We modify the definition of the event $\text{Fail}_H$ as follows:

**Fail$_H$**: the experiment raises $\text{Fail}_H$ if the list of all queries made by $\mathcal{A}$ to $H$ contains either a tuple $(v_1, y')$ or $(v_2, y')$ for any $y'$.

Due to the symbolic evaluation, the answers all queries of $\mathcal{A}$ to $O_{\mathbb{G}}$ up to the second query to $O_{H,h,\Delta}$ are totally independent of $v_1, v_2$, since all queries of $\mathcal{A}$ are with respect to tuples $(P_u, u)$ where the coefficient of $X^B$ in $P_u$ is 0 (since $\mathcal{A}$ is not given access to the tuple $(X^B, f)$). Hence, $v_1$ and $v_2$ are perfectly random and independent from $\mathcal{A}$'s view (with the exception that $v_1 = v_2$ when $x_1 = x_2$), and we can bound $\text{Fail}_H$ by $2Q_H/p$.

Conditioned on $\text{Fail}_\alpha$ and $\text{Fail}_H$ not being raised after the second $O_{H,h,\Delta}$ query, Hybrid$_3$ and Hybrid$_{3,2}$ are perfectly indistinguishable, and the probability of the failure events can be bounded by the same analysis as Lemma 24. Note that when $\text{Fail}_H$ is not raised, the answer $a_2$ to the second query is either equal to $a_1$, or uniformly random (and independent of $\Delta$). We get

$$|\Pr[\text{Hybrid}_{3,2}] - \Pr[\text{Hybrid}_3]| \le \frac{2B \cdot (Q_{\mathbb{G}} + 1)^2 + 2Q_H}{p}.$$

**Hybrid$_{3,i}$**. For $i = 3$ to $Q_O$, we let Hybrid$_{3,i}$ be defined as follows: it uses symbolic evaluation up to the $i$-th query to $O_{H,h,\Delta}$. For $j = 1$ to $i$, it answers queries to $O_{H,h,\Delta}$ as follows: if $(x_j, y_j, z_j) = (x_k, y_k, z_k)$ for some $k < j$, it sets $v_j := v_k$ and returns $a_k$. Else, it samples $v_j \leftarrow \mathbb{G}$, adds $(x_j \cdot X^B, v_j)$ to $L$, and returns $a_j \leftarrow \mathbb{Z}_{p-1}$. After the **collapsing $L$ and sampling the answers** steps, it raises a flag $\text{Fail}_\alpha$ if a collision
occured during collapsing, and a flag Fail<sub>H</sub> if the list of 𝒜's queries to H contain a pair (v<sub>j</sub>, y') for any y'.
It behaves as Hybrid<sub>3.(i-1)</sub> afterwards. The same analysis as before shows

$$
|\Pr[\text{Hybrid}_{3,i}] - \Pr[\text{Hybrid}_{3.(i-1)}]| \le \frac{2B \cdot (Q_{\mathbb{G}} + 1)^2 + j \cdot Q_{\mathbb{H}}}{p}.
$$

Hybrid<sub>4</sub>. Observe that from Hybrid<sub>3.Q<sub>O</sub></sub>, the oracle O<sub>H,h,Δ</sub> behaves identically to a random oracle. In Hybrid<sub>4</sub>, we replace O<sub>H,h,Δ</sub> with a random oracle 𝒜 (this is just a syntactic change at this step). In addition, the experiment uses the true generic oracle O<sub>G</sub> instead of using symbolic evaluation. By the same argument as before, this hybrid is indistinguishable from the previous one unless the event Fail<sub>α</sub> is raised, hence

$$
|\Pr[\text{Hybrid}_4] - \Pr[\text{Hybrid}_{3.Q_o}]| \le \frac{2B \cdot (Q_G + 1)^2}{p},
$$

which concludes the proof.

<figure><img src="image_2.png" /></figure>

4.2 Leveled Circular Correlation-Robustness

We will also consider a leveled version of the assumption. In this version, there are *d* levels. For each
$j \le d + 1$, the security experiment samples $(\Delta_j, h_j) \leftarrow_S \mathbb{Z}_{p-1} \times \mathbb{G}$ and sets $\alpha_j := G^{\Delta_j} \bmod p$ and $h_{j,i} := h_j^{\alpha_j}$
for all $i \in [\pm B]$. The adversary $\mathcal{A}$ is restricted to make at most *d* adaptive batches of queries to the oracle,
and the oracle answer the *j*-th batch of queries with answers of the form $H(h_j^x, y) + z \cdot \Delta_{j+1} \bmod p - 1$.

**Definition 8** (Leveled TCCR hashing for exponential correlation with auxiliary powers over $\mathbb{G}$). Given a security parameter $\lambda$, let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$. Let $H = \{H_\lambda\}_{\lambda \in \mathbb{N}}$ be a family of hash functions $H_\lambda : \mathbb{G} \to \mathbb{Z}_{p-1}$. Fix a (polynomial) depth parameter $d = d(\lambda)$. Let $\mathcal{O}_{H,h,\Delta}$ denote the following stateful oracle:

$\mathcal{O}_{H,h,\Delta}$

1 : Initialize $\eta := 0$

2 : **parse h** = (h<sub>1</sub>, ..., h<sub>d+1</sub>) ∈ G<sup>d+1</sup>

3 : **parse** $\mathbf{\Delta} = (\Delta_1, \dots, \Delta_{d+1}) \in (\mathbb{Z}_{p-1})^{d+1}$

4 : On input $S = \{(x_j, y_j, z_j)\}_{j=1}^{|S|} \subset \mathbb{Z}_{p-1} \times \{0, 1\}^* \times \mathbb{Z}_{p-1}$ :

5 : $\eta := \eta + 1$

6 : **if** $\eta \le d$, **return** $\left(H(h_{\eta}^{x_j}, y_j) + z_j \cdot \Delta_{\eta+1} \mod p - 1\right)_{j=1}^{|S|}$

Given a polynomial bound $B = B(\lambda)$, we say that the hash family $H = \{H_\lambda\}_{\lambda \in \mathbb{N}}$ is a *d*-leveled TCCR hash for exponential correlation with $2B-1$ auxiliary powers per level over $\mathbb{G}$ if for every probabilistic polynomial-time adversary $\mathcal{A}$, it holds that

$$
\left| \Pr \left[ \mathcal{A}^{H, \mathcal{O}_{H,h,\Delta}} \left( (h_{i,j})_{i \le d+1} \mid j \in [\pm B]^* \right) \right] - \Pr \left[ \mathcal{A}^{H, \mathcal{R}} \left( (h_{i,j})_{i \le d+1} \mid j \in [\pm B]^* \right) \right] \right| \le \text{negl}(\lambda),
$$

where the probability is taken over the random choice of $(\Delta_i, h_i) \leftarrow_S \mathbb{Z}_{p-1} \times \mathbb{G}$ for $i \in [d]$ and of a random oracle $\mathcal{R}$ that on input a set $S$ of tuples $(x, y, z) \in \mathbb{Z}_{p-1} \times \{0, 1\}^* \times \mathbb{Z}_{p-1}$, outputs $(r_1, \dots, r_{|S|}) \leftarrow_S (\mathbb{Z}_{p-1})^{|S|}$, and where the $h_{i,j}$'s are defined as follows: for $i \in [d]$, set $\alpha_i := G^{\Delta_i} \bmod p$ and define $h_{i,j} := h_i^{\alpha_i}$ for all $j \in [\pm B]^*$.
While the above definition is somewhat involved, the theorem below shows that under the power-DDH assumption, any tweakable correlation-robust hash for the exponential correlation over $\mathbb{G}$ is also a leveled TCCR hash for the exponential correlation with auxiliary powers over $\mathbb{G}$.

**Theorem 7.** Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$, let $H$ be a family of TCR hash functions for exponential correlation over $\mathbb{G}$ (Definition 6), and let $B = B(\lambda)$ be a polynomial bound. Then if the $B$-power-DDH assumption (Definition 4) holds with respect to $\text{GrpGen}^*$, for all polynomial $d = d(\lambda)$, $H$ is a $d$-leveled TCCR hash for exponential correlation with $2B - 1$ auxiliary powers per level over $\mathbb{G}$ (Definition 8).

*Proof.* Consider an arbitrary PPT adversary $\mathcal{A}$ against the $d$-leveled TCCR security of $H$. We will show that $\mathcal{A}$ has negligible advantage by a straightforward hybrid argument.

Let $O_{H,h,\Delta}^{(i)}$ be a stateful oracle that is identical to $O_{H,h,\Delta}$ except for the following: for all queries $S$, it returns $|S|$ uniformly random elements from $\mathbb{Z}_{p-1}$ if $\eta \le i$; otherwise, it responds as in $O_{H,h,\Delta}$. Consider a sequence of hybrids

$\text{Hybrid}_{0,0}, \text{Hybrid}_{0,1}, \dots, \text{Hybrid}_{i,0}, \text{Hybrid}_{i,1}, \text{Hybrid}_{i+1,0}, \dots, \text{Hybrid}_{d,1}$

defined as follows.

* $\text{Hybrid}_{0,0}$: This hybrid denotes $\mathcal{A}^{H, O_{H,h,\Delta}}((h_{i,j})_{i,j})$ as described in Definition 8.

* $\text{Hybrid}_{i,1}$: For each $i \in [d]$, $\text{Hybrid}_{i,1}$ denotes $\mathcal{A}^{H, O_{H,f_i,\Delta}^{(i)}}((h_{i,j})_{i,j})$ where

$$f_i = (f_1, \dots, f_{i+1}, h_{i+2}, \dots, h_{d+1}),$$

$(f_1, \dots, f_{i+1}) \stackrel{\$}{\leftarrow} \mathbb{G}^{i+1}$, and $(\mathbf{h}, \Delta, (h_{i,j})_{i,j})$ are distributed as in $\text{Hybrid}_{i,0}$. In other words, $\text{Hybrid}_{i,1}$ corresponds to the output of the adversary when the oracle returns uniformly random elements from $\mathbb{Z}_{p-1}$ for the first $i$ queries and computes the output as in $O_{H,h,\Delta}$ for the last $d - i - 1$ queries. In the $(i+1)$-th query, it returns $H(f_{i+1}^x, y) + z \cdot \Delta_{i+1} \mod p - 1$ for every $(x, y, z)$ in the queried input $S$.

* $\text{Hybrid}_{i,0}$: For each $i \in \{1, \dots, d\}$, $\text{Hybrid}_{i,0}$ denotes $\mathcal{A}^{H, O_{H,f_i,\Delta}^{(i)}}((h_{i,j})_{i,j})$ where

$$f_i = (f_1, \dots, f_i, h_{i+1}, \dots, h_{d+1}),$$

$(f_1, \dots, f_i) \stackrel{\$}{\leftarrow} \mathbb{G}^i$, and $(\mathbf{h}, \Delta, (h_{i,j})_{i,j})$ are distributed as in $\text{Hybrid}_{i-1,1}$. In other words, $\text{Hybrid}_{i,0}$ corresponds to the output of the adversary when the oracle returns uniformly random elements from $\mathbb{Z}_{p-1}$ for the first $i$ queries and computes the output as in $O_{H,h,\Delta}$ for the last $d - i$ queries.

We next show that, in the sequence of hybrids above, each hybrid is indistinguishable from the next using the following two claims.

**Claim.** If the $B$-power-DDH assumption holds with respect to $\text{GrpGen}^*$ then for every $i \in [d]$, $\text{Hybrid}_{i,0} \stackrel{\$}{\approx} \text{Hybrid}_{i,1}$.

*Proof.* Note that $\text{Hybrid}_0$ is identical to $\mathcal{A}^{H, O_{H,h,\Delta}^{(0)}}((h_{i,j})_{i,j})$ since the oracles $O_{H,h,\Delta}$ and $O_{H,h,\Delta}^{(0)}$ are equivalent in this case. Thus, for any $i \in [d]$, the only difference between $\text{Hybrid}_{i,0}$ and $\text{Hybrid}_{i,1}$ is that the output of the $(i+1)$-th query is computed as $H(h_{i+1}^x, y) + z \cdot \Delta_{i+1} \mod p - 1$ in $\text{Hybrid}_{i,0}$ and as $H(f_{i+1}^x, y) + z \cdot \Delta_{i+1} \mod p - 1$ in $\text{Hybrid}_{i,1}$ for every $(x, y, z) \in S$. However, under the $B$-power-DDH assumption, the uniformly random $f_{i+1}$ is indistinguishable from $h_{i+1}$ given $(h_{i,j})_j$. It then immediately follows that $\text{Hybrid}_{i,0} \stackrel{\$}{\approx} \text{Hybrid}_{i,1}$. $\square$
**Claim.** If H is a TCR hash for exponential correlation over $\mathbb{G}$ then for every $i \in [d-1]$, $\text{Hybrid}_{i,1} \stackrel{\xi}{\approx} \text{Hybrid}_{i+1,0}$.

*Proof.* For any $i \in [d-1]$, the only difference between $\text{Hybrid}_{i,1}$ and $\text{Hybrid}_{i+1,0}$ is that the output of the $(i+1)$-th query is computed as $H(f_{i+1}^x, y) + z \cdot \Delta_{i+1} \mod p - 1$ for a random group element $f_{i+1}$ in $\text{Hybrid}_{i,1}$ while in $\text{Hybrid}_{i+1,0}$, the $(i+1)$-th query's output is a set of uniformly random elements from $\mathbb{Z}_{p-1}$. However, if H is a TCR for exponential correlation then $H(f_{i+1}^x, y)$ and hence the output of the oracle in $\text{Hybrid}_{i,1}$ are indistinguishable from random values in $\mathbb{Z}_{p-1}$. This implies that $\text{Hybrid}_{i,1}$ is indistinguishable from $\text{Hybrid}_{i+1,0}$. $\square$

Since $d$ is polynomial in the security parameter, it follows from the above claims that $\text{Hybrid}_{0,0} \stackrel{\xi}{\approx} \text{Hybrid}_{d,1}$. Moreover, observe that the oracle provided to the adversary in $\text{Hybrid}_{d,1}$ is identical to $\mathcal{R}$, as defined in Definition 8, since it does not use $\mathbf{h} = (h_1, \dots, h_{d+1})$ and returns uniformly random elements from $\mathbb{Z}_{p-1}$ for all $d$ queries. Since $\text{Hybrid}_{0,0} \stackrel{\xi}{\approx} \text{Hybrid}_{d,1}$, we have

$$ \left| \Pr \left[ \mathcal{A}^{\text{H},\text{O}_{\text{H},\text{h,}\Delta}} \left( (h_{i,j})_{\substack{i \le d+1 \\ j \in [\pm B]^*}} \right) \right] - \Pr \left[ \mathcal{A}^{\text{H},\mathcal{R}} \left( (h_{i,j})_{\substack{i \le d+1 \\ j \in [\pm B]^*}} \right) \right] \right| \le \text{negl}(\lambda). $$

■

# 5 Building Blocks

## 5.1 Embedding Polynomials into $\mathbb{Z}_p$

Given a degree-$m$ polynomial $a \in \mathbb{F}_2[X]$, we let $(a[i])_{i \in [m]} \in \mathbb{F}_2^{m+1}$ denote the list of its coefficients. In this work, we manipulate embeddings of polynomials over $\mathbb{Z}_p$. Given parameters $N \ge 2$ and $m \in \mathbb{N}$, let $B(N, m) := (N^{m+1}-1)/(N-1)$. We encode $a \in \mathbb{F}_2[X]$ into $\tilde{a} \in [B(N, \deg(a))]$ by interpreting $a$ as an element of $\mathbb{Z}[X]$ and computing $\tilde{a} := a(N)$. When $|B(N, \deg(a))| < p$ (looking ahead, this will always hold in our constructions), we slightly abuse the notation and view $\tilde{a}$ as an element of $\mathbb{Z}_p$ via the natural embedding from $[p]$ to $\mathbb{Z}_p$. For any $N \ge 2$, $m \in \mathbb{N}$, we let $\text{l}_{N,m} := \{\tilde{a} \in \mathbb{Z}_p : \exists a \in \mathbb{F}_2[X], \deg(a) \le m, \tilde{a} = a(N)\}$ denote the subset of all valid embeddings of degree-at-most-$m$ polynomials to $\mathbb{Z}_p$.

**Procedures.** We introduce below two procedures that are used to manipulate embeddings of polynomials into $\mathbb{Z}_p$. In the procedures below, $\mathbb{Z}_p$ is identified with the subset of integers $\{0, \dots, p-1\}$.

* toPoly$_N(\tilde{a})$ : On input $\tilde{a} \in \mathbb{Z}_p$, parse $\tilde{a} = \sum_{i=0}^m a[i] \cdot N^i$ (the $N$-ary decomposition of $\tilde{a}$) and return $a := \sum_{i=0}^m a[i] \cdot X^i \in \mathbb{Z}[X]$, a degree-$m$ integer polynomial with coefficients in $\{0, N-1\}$. When $N$ is clear from the context, we write $a := \text{toPoly}(\tilde{a})$.

* Mod$_N(\tilde{a}, M)$ : On input $\tilde{a} \in \mathbb{Z}_p$ and a modulus $M$, compute $b := [\text{toPoly}_N(\tilde{a}) \mod M]$ and return $\tilde{b} := b(N)$. When $N$ is clear from the context, we write $\tilde{b} := \text{Mod}(\tilde{a}, M)$.

Above, we let all procedures take variable length inputs: the degree $m$ is inferred from the input and $N$. Furthermore, we let Mod take as second input either an integer $M \in \mathbb{N}$ (in which case $[a \mod M] = b \in \mathbb{Z}_M[X]$) or a polynomial $M \in \mathbb{Z}[X]$ (in which case $[a \mod M] = b \in \mathbb{Z}[X]/M$). We slightly abuse the notation and write, given an integer $n$ and a polynomial $P$, Mod$_N(\tilde{a}, (n, P))$ to denote $\text{Mod}_N(\text{Mod}_N(\tilde{a}, n), P)$ (that is, the function that computes the polynomial associated to $\tilde{a}$, reduces it modulo $n$ and $P$, and embeds back the polynomial in $\mathbb{Z}_n[X]/P$ over the integers).
**Input perturbation.** We introduce a procedure that perturimates an element $a \in \mathbb{F}_2[X]$ in the following sense: the perturbation maps $a$ to a polynomial $a' \in \mathbb{Z}[X]$ such that $a(N) = \text{Mod}_N(a'(N), 2)$ (i.e., $a'$ preserves the parity of the value of the coefficients of $a$, and its coefficients do not overflow $N$), but $a$ can be masked by a random $\mathbb{Z}[X]$-polynomial with small coefficients.

* $\text{Pert}_c(a)$: On input $a \in \mathbb{F}_2[X]$, sample $c$ uniformly random shares $(a_1, \dots, a_c)$ of $a$ over $\mathbb{F}_2[X; \text{deg}(a)]$. Interpret each $a_i$ as a polynomial over $\mathbb{Z}[X]$ and return $a' = \sum_{i=1}^c a_i$ (where the sum is computed over $\mathbb{Z}[X]$).

It is immediate to check that for any $N$ such that $c < N$, it holds that $a(N) = \text{Mod}_N(a'(N), 2)$. The following lemma shows that one can statistically hide $a$ by masking $a' \leftarrow \text{Pert}_c(a)$ with a carefully chosen element $r \in \mathbb{Z}[X]$ with small coefficients such that $\|r\|_{\infty} \le c$. We first define the appropriate distribution over polynomials with small coefficients for integers $m, c$:

* $\text{RandSum}_{m,c}$: Sample $(r_1, \dots, r_c) \leftarrow \mathbb{F}_2[X; m]^c$ and set $r := \sum_{i=1}^c r_i$, where the $r_i$'s are interpreted as polynomials over $\mathbb{Z}[X; m]$. Output $r$.

* $\text{RandSum}_{m,c}(N)$: Sample $r \leftarrow \text{RandSum}_{m,c}$ and output $r(N)$.

It is clear from the definition that for any $r$ in the support of $\text{RandSum}_{m,c}$, we have $\|r\|_{\infty} \le c$. Equipped with the above definition, we have the following lemma:

**Lemma 8.** For any $m, c \in \mathbb{N}$ and $a \in \mathbb{F}_2[X; m]$, denote $\mathcal{D}_{m,c}^{(a)} := \{a' + r : a' \leftarrow \text{Pert}_c(a), r \leftarrow \text{RandSum}_{m,c}\}$ and $\mathcal{D}_{m,c} := \{a' + r : a', r \leftarrow \text{RandSum}_{m,c}\}$. Then:

$$ \text{SD}(\mathcal{D}_{m,c}^{(a)}, \mathcal{D}_{m,c}) \le \frac{m}{2^c}. $$

Using the above procedures, integer encodings can support a limited number of homomorphic additions and multiplications. Concretely, we will use the following simple lemma:

**Lemma 9.** Let $m, T, c, N \in \mathbb{N}$ be integers. Fix any tuple $(a_1, \dots, a_T, b_1, \dots, b_T) \in \mathbb{F}_2[X; m]^{2T}$ and let $b'_i \leftarrow \text{Pert}_c(b_i)$ for $i = 1$ to $T$. Define

$$ v := \sum_{i=1}^{T} a_i \cdot b_i, \qquad \tilde{v} := \sum_{i=1}^{T} a_i(N) \cdot b'_i(N), $$

where the left sum is computed over $\mathbb{F}_2[X]$, and the right sum is computed over $\mathbb{N}$. Then, if $N > T \cdot c \cdot m$, it holds that

$$ v = \text{toPoly}_N(\text{Mod}_N(\tilde{v}, 2)). $$

**Mapping to RandSum samples.** Given a set $S$, we write $\mathbb{U}_S$ to denote the uniform distribution over $S$.

**Definition 9.** We denote by map: $\mathbb{Z}_{p-1} \to \mathbb{Z}_{p-1}$ a mapping such that $\text{map}(\mathbb{U}_{\mathbb{Z}_{p-1}}) \approx_c \text{RandSum}_{m,c}(N)$.

Note that map is implicitly parametrized by $(N, m, c)$; we write $\text{map}_{N,m,c}$ when we want to make the dependency explicit. Concretely, constructing map is done as follows:

* On input $x \in \mathbb{Z}_{p-1}$, set $x' := [x \bmod 2^\lambda]$, and parse $x'$ as an element of $\{0, 1\}^\lambda$. Note that over a uniform choice of $x \leftarrow \mathbb{Z}_{p-1}$, where $p$ is a $2\lambda$-bit prime, the induced distribution of $x'$ is $2^{-\lambda}$-close to uniform over $\{0, 1\}^\lambda$.

* Let PRG: $\{0, 1\}^\lambda \to \{0, 1\}^{c \cdot (m+1)}$ denote a pseudorandom generator. Compute $y = \text{PRG}(x')$ and parse the output as a $c$-tuple $(y_1, \dots, y_c)$ of degree-$m$ $\mathbb{F}_2$-polynomials $y_i \in \mathbb{F}_2[X; m]$.

* Run the $\text{RandSum}_{m,c}(N)$ procedure: compute $r := \sum_{i=1}^c y_i$ over $\mathbb{Z}[X; m]$ and output $r(N)$.
## 5.2 VOLE to OLE Procedure

We start by recalling a power-DDH-based puncturable pseudorandom function (PPRF) introduced recently in [CHHK25], which is at the heart of our construction (we do not recall the formal definition of PPRFs, as we will directly use the construction below rather than abstracting it out as a PPRF). Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$. We let $H = \{H_\lambda : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}$ denote a family of hash functions over $\mathbb{G} \times \{0, 1\}^*$.

<table><thead><tr><th></th><th>F.setup(1<sup>λ</sup>, B)</th><th>F.Punct(mpk, Γ<sub>E</sub>)</th></tr></thead><tbody><tr><td>1 :</td><td>(G, p, g, G) := GrpGen<sup>*</sup>(1<sup>λ</sup>)</td><td>1 :</td><td>parse p, G from mpk</td></tr><tr><td>2 :</td><td>(Δ, h) ← $\mathbb{Z}_{p-1} \times \mathbb{G}$</td><td>2 :</td><td>return psk = G<sup>Γ<sub>E</sub></sup> mod p</td></tr><tr><td>3 :</td><td>α := G<sup>Δ</sup> mod p</td><td>F<sup>H</sup>(k, x, salt) := F.Eval<sup>H</sup>(k, x, salt)</td><td></td></tr><tr><td>4 :</td><td>for i ∈ [±B], h<sub>i</sub> := h<sup>α<sup>i</sup></sup></td><td>1 :</td><td>parse k as (msk, sk)</td></tr><tr><td>5 :</td><td>mpk := (G, p, G, (h<sub>i</sub>)<sub>i∈[±B]</sub>)</td><td>2 :</td><td>parse (h<sub>i</sub>)<sub>i∈[±B]</sub> from msk</td></tr><tr><td>6 :</td><td>msk := (mpk, Δ, h<sub>0</sub>)</td><td>3 :</td><td>return H(h<sub>x</sub><sup>sk</sup>, salt)</td></tr><tr><td>7 :</td><td>return (mpk, msk)</td><td></td><td></td></tr><tr><td></td><td>F.KeyGen(mpk, Γ<sub>G</sub>)</td><td>pF<sup>H</sup>(k<sup>*</sup>, z, x, salt) := F.PEval<sup>H</sup>(k<sup>*</sup>, z, x, salt)</td><td></td></tr><tr><td>1 :</td><td>parse p, G from mpk</td><td>1 :</td><td>parse k<sup>*</sup> as (mpk, psk)</td></tr><tr><td>2 :</td><td>return sk = G<sup>Γ<sub>G</sub></sup> mod p</td><td>2 :</td><td>parse (h<sub>i</sub>)<sub>i≠0</sub> from mpk</td></tr><tr><td></td><td></td><td>3 :</td><td>return H(h<sub>x-z</sub><sup>psk</sup>, salt)</td></tr></tbody></table>

**Lemma 10** (Correctness of the PPRF). Fix an arbitrary polynomial modulus $B$ and let $H = \{H_\lambda : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}$ denote a family of hash functions over $\mathbb{G}$. Let (mpk, msk) be a master key pair in the support of $F.setup(1^\lambda, B)$. Parse msk as (mpk, $\Delta$, $h_0$). Fix any constraint $z \in \{0, \dots, B\}$. Then for any $\Gamma_E, \Gamma_G \in \mathbb{Z}_{p-1}$ such that $\Gamma_E - \Gamma_G = \Delta \cdot z$, denoting sk := $F.KeyGen(mpk, \Gamma_G)$, psk := $F.Punct(mpk, \Gamma_E)$, k := (msk, sk), and $k^* := (mpk, psk)$, it holds that for any input $x \in \{0, \dots, B\} \setminus \{z\}$ and salt $\sigma \in \{0, 1\}^*$,

$$F^H(k, x, \text{salt}) = pF^H(k^*, z, x, \text{salt}).$$

In [CHHK25], it is shown that if $H$ is a tweakable correlation-robust hash function for exponential correlations over $\mathbb{G}$ and if the power-DDH assumption holds, then the above PPRF satisfies a strong notion of pseudorandomness: all evaluations $F^H(k, z, \text{salt})$ at the punctured point look pseudorandom given $k^{**}$, even when the adversary is allowed to request multiple pairs $(k, k^*)$ for the same master secret key msk. We do not formally state this security notion here: we will instead directly prove the security of our garbling scheme constructed from this primitive.

**A VOLE-to-OLE procedure.** Given a security parameter $\lambda$, fix integers $N = N(\lambda)$, $m = m(\lambda)$ such that $N^m = \text{poly}(\lambda)$. Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$ and $H = \{H_\lambda : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}$. Fix a master key pair (mpk, msk) $\leftarrow \text{ Setup}(1^\lambda, N^m)$ and parse msk as (mpk, $\Delta$, $h_0$). A core building block of our garbling scheme is a one-message (from $G$ to $E$) VOLE-to-OLE protocol where $G$ and $E$ hold respective inputs $(v_G, v_E) \in \mathbb{Z}_{p-1} \times I_{N,m}$ and shares of $\Delta \cdot v_E$, and obtain as output shares of $v_G v_E$.
$VtO_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt})$

1: sk := F.KeyGen(msk, $\langle \Delta v_E \rangle_G$)

2: k := (msk, sk)

3: shift := $\sum_{x \in I_{N,m}} F^H(k, x, \text{salt}) + v_G$

4: $z_G := \sum_{x \in I_{N,m}} x \cdot F^H(k, x, \text{salt})$

5: return (shift, $z_G$)

$VtO_E^H(\text{mpk}, v_E, \langle \Delta v_E \rangle_E, \text{salt, shift})$

1: psk := F.Punct(mpk, $\langle \Delta v_E \rangle_E$)

2: $k^* := (\text{mpk}, \text{psk})$

3: $z_E := \sum_{x \in I_{N,m}} (x - v_E) \cdot pF^H(k^*, v_E, x, \text{salt}) + v_E \cdot \text{shift}$

4: return $z_E$

We will consider two variants of the above procedure. In the first variant, the computation of (shift, $z_G$, $z_E$) is done over the integers, while in the second variant, the computation is done over $\mathbb{Z}_{p-1}$. In the first case, $v_G$, $v_E$, and all outputs of H are treated as positive integers in $[p-2] \subset \mathbb{Z}$. We will write $\mathcal{R}-VtO_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt})$ and $\mathcal{R}-VtO_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt})$ to explicitly indicate that computation takes place over a ring $\mathcal{R} \in \{\mathbb{Z}, \mathbb{Z}_{p-1}\}$. By default, if no ring is indicated, the computation happens over $\mathbb{Z}_{p-1}$.

**Remark 1.** The VtO procedure is identical to the VOLE-to-OLE procedure introduced in [CHHK25], up to a minor difference: instead of summing over all possible inputs $x$ between 0 and the bound $B = N^m$, we leverage the fact that the evaluator input $v_E$ will always be the embedding $v(N) \in I_{N,m}$ of some $\mathbb{F}_2$-polynomial $v \in \mathbb{F}_2[X; m]$. Since this is known to both parties, they can restrict the sums in the VtO procedures to be over valid embeddings, which reduces the number of terms in the sum from $N^m$ to $2^m$. This minor modification is crucial to control the growth of the size of the output share, which in turns influences the amount of garbling material per gate in our Boolean garbling scheme.

**Correctness.** The following lemma establishes perfect correctness of VtO:

**Lemma 11.** For every $\mathcal{R} \in \{\mathbb{Z}, \mathbb{Z}_{p-1}\}$, every (mpk, msk) in the support of F Gibbison and Hwang's Setup with msk := (mpk, $\Delta$, $h_0$), every $v_E \in I_{N,m}$, every $v_G \in \mathbb{Z}_{p-1}$, every salt $\in \{0, 1\}^*$, and every $\langle \Delta v_E \rangle_G, \langle \Delta v_E \rangle_E$ such that $\langle \Delta v_E \rangle_E - \langle \Delta v_E \rangle_G = \Delta_E$, denoting (shift, $z_G$) := $\mathcal{R}$-VtO$_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt})$ and $z_E := \mathcal{R}$-VtO$_E^H(\text{mpk}, v_E, \langle \Delta v_E \rangle_E, \text{salt, shift})$, it holds that $z_E - z_G = v_E v_G$ (over $\mathcal{R}$). Furthermore, if $\mathcal{R} = \mathbb{Z}$, then $z_G, z_E$ are positive integers.

The last part of the lemma follows immediately from the definition of $z_G$ and the first part of the lemma. The proof of the first part is a routine check:

$$
\begin{align*}
z_E &= \sum_{x \in I_{N,m}} (x - v_E) \cdot pF^H(k^*, v_E, x, \text{salt}) + v_E \cdot \text{shift} \\
&= \sum_{x \in I_{N,m}} (x - v_E) \cdot F^H(k, x, \text{salt}) + v_E \cdot \text{shift} \quad \triangleright \text{ via Lemma 10} \\
&= z_G - v_E \cdot (\text{shift} - v_G) + v_E \cdot \text{shift} = z_G + v_E v_G.
\end{align*}
$$

**Simulating shifts using $O_{H,h_0,\Delta}$.** We define a simulator for VtO, that will be used in our security analysis, that simulates shift and $z_E$ using only mpk, psk, and calls to the oracle $O_{H,h,\Delta}$ from Definition 7. To handle the case where the garbler input $v_G$ is an affine function of $\Delta$ (as this is the case in some parts of the garbling procedure), the simulator takes two additional inputs $(a, b)$ such that $v_G = a \cdot \Delta + b$. Intuitively, the $\Delta \cdot a$ term will be computed within $O_{H,h_0,\Delta}$, and the simulator adds $b$ to the output.

Some of our procedures also use $VtO^H_0$ with a hash function $H_0$ defined as $H_0 := \text{map} \circ \mathbb{H}$ for a suitable mapping map. To handle this usecase, we also consider a variant of SimVtO, denoted Sim'VtO, that takes
as input the map $\mathcal{M}$. As $\mathcal{M}$ will always be equal to 0 when using this variant, we omit it from the inputs.

Fix integers $N = N(\lambda)$, $m = m(\lambda)$ such that $N^m = \text{poly}(\lambda)$. Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$ and $H = \{H_\lambda : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}_\lambda$. Fix a master key pair (mpk, msk) $\leftarrow \text{F}\text{Setup}(1^\lambda, N^m)$ and parse msk as (mpk, $\Delta$, $h_0$). Let $O := O_{H,h_0,\Delta}$ be the oracle defined in Definition 7.

$\text{SimVtO}^{H,O}(\text{mpk}, v_E, (\Delta v_E)_E, a, b, \text{salt})$

1 : psk := F.Punct(mpk, (Δv_E)_E)

2 : k* := (mpk, psk)

3 : **for** x ∈ I_{N,m} \ {v_E} :

4 : y_x := pF^H(k^*, v_E, x, salt)

5 : shift := $\sum_{x \in I_{N,m} \setminus \{v_E\}} y_x + O(\text{psk}, \text{salt}, a) + b$

6 : z_E := VtO_E^H(\text{mpk}, v_E, (\Delta v_E)_E, \text{salt}, shift)

7 : **return** (shift, z_E)

$\text{Sim}'\text{VtO}^{H,O}(\text{mpk}, v_E, (\Delta v_E)_E, \text{map}, b, \text{salt})$

1 : psk := F.Punct(mpk, (Δv_E)_E)

2 : k* := (mpk, psk)

3 : **for** x ∈ I_{N,m} \ {v_E} :

4 : y_x := \text{map} (pF^H(k^*, v_E, x, salt))

5 : shift := $\sum_{x \in I_{N,m} \setminus \{v_E\}} y_x + \text{map}(O(\text{psk}, \text{salt}, 0)) + b$

6 : z_E := VtO_E^{H_0}(\text{mpk}, v_E, (\Delta v_E)_E, \text{salt}, shift)

7 : **return** (shift, z_E)

As for VtO, the computation can be performed either over $\mathbb{Z}$ or $\mathbb{Z}_{p-1}$; we write $\mathcal{R}$-SimVtO to indicate the ring explicitly. The following lemma states that SimVtO outputs the exact same shift as VtO_G^H and the same $z_E$ as VtO_E^H:

**Lemma 12 (Perfect simulation).** For every (mpk, msk) in the support of $\text{F}\text{Setup}(1^{\lambda}, N^m)$ with msk $:= (\text{mpk}, \Delta, h_0)$, every $v_E \in I_{N,m}$, every $v_G \in \mathbb{Z}_{p-1}$, every pair $(a, b) \in \mathbb{Z}_{p-1}^2$ such that $v_G = a \cdot \Delta + b$, every salt $\in \{0, 1\}^*$, and every $(\Delta v_E)_G, (\Delta v_E)_E$ such that $(\Delta v_E)_E - (\Delta v_E)_G = \Delta v_E$, denoting $O := O_{H,h_0,\Delta}$, denoting (shift, $z_E$) $:= \text{SimVtO}^{H,O}(\text{mpk}, v_E, (\Delta v_E)_E, a, b, \text{salt})$, it holds that

$$ (\text{shift}, -) = \text{VtO}_G^H(\text{msk}, v_G, (\Delta v_E)_G, \text{salt}), \text{ and} $$

$$ z_E = \text{VtO}_E^H(\text{mpk}, v_E, (\Delta v_E)_E, \text{salt}, \text{shift}). $$

Furthermore, for any map : $\mathbb{Z}_{p-1} \to \{0, 1\}^*$, setting $H_0 := \text{map} \circ H$ and (shift', $z'_E$) $:= \text{Sim}'\text{VtO}^{H,O}(\text{mpk}, v_E, (\Delta v_E)_E, \text{map}, v_G, \text{salt})$, it holds that

$$ (\text{shift}', -) = \text{VtO}_G^{H_0}(\text{msk}, v_G, (\Delta v_E)_G, \text{salt}), \text{ and} $$

$$ z'_E = \text{VtO}_E^{H_0}(\text{mpk}, v_E, (\Delta v_E)_E, \text{salt}, \text{shift}). $$

*Proof.* Let $k^* := (\text{mpk}, \text{psk})$ where psk $:= \text{F}\text{Punct}(\text{mpk}, (\Delta v_E)_E)$. Observe that for shift computed using $\text{VtO}_G^H(\text{msk}, v_G, (\Delta v_E)_G, \text{salt})$, we have,

$$ \text{shift} = \sum_{x \in I_{N,m}} F^H(k, x, \text{salt}) + v_G $$

$$ = \sum_{x \in I_{N,m} \setminus \{v_E\}} pF^H(k^*, v_E, x, \text{salt}) + F^H(k, x, \text{salt}) + a\Delta + b \quad \triangleright \text{ via Lemma 10} $$

$$ = \sum_{x \in I_{N,m} \setminus \{v_E\}} pF^H(k^*, v_E, x, \text{salt}) + O(\text{psk}, \text{salt}, a) + b \quad \triangleright \text{ via Definition 7} $$

where the last expression is equal to shift as computed in $\text{SimVtO}^{H,O}(\text{mpk}, v_E, (\Delta v_E)_E, a, b, \text{salt})$. It then immediately follows that $z_E$, as computed by $\text{SimVtO}^{H,O}$, is equal to $z_E$ output by $\text{VtO}_E^H$, since $\text{SimVtO}^{H,O}$ simply runs $\text{VtO}_E^H$ using the shift it computes. It is easy to see that a similar argument shows that shift' and $z'_E$, as output by $\text{Sim}'\text{VtO}^{H,O}$, are identical to shift' and $z'_E$ output by $\text{VtO}_G^{H_0}$ and $\text{VtO}_E^{H_0}$ respectively. ■
## 5.3 Batch Function Evaluation on Authenticated Shares

We now introduce a second core procedure. It builds upon the following observation from [CHHK25] (a similar observation was also made in previous works, e.g., [Hea24]): the VtO procedure can be modified to convert shares of $\Delta \cdot v_E$ into shares of $v_G \cdot f(v_E)$ for an arbitrary function $f$ (known to the parties): it suffices to compute instead $z_G := \sum_x f(x) \cdot F^H(k, x, \text{salt})$ and $z_E := \sum_x (f(v_E) - f(x)) \cdot pF^H(k^*, v_E, x, \text{salt}) + f(v_E) \cdot \text{shift}$.

A useful implication of this functional VtO procedure is that the parties can evaluate an arbitrary function on authenticated shares: given shares of $\Delta \cdot v_E$, they can obtain shares of $\Delta \cdot f(v_E)$ by letting G set $\Delta$ to be its input to the functional VtO procedure. In this work, we make an additional observation which, while very simple in hindsight, proves to be very powerful: this “functional authentication” procedure can be generalized to allow the evaluation of an arbitrary-size tuple of functions $f_1, f_2, \dots$ on an authenticated share without any penalty in communication. Indeed, the shift transmitted from G to E depends solely on its input $v_G$ (set here to $\Delta$), and not on the target function $f$. Hence, if G and E want to obtain shares of $\Delta \cdot f_i(v_E)$ for many functions $i$, they can run arbitrarily many parallel executions of the functional authentication procedure using the transmission of a single shift from G to E, independent of the number of functions. We describe the procedure below.

**The batch functional authentication procedure.** For $i = 1$ to $q$, let $f_i : I_{N,m} \to \mathbb{Z}_{p-1}$ denote a public function. We let $q$ unspecified and assume that BatchfAuth takes variable-length inputs.

BatchfAuth<sup>H</sup><sub>G</sub>(msk, $\Delta'$, $\langle \Delta v_E \rangle_G$, $(f_1, \dots, f_q)$, salt)

1. sk := F.KeyGen(msk, $\langle \Delta v_E \rangle_G$)

2. k := (msk, sk)

3. shift := $\sum_{x \in I_{N,m}} F^H(k, x, \text{salt}) + \Delta'$

4. for $i = 1$ to $q$ :

5. $z_G[i] := \sum_{x \in I_{N,m}} f_i(x) \cdot F^H(k, x, \text{salt})$

6. return (shift, $z_G$)

BatchfAuth<sup>H</sup><sub>E</sub>(mpk, $v_E$, $\langle \Delta v_E \rangle_E$, $(f_1, \dots, f_q)$, salt, shift)

1. psk := F.Punct(mpk, $\langle \Delta v_E \rangle_E$)

2. k* := (mpk, psk)

3. for $x \in I_{N,m} \setminus \{v_E\}$ :

4. $y_x := pF^H(k^*, v_E, x, \text{salt})$

5. for $i = 1$ to $q$ :

6. $z_E[i] := \sum_{x \in I_{N,m}} (f_i(x) - f_i(v_E)) \cdot y_x + f_i(v_E) \cdot \text{shift}$

7. return $z_E$

We will also use a variant of BatchfAuth, denoted S-BatchfAuth, where the set $I_{N,m}$ of the summands is replaced with another set $S$ (that is, the sums for shift, $z_G[i]$, and $z_E[i]$ are over all $x \in S$).

**Correctness.** The following lemma establishes perfect correctness of the BatchfAuth procedure:

**Lemma 13.** For every (mpk, msk) in the support of F Gibb[1, N<sup>m</sup>] with msk := (mpk, A, h<sub>0</sub>), every $v_E \in I_{N,m}$, every $\Delta' \in \mathbb{Z}_{p-1}$, every $\langle \Delta v_E \rangle_G$, $\langle \Delta v_E \rangle_E$ such that $\langle \Delta v_E \rangle_E - \langle \Delta v_E \rangle_G = \Delta \cdot v_E \bmod p - 1$, every $q \ge 1$, every q-tuple $(f_1, \dots, f_q)$ of functions $f_i : I_{N,m} \to \mathbb{Z}_{p-1}$, and every salt $\in \{0, 1\}^*$, denoting (shift, $z_G$) := BatchfAuth<sup>H</sup><sub>G</sub>(msk, $\Delta'$, $\langle \Delta v_E \rangle_G$, $(f_1, \dots, f_q)$, salt) and $z_E := \text{BatchfAuth<sup>H</sup><sub>E</sub>(mpk, }v_E, \langle \Delta v_E \rangle_E, (f_1, \dots, f_q), \text{ salt, shift})$, for all $i \le q$, it holds that

$$z_E[i] - z_G[i] = \Delta' \cdot f_i(v_E) \bmod p - 1.$$

The proof is again routinely checked using the correctness of the PPRF at all points $x \neq v_E$, and using
the fact that $f(x) - f(v_E) = 0$ when $x = v_E$:

$$
\begin{align*}
z_E &= \sum_{x \in I_{N,m}} (f(x) - f(v_E)) \cdot \mathrm{pF}^H(k^*, v_E, x, \text{salt}) + f(v_E) \cdot \text{shift} \\
&= \sum_{x \in I_{N,m}} (f(x) - f(v_E)) \cdot \mathrm{F}^H(k, x, \text{salt}) + f(v_E) \cdot \text{shift} \quad \triangleright \text{ via Lemma 10} \\
&= z_G - v_E \cdot \sum_{x \in I_{N,m}} \mathrm{F}^H(k, x, \text{salt}) + f(v_E) \cdot \left( \sum_{x \in I_{N,m}} \mathrm{F}^H(k, x, \text{salt}) + v_G \right) \\
&= z_G + v_G \cdot f(v_E).
\end{align*}
$$

**Simulating shifts using $O_{H,h_0,\Delta}$.** We outline a simulator for (shift, $z_E$) for the case $\Delta' = \Delta$ (used in our main construction). The case where $\Delta'$ is independent of $\Delta$ (used for our result in the standard model) is discussed afterwards. Fix integers $N = N(\lambda)$, $m = m(\lambda)$ such that $N^m = \text{poly}(\lambda)$. Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$ and $H = \{H_\lambda : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}$. Fix a master key pair (mpk, msk) $\leftarrow \$ \text{F}\text{Setup}(1^\lambda, N^m)$ and parse msk as (mpk, $\Delta$, $h_0$). Let $O := O_{H,h_0,\Delta}$ be the oracle defined in Definition 7.

SimBatchfAuth$^{H,O}$(mpk, $v_E$, $\langle \Delta v_E \rangle_E$, $(f_1, \dots, f_q)$, salt)

1. psk := F.Punct(mpk, $\langle \Delta v_E \rangle_E$)

2. $k^* := (mpk, psk)$

3. shift := $\sum_{x \in I_{N,m} \setminus \{v_E\}} \mathrm{pF}^H(k^*, v_E, x, \text{salt}) + O(\text{psk}, \text{salt}, 1)$

4. $z_E := \text{BatchfAuth}_E^H(\text{mpk}, v_E, \langle \Delta v_E \rangle_E, (f_1, \dots, f_q), \text{salt}, \text{shift})$

5. **return** (shift, $z_E$)

As for BatchfAuth, we let $S$-SimBatchfAuth$^{H,O}$ denote the variant where the sum is computed over $S \setminus \{v_E\}$. The following lemma states that SimVtO outputs the exact same shift as $\text{VtO}_G^H$ and the same $z_E$ as $\text{VtO}_E^H$:

**Lemma 14 (Perfect simulation).** For every (mpk, msk) in the support of $\text{F}\text{Setup}(1^\lambda, N^m)$ with msk := (mpk, $\Delta$, $h_0$), every $v_E \in I_{N,m}$, and every $\langle \Delta v_E \rangle_G$, $\langle \Delta v_E \rangle_E$ such that $\langle \Delta v_E \rangle_E - \langle \Delta v_E \rangle_G = \Delta v_E$, every $q \ge 1$, every $q$-tuple $(f_1, \dots, f_q)$ of functions $f_i : I_{N,m} \to \mathbb{Z}_{p-1}$, and every salt $\in \{0, 1\}^*$, denoting $O := O_{H,h_0,\Delta}$, denoting (shift, $z_E) := \text{SimBatchfAuth}^{H,O}(\text{mpk}, v_E, \langle \Delta v_E \rangle_E, (f_1, \dots, f_q)$, salt), it holds that

$\text{shift} = \text{BatchfAuth}_G^H(\text{msk}, \Delta, \langle \Delta v_E \rangle_G, (f_1, \dots, f_q), \text{salt}, \text{and}$

$z_E = \text{BatchfAuth}_E^H(\text{mpk}, v_E, \langle \Delta v_E \rangle_E, (f_1, \dots, f_q), \text{salt}, \text{shift}).$

The straightforward proof, which is essentially identical to that of Lemma 12, is omitted.

**Remark 2.** The case where BatchfAuth uses a $\Delta'$ independent of $\Delta$, as in our standard model construction, is obtained as a simple variant of the above procedure by letting $\text{SimBatchfAuth}^{H,O}$ additionally take $\Delta'$ as input and computing instead shift as

$$
\text{shift} := \sum_{x \in I_{N,m} \setminus \{v_E\}} \mathrm{pF}^H(k^*, v_E, x, \text{salt}) + O(\text{psk}, \text{salt}, 0) + \Delta'.
$$
# 6 $\omega(1/\lambda)$-Rate Boolean Garbling Scheme from Generic Groups

We prove in this section the following theorem:

**Theorem 15.** There exists a polynomial $B(\lambda) = \text{poly}(\lambda)$ such that, given a group $\mathbb{G}$ of order $p$ (whose elements are of size $O(\lambda)$ bits), if there exists a TCCR hashing $H$ for exponential correlation with $B$ auxiliary powers over $\mathbb{G}$, then there exists a Boolean garbling scheme $\text{GC} = (\text{GC}.\text{Garble}, \text{GC}.\text{Enc}, \text{GC}.\text{Eval}, \text{GC}.\text{Dec})$ such that for each circuit $C$ whose layers contain at least $\sqrt{\log \lambda}$ gates, it holds that

$$|\hat{C}| = \frac{\lambda}{\sqrt{\log(\lambda)}} \cdot O(|C|) + \text{poly}(\lambda).$$

For extremely narrow circuits, the above cost can grow by up to an additive $O(\lambda \cdot D)$ factor.

## 6.1 High Level Structure

For convenience, we first describe the garbling procedure by abstracting out the gadgets used to compute the keys and labels for batches of XOR and AND gates and for packing/unpacking keys and labels into batches. The garbling scheme uses the following parameters:

* $t$: the number of bits in a batch. Concretely, we will set $t = \sqrt{\log \lambda}$.

* $m$: the degree of the extension field $\mathbb{F}_{2^m}$ where batches of $t$ bits are embedded via the $(t, m)_2$-RMFE $(\Phi, \Psi)$. Using Lemma 4, we have $m = O(t)$.

* $c$: a statistical security parameter for hiding perturbed polynomials. Our construction guarantees security up to a $\text{poly}(\lambda)/2^c$ statistical leakage probability. Concretely, we will set $c$ to $2^{\sqrt{\log \lambda}}$.

* $N$: a size parameter for embedding polynomials into integers without overflows. Our construction requires $N > 2c \cdot m \cdot (2^m + 1)$, and $N^m \le \text{poly}(\lambda)$. Using our parameters $m = O(\sqrt{\log \lambda})$ and $c = 2^{\sqrt{\log \lambda}}$ yields $c^m \cdot (m \cdot (2^m + 1))^m = \text{poly}(\lambda)$, as required.

**Parameters.** Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$. Let $t = \sqrt{\log \lambda}$ denote the batch parameter and $(\Phi, \Psi)$ be a $(t, m)_2$-reverse multiplication friendly embedding with $m = O(t)$. Let $c = \omega(1)$ denote a statistical security parameter with $c \le 2^{\sqrt{\log \lambda}}$ and set $N = 2c \cdot m \cdot (2^m + 1) + 1$ (note that $N^m = \text{poly}(\lambda)$). Let $H = \{H_\lambda : \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}_{\lambda \in \mathbb{N}}$ denote a TCCR hash family for exponential correlation with auxiliary powers over $\mathbb{G}$. Let $H_0 := \text{map} \circ H$, where $\text{map} = \text{map}_{N,m,c}$ is the mapping from Definition 9.

**Input.** The input to $\text{GC}.\text{Garble}$ is a boolean circuit $C$ with $|C| = s$ gates, $n = |I(C)|$ inputs, and depth $\text{depth}(C) = D$. Without loss of generality, we assume that the gates of $C$ are divided into $D$ layers, denoted $\mathcal{L}_1, \dots, \mathcal{L}_D$, where each layer contains either only AND gates or only XOR gates. All incoming wires of gates in a layer are connected to inputs or to gates from previous layers (in particular, the gates in $\mathcal{L}_1$ are only connected to input gates). Each layer $\mathcal{L}_d$ is partitioned into $n_d := \lceil |\mathcal{L}_d|/t \rceil$ batches $(\mathcal{B}_{d,1}, \dots, \mathcal{B}_{d,n_d})$ containing at most $t$ gates each. For $d = 1$ to $D$, let $\text{salt}_{d,1}, \dots, \text{salt}_{d,n_d}$ denote unique identifiers for each batch of gate, and write $\text{salt}_{d,i,j} := \text{salt}_{d,i}||j$ for $j = 0, 1, 2, 3$. We assume that all these data can be parsed from the description $C$ of the circuit.

**Algorithms.** The algorithms $(\text{GC}.\text{Garble}, \text{GC}.\text{Enc}, \text{GC}.\text{Eval}, \text{GC}.\text{Dec})$ are represented below. The algorithms $\text{GC}.\text{Garble}$ and $\text{GC}.\text{Eval}$ rely on subprocedures, respectively $(\text{Pack}_G^H, \text{BatchAND}_G^H, \text{UnpackAND}_G^H, \text{BatchXOR}_G^H, \text{UnpackXOR}_G^H)$ and $(\text{Pack}_E^H, \text{BatchAND}_E^H, \text{UnpackAND}_E^H, \text{BatchXOR}_E^H, \text{UnpackXOR}_E^H)$, that are described afterwards.
**Algorithm GC.Garble(1<sup>λ</sup>, C)**

**Input.** A boolean circuit $C$ with $|C|=$ s gates and depth($C$) = $D$ represented as described in Section 6.1. The input gates are indexed from 1 to $n$.

**Initialization.**

* Sample (mpk, msk) ←$F$.Setup(1<sup>λ</sup>, N<sup>m</sup>). Parse msk := (mpk, Δ, g<sub>0</sub>).

* For each input wire $i$, sample $(k_i, K_i)$ ←$\{0, 1\} \times \mathbb{Z}_{p-1}$.

**Procedure.** The garbling proceeds in a layer-by-layer fashion, from $\mathcal{L}_1$ to $\mathcal{L}_D$. After evaluating a layer $\mathcal{L}_d$, it labels each gate $u$ in the layer with a pair $(k_u, K_u)$ and stores a garbling $\hat{\mathcal{L}}_d$ of $\mathcal{L}_d$.

**On layer $\mathcal{L}_d$.** For $i = 1$ to $n_d$,

* Let $\text{Left}_{d,i}$ (resp. $\text{Right}_{d,i}$) denote the multisets of gates that are the left parent (resp. right parent) of a gate in $\mathcal{B}_{d,i}$. Retrieve the pairs $(k_u, K_u)$ labeling each $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$ and compute

$$ (k_l, K_l, \text{shift}_{l,d,i}) := \text{Pack}_{\mathcal{G}}^{\mathcal{H}}(\text{msk}, (k_u, K_u)_{u \in \text{Left}_{d,i}}, \text{salt}_{d,i,0}) $$

$$ (k_r, K_r, \text{shift}_{r,d,i}) := \text{Pack}_{\mathcal{G}}^{\mathcal{H}}(\text{msk}, (k_u, K_u)_{u \in \text{Right}_{d,i}}, \text{salt}_{d,i,1}). $$

* If $\mathcal{L}_d$ is an AND layer:

- $(k_{\text{out}}, K_{\text{out}}, S_{d,i}) \leftarrow \text{BatchAND}_{\mathcal{G}}^{\mathcal{H}}(\text{msk}, (k_l, K_l), (k_r, K_r), \Delta, \text{salt}_{d,i,2})$

- $((k[j], K_j)_{0 \le i \le t-1}, \text{shift}_{\text{out},d,i}) := \text{UnpackAND}_{\mathcal{G}}^{\mathcal{H}}(\text{msk}, k_{\text{out}}, K_{\text{out}}, \text{salt}_{d,i,3})$

- $(k_u, K_u)_{u \in \mathcal{B}_{d,i}} := (k[j], K_j)_{0 \le j \le |\mathcal{B}_{d,i}| - 1}$

* If $\mathcal{L}_d$ is a XOR layer:

- $(k_{\text{out}}, K_{\text{out}}, S_{d,i}) \leftarrow \text{BatchXOR}_{\mathcal{G}}^{\mathcal{H}}(\text{msk}, (k_l, K_l), (k_r, K_r), \Delta, \text{salt}_{d,i,2})$

- $((k[j], K_j)_{0 \le j \le t-1}, \text{shift}_{\text{out},d,i}) := \text{UnpackXOR}_{\mathcal{G}}^{\mathcal{H}}(\text{msk}, k_{\text{out}}, K_{\text{out}}, \text{salt}_{d,i,3})$

- $(k_u, K_u)_{u \in \mathcal{B}_{d,i}} := (k[j], K_j)_{0 \le j \le |\mathcal{B}_{d,i}| - 1}$

* Label each $u \in \mathcal{B}_{d,i}$ with the key pair $(k_u, K_u)$.

$$ \text{Set } \hat{\mathcal{L}}_d := (\text{shift}_{l,d,i}, \text{shift}_{r,d,i}, S_{d,i}, \text{shift}_{\text{out},d,i})_{i \le n_d}. $$

**Output.** Return $e := ((k_i, K_i)_{i \le n}, \Delta)$, $\hat{C} := (C, \text{mpk}, (\hat{\mathcal{L}}_d)_{d \le D})$, and $d := (k_o)_{o \in O(C)}$.

<caption>Algorithm 1: Garbling procedure of the Boolean garbling scheme</caption>

**Algorithm GC.Enc(e, x)**

**Input.** Encoding information e and input $x \in \{0, 1\}^n$. Parse e := $((k_i, K_i)_{i \le n}, \Delta)$.

**Procedure.** For $i = 1$ to $n$, set $(\ell_i, L_i) := (k_i \oplus x_i, K_i + \Delta \cdot \ell_i \mod p - 1)$.

**Output.** Return $\hat{x} := (\ell_i, L_i)_{i \le n}$.
Algorithm 2: Encoding procedure of the Boolean garbling scheme

We now describe the evaluation procedure. It maintains the invariant that on each gate u carrying a value $y_u$, the keys and labels computed by the garbler and evaluator respectively satisfy $(\ell_u, L_u) = (k_u \oplus y_u, K_u + \Delta \cdot \ell_u \mod p - 1)$.

**Algorithm GC.Eval($\hat{C}$, $\hat{x}$)**

**Inputs.** Parse $\hat{C}$ as $(C, mpk, (\hat{\mathcal{L}}_d)_{d \le D})$ and $\hat{x}$ as $(\ell_i, L_i)_{i \le n} \in (\mathbb{F}_2 \times \mathbb{Z}_{p-1})^n$.

**Procedure.** The evaluation proceeds in a layer-by-layer fashion, from $\mathcal{L}_1$ to $\mathcal{L}_D$. After evaluating a layer $\mathcal{L}_d$, it labels each gate $u$ in the layer with a pair $(\ell_u, L_u)$.

**On layer $\mathcal{L}_d$.** For $i = 1$ to $n_d$,

* Parse $\hat{\mathcal{L}}_d$ as $\hat{\mathcal{L}}_d := (\text{shift}_{l,d,i}, \text{shift}_{r,d,i}, S_{d,i})_{i \le n_d}, \text{shift}_{\text{out},d,i})$.

* Let $\text{Left}_{d,i}$ (resp. $\text{Right}_{d,i}$) denote the multisets of gates that are the left parent (resp. right parent) of a gate in $\mathcal{B}_{d,i}$. Retrieve the pairs $(\ell_u, L_u)$ labeling each $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$ and compute

$$ (\ell_l, L_l) := \text{Pack}^{\text{H}}(\text{mpk}, (\ell_u, L_u)_{u \in \text{Left}_{d,i}}, \text{salt}_{i,d,0}, \text{shift}_{l,d,i}) $$

$$ (\ell_r, L_r) := \text{Pack}^{\text{H}}(\text{mpk}, (\ell_u, L_u)_{u \in \text{Right}_{d,i}}, \text{salt}_{i,d,1}, \text{shift}_{r,d,i}). $$

* If $\mathcal{L}_d$ is an AND layer:

$$ - (\ell_{\text{out}}, L_{\text{out}}) := \text{BatchAND}^{\text{H}}(\text{mpk}, (\ell_l, L_l), (\ell_r, L_r), \text{salt}_{d,i,2}, S_{d,i}) $$

$$ - (\ell[j], L_j)_{0 \le j \le t-1} := \text{UnpackAND}^{\text{H}}(\text{mpk}, \ell_{\text{out}}, L_{\text{out}}, \text{salt}_{d,i,3}, \text{shift}_{\text{out},d,i}) $$

$$ - (\ell_u, L_u)_{u \in \mathcal{B}_{d,i}} := (\ell[j], L_j)_{0 \le j \le |\mathcal{B}_{d,i}| - 1} $$

* If $\mathcal{L}_d$ is a XOR layer:

$$ - (\ell_{\text{out}}, L_{\text{out}}) := \text{BatchXOR}^{\text{H}}(\text{mpk}, (\ell_l, L_l), (\ell_r, L_r), \text{salt}_{d,i,2}, S_{d,i}) $$

$$ - (\ell[j], L_j)_{0 \le i \le t-1} := \text{UnpackXOR}^{\text{H}}(\text{mpk}, \ell_{\text{out}}, L_{\text{out}}, \text{salt}_{d,i,3}, \text{shift}_{\text{out},d,i}) $$

$$ - (\ell_u, L_u)_{u \in \mathcal{B}_{d,i}} := (\ell[j], L_j)_{0 \le i \le |\mathcal{B}_{d,i}| - 1} $$

* Label each $u \in \mathcal{B}_{d,i}$ with $(\ell_u, L_u)$.

**Output.** Return $\hat{y} := (\ell_o)_{o \in O(C)}$.

Algorithm 3: Evaluator algorithm of the Boolean garbling scheme

**Algorithm GC.Dec(d, $\hat{y}$)**

**Input.** Decoding information d and garbled output $\hat{y}$. Parse $d := (k_o)_{o \in O(C)}$ and $\hat{y} := (\ell_o)_{o \in O(C)}$.

**Output.** Return $y := (\ell_o \oplus k_o)_{o \in O(C)}$.
Algorithm 4: Decoding procedure of the Boolean garbling scheme

**Padding.** For convenience, given values $(v_u)_{u \in \mathcal{B}}$ either in $\mathbb{F}_2^{|\mathcal{B}|}$ or in $\mathbb{Z}_{p-1}^{|\mathcal{B}|}$ where $\mathcal{B}$ is a subset of indices of size at most $t$, we write $(v[0], \dots, v[t-1]) := \text{pad}_t((v_u)_{u \in \mathcal{B}})$ to denote the procedure that assigns $(v_{u_0}, \dots, v_{u_{|\mathcal{B}|-1}})$ to $(v[0], \dots, v[|\mathcal{B}|-1])$, where $u_0 \cdots u_{|\mathcal{B}|-1}$ is an ordering (e.g., lexicographic) of the elements of $\mathcal{B}$, and assigns 0 to the remaining $v[i]$'s for $i = |\mathcal{B}|$ to $t-1$. That is, $\text{pad}_t$ pads a list of values with zeroes to get an element of $\mathbb{F}_2^t$ or $\mathbb{Z}_{p-1}^t$ (we slightly abuse our notations and do not distinguish between padding with $0 \in \mathbb{F}_2$ or with $0 \in \mathbb{Z}_{p-1}$).

## 6.2 Efficiency and Correctness

**Efficiency.** Let $\hat{C} := \text{GC.Garble}(1^{\lambda}, C)$. We have

$$|\hat{C}| = |C| + |\text{mpk}| + \sum_{d=1}^{D} |\hat{\mathcal{L}}_d|.$$

The size of $|\text{mpk}|$ is $2N^m + 1$ elements of $\mathbb{G}$, which translates to $O(\lambda \cdot (2cm2^m)^m)$ bits. Using $m = O(\sqrt{\log \lambda})$ yields $|\text{mpk}| = \text{poly}(\lambda)$, where $\text{poly}$ is a fixed polynomial independent of $C$. The size of each garbled layer $\hat{\mathcal{L}}_d$ is $O(\lambda \cdot n_d)$, as it contains $n_d$ constant-length tuples of shifts (4 for a batch of XORs, 9 for a batch of ANDs), where each shift is $O(\lambda)$-bit long. This yields

$$|\hat{C}| = |C| + O(\lambda) \cdot \sum_{d=1}^{D} \lceil |\mathcal{L}_d|/t \rceil + \text{poly}(\lambda).$$

For circuits that are not too narrow (where the layers contain more than $\sqrt{\log \lambda}$ gates), this translates to $O(\lambda/\sqrt{\log(\lambda)}) \cdot |C| + \text{poly}(\lambda)$ bits. In the worst-case, for extremely narrow circuits, $|\hat{C}|$ can grow to $O(\lambda/\sqrt{\log(\lambda)}) \cdot |C| + O(\lambda \cdot D) + \text{poly}(\lambda)$ bits.

**Correctness.** Let $x$ denote an input to $C$. For each gate $u$, let $x_u$ denote the bit output by this gate in the computation of $C(x)$. Given a batch $\mathcal{B}$ of gates, let $x_{\mathcal{B}} := (x_u)_{u \in \mathcal{B}}$. The proof of correctness relies on the fact that all the procedures maintain a suitable invariant throughout the computation. The required invariant for each procedure is guaranteed by a correctness lemma:

* Lemma 16 for Pack$^H$

* Lemma 17 for Unpack$^H$

* Lemma 19 for BatchAND$^H$

* Lemma 18 for BatchXOR$^H$

At the start of the procedure, for each input gate $i$, we have $k_i \oplus \ell_i = x_i$ and $L_i - K_i = \Delta \cdot \ell_i \bmod p - 1$ by definition of GC.Enc. Then, fix a layer $d$ and a batch $i \le n_d$ and assume that before running the procedures on $\mathcal{L}_d$, it holds that $x_u = k_u \oplus \ell_u$ and $L_u - K_u = \Delta \cdot \ell_u \bmod p - 1$ for all $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$. Then,

* By Lemma 16, it holds after running the Pack$^H$ procedures that $k_l + \ell_l = \Phi(\text{pad}_t(x_{\text{Left}_{d,i}}))$, $k_r + \ell_r = \Phi(\text{pad}_t(x_{\text{Right}_{d,i}}))$, $L_l - K_l = \Delta \cdot \ell_l(N) \bmod p - 1$, and $L_r - K_r = \Delta \cdot \ell_r(N) \bmod p - 1$. Let $x_l := \Phi(\text{pad}_t(x_{\text{Left}_{d,i}}))$ and $x_r := \Phi(\text{pad}_t(x_{\text{Right}_{d,i}}))$.
• If $\mathcal{L}_d$ is an AND layer, by Lemma 19, it holds after running the BatchAND$^H$ procedure that $k_{\text{out}} + \ell_{\text{out}} = x_l \cdot x_r$ and $K_{\text{out}} - L_{\text{out}} = \Delta \cdot \ell_{\text{out}}(N) \bmod p - 1$.

• If $\mathcal{L}_d$ is an AND layer, by Lemma 17, it holds after running the Unpack$^H$ procedure that $(k[i] \oplus \ell[i])_{i \le t-1} = \Psi(x_l \oplus x_r)$ and $K[i] - L[i] = \Delta \cdot \ell[i] \bmod p - 1$ for $i = 0$ to $t-1$.

• By an identical reasoning, if $\mathcal{L}_d$ is a XOR layer, by Lemma 18 and Lemma 17, it holds after running the BatchXOR$^H$ and Unpack$^H$ procedures that $(k[i] \oplus \ell[i])_{i \le t-1} = \Phi^{-1}(x_l \oplus x_r)$ and $K[i] - L[i] = \Delta \cdot \ell[i] \bmod p - 1$ for $i = 0$ to $t-1$.

It follows that after each AND layer, the gates in $\mathcal{B}_{d,i}$ are labeled with the first $|\mathcal{B}_{d,i}|$ entries of $\Psi(\Phi(\text{pad}_t(x_{\text{Left}_{d,i}})))$. By definition of the RMFE maps (Definition 5), this value equal to $\text{pad}_t(x_{\text{Left}_{d,i}}) \odot \text{pad}_t(x_{\text{Right}_{d,i}})$, hence its first $|\mathcal{B}_{d,i}|$ entries are exactly the products $x_{u_l} \cdot x_{u_r}$, where $u_l, u_r$ denote the left and right parents of each gate $u \in \mathcal{B}_{d,i}$ respectively. Similarly, after each XOR layer, each gate $u$ of the layer gets labeled with $x_{u_l} \oplus x_{u_r}$. Eventually, after all layers have been computed, it holds that $k_o \oplus \ell_o = x_o$ for each output gate $o$, and we have $(x_o)_{o \in O(C)} = y = C(x)$.

## 6.3 Packing Procedures

Given $x \in \mathbb{N}$, let us write $|x| := [\log_2(x)]$. Let toBits: $\mathbb{N} \to \mathbb{F}_2^*$ denote the function that, on input an integer $x \in \mathbb{N}$, output the bit decomposition $x[1], \dots, x[|x|]$ of $x$, viewed as an element of $\mathbb{F}_2^{|x|}$.

**Algorithm Pack$^H_G(\text{msk}, (k_u, K_u)_{u \in \mathcal{B}}$, salt)**

**Input.** Master secret key msk. Wire keys $(k_u, K_u)_{u \in \mathcal{B}} \in (\{0, 1\} \times \mathbb{Z}_{p-1})^{|\mathcal{B}|}$ for a batch of gates $\mathcal{B}$ of size $|\mathcal{B}| \le t$. Salt salt. Parse msk as (mpk, $\Delta$, $h_0$).

**Procedure.**

• $k_{\text{out}} := \Phi(\text{pad}_t((k_u)_{i \in \mathcal{B}}))$

• $(K[0], \dots, K[t-1]) := \text{pad}_t((K_u)_{i \in \mathcal{B}})$

• $K \leftarrow \sum_{i=0}^{t-1} K[i] \cdot 2^i \bmod p - 1 \quad \triangleright K = \langle \Delta \cdot \sum_{i=0}^{t-1} \ell[i] \cdot 2^i \rangle_G$

• (shift, $K_{\text{out}}) := [2^t]$-BatchfAuth$^H_G(\text{msk}, \Delta, K, \text{Eval}_N \circ \Phi \circ \text{toBits}, \text{salt})$

**Output.** ($k_{\text{out}}$, $K_{\text{out}}$, shift)

Algorithm 5: Garbler packing procedure. Given ordered indices $(u_0, \dots, u_{|\mathcal{B}|-1})$, it packs multiples of $(k_{u_i}, \ell_{u_i})$ of bits $x_i \in \mathbb{F}_2$, and $\mathbb{Z}_{p-1}$-shares $(K_{u_i}, L_{u_i})_i$ of $\Delta \cdot \ell_{u_i}$, into $\mathbb{F}_{2^m}$-shares of $\Phi((x_0, \dots, x_{|\mathcal{B}|-1})$ and $\mathbb{Z}_{p-1}$-shares of $\Delta \cdot \text{Eval}_N(\Phi(\ell_{u_0}, \dots, \ell_{u_{|\mathcal{B}|-1}}))$.

**Algorithm Pack$^H_E(\text{mpk}, (\ell_u, L_u)_{u \in \mathcal{B}}$, salt, shift)**

**Input.** Wire labels $(\ell_u, L_u)_{u \in \mathcal{B}} \in (\{0, 1\} \times \mathbb{Z}_{p-1})^{|\mathcal{B}|}$ for a batch of gates $\mathcal{B}$ of size $|\mathcal{B}| \le t$, garbling material shift.

**Procedure.**
• $\ell_{out} := \Phi(\ell[0], \dots, \ell[t-1]) = \Phi(\text{pad}_t((\ell_u)_{i \in \mathcal{B}}))$

• $(L[0], \dots, L[t-1]) := \text{pad}_t((L_u)_{i \in \mathcal{B}})$

• $\tilde{\ell}_{out} := \sum_{i=0}^{t-1} \ell[i] \cdot 2^i$

• $L \leftarrow \sum_{i=0}^{t-1} L[i] \cdot 2^i \mod p - 1 \quad \triangleright L = \langle \Delta \cdot \tilde{\ell}_{out} \rangle_E$

• $L_{out} := [2^t]_{\text{BatchfAuth}_E(\text{mpk}, \tilde{\ell}_{out}, L, \text{Eval}_N \circ \Phi \circ \text{toBits}, \text{salt}, \text{shift})}$

**Output.** ($\ell_{out}, L_{out}$)

**Algorithm 6:** Evaluator packing procedure. Given ordered indices $(u_0, \dots, u_{|\mathcal{B}|-1})$, it packs multiples shares $(k_{u_i}, \ell_{u_i})$ of bits $x_i \in \mathbb{F}_2$, and $\mathbb{Z}_{p-1}$-shares $(K_{u_i}, L_{u_i})_i$ of $\Delta \cdot \ell_{u_i}$, into $\mathbb{F}_{2^m}$-shares of $\Phi((x_0, \dots, x_{|\mathcal{B}|-1})$ and $\mathbb{Z}_{p-1}$-shares of $\Delta \cdot \text{Eval}_N(\Phi(\ell_{u_0}, \dots, \ell_{u_{|\mathcal{B}|-1}}))$.

**Lemma 16** (Correctness of packing). Fix (mpk, msk, $(\ell_u, L_u, k_u, K_u)_{u \in \mathcal{B}}$, salt) where msk := (mpk, $\Delta$, $h_0$). Assume that for each $u \in \mathcal{B}$, it holds that $L_u - K_u = \Delta \cdot \ell_u \mod p - 1$. Then, denoting

$$ \begin{align*} (x_u)_{u \in \mathcal{B}} &:= (k_u \oplus \ell_u)_{u \in \mathcal{B}} \\ (k_{\text{out}}, K_{\text{out}}, \text{shift}) &:= \text{Pack}_{\text{G}}^{\text{H}}(\text{msk}, (k_u, K_u)_{u \in \mathcal{B}}, \text{salt}) \\ (\ell_{\text{out}}, L_{\text{out}}) &:= \text{Pack}_{\text{E}}^{\text{H}}(\text{mpk}, (\ell_u, L_u)_{u \in \mathcal{B}}, \text{salt}, \text{shift}), \end{align*} $$

it holds that

$$ \begin{align*} k_{\text{out}} + \ell_{\text{out}} &= \Phi(\text{pad}_t((x_u)_{u \in \mathcal{B}})) \\ L_{\text{out}} - K_{\text{out}} &= \Delta \cdot \text{Eval}_N(\ell_{\text{out}}) \mod p - 1. \end{align*} $$

*Proof.* The first part of Lemma 16 follows immediately from the linearity of $\Phi \circ \text{pad}_t$. As for the second part, we have

$$ \begin{align*} L - K &= \sum_{i=0}^{t-1} (L[i] - K[i]) \cdot 2^i \mod p - 1 \\ &= \Delta \cdot \sum_{i=0}^{t-1} \ell[i] \cdot 2^i = \Delta \cdot \tilde{\ell}_{\text{out}} \mod p - 1 \quad \triangleright \text{by assumption of Lemma 16} \end{align*} $$

Hence, the conditions of Lemma 13 are satisfied. Applying Lemma 13, we get

$$ L_{\text{out}} - K_{\text{out}} = \Delta \cdot \text{Eval}_N(\Phi(\text{toBits}(\tilde{\ell}_{\text{out}}))) \mod p - 1, $$

and we conclude by observing that $\text{pad}_t((\ell_u)_{u \in \mathcal{B}}) = \text{toBits}(\tilde{\ell}_{\text{out}})$ by construction, hence $\ell_{\text{out}} = \Phi(\text{toBits}(\tilde{\ell}_{\text{out}}))$.

<figure><img src="image_3.png" /></figure>

## 6.4 Unpacking Procedures

We also introduce unpacking procedures for the garbler and the evaluator. We let $\text{Bit}_i$ denote the function that, given a value $v \in \mathbb{F}_2^t$, outputs the $i$-th co-efficient $v[i]$ of $v$. Given an operation $\star \in \{+, \cdot\}$ (bitwise-XOR or bitwise-AND), the procedures convert shares $(k, \ell)$ of $\Phi(x) \star \Phi(y) \in \mathbb{F}_{2^m}$ and $\Delta \cdot \ell(n)$ back to bitwise shares of $f(\Phi(x) \star \Phi(y)) \in \mathbb{F}_2^t$ and of $(\Delta \cdot f(\ell)[i])_{i \le t}$ (that is, $\Delta$-authenticated subtractive shares of each bit of $\Phi^{-1}(\ell)$ over $\mathbb{Z}_{p-1}$). Depending on the operation $\star$, we use a different “inverse mapping” $f$:
* If $\otimes = +$ (when unpacking the output of a batch-XOR), we set $f = \Phi^{-1}$, since $\Phi^{-1}(\Phi(x)+\Phi(y)) = x \oplus y$ (by linearity of $\Phi$).

* If $\otimes = \cdot$ (when unpacking the output of a batch-AND), we set $f = \Psi$, since $\Psi(\Phi(x) \cdot \Phi(y)) = x \odot y$ (by definition of RMFEs).

We define the general procedures below.

**Algorithm Unpack<sub>G</sub><sup>H</sup>(f, msk, k, K, salt)**

**Input.** Function $f \in \{\Phi^{-1}, \Psi\}$. Master secret key msk, packed keys $(k, K) \in \mathbb{F}_{2^m} \times \mathbb{Z}_{p-1}$, salt salt. Parse msk := (mpk, $\Delta$, $h_0$).

**Procedure.**

* $(k[0], \dots, k[t-1]) := f(k)$

* (shift, $K_0, \dots, K_{t-1}$) := BatchfAuth<sub>G</sub><sup>H</sup>(msk, $\Delta$, K, (Bit<sub>i</sub> $\circ f \circ \text{toPoly}_N$)<sub>0\le i \le t-1</sub>)

**Output.** $((k[i], K_i)_{i \le t-1}, \text{shift})$

**Algorithm 7:** Garbler procedure for unpacking the result of a batch evaluation. The procedure toPoly<sub>N</sub> returns an element of $\mathbb{N}[X]$, but in our context, toPoly<sub>N</sub> will always take as input an integer embedding of a polynomial in $\mathbb{F}_2[X]/P(X)$, hence its output is guaranteed to be a polynomial in $\mathbb{F}_2[X; m]$ with coefficients in $\{0, 1\}$. We interpret this polynomial as an element of $\mathbb{F}_{2^m}$ when evaluating $f$.

**Algorithm Unpack<sub>E</sub><sup>H</sup>(f, mpk, $\ell$, L, salt, shift)**

**Input.** Function $f \in \{\Phi^{-1}, \Psi\}$. Master public key mpk, packed labels ($\ell, L) \in \mathbb{F}_{2^m} \times \mathbb{Z}_{p-1}$, salt salt, garbling material shift.

**Procedure.**

* $(\ell[0], \dots, \ell[t-1]) := f(\ell)$

* $(L_0, \dots, L_{t-1}) := \text{BatchfAuth}_E^H(\text{mpk}, \ell(N), L, (\text{Bit}_i \circ f \circ \text{toPoly}_N)_{0 \le i \le t-1})$

**Output.** $(\ell[i], L_i)_{i \le t-1}$

**Lemma 17 (Correctness of unpacking).** Fix $f \in \{\Phi^{-1}, \Psi\}$ and (mpk, msk, $(k, K, \ell, L)$, salt) where msk := (mpk, $\Delta$, $h_0$). Assume that $L - K = \Delta \cdot \text{Eval}_N(\ell) \mod p - 1$. Then, denoting

$$x := k + \ell \quad \triangleright \text{ over } \mathbb{F}_{2^m}$$

$$((k[i], K[i])_{i \le t-1}, \text{shift}) := \text{Unpack}_{\text{G}}^{\text{H}}(f, \text{msk}, k, K, \text{salt})$$

$$(\ell[i], L[i])_{i \le t-1} := \text{Unpack}_{\text{E}}^{\text{H}}(f, \text{mpk}, \ell, L, \text{salt}, \text{shift}),$$
it holds that

$$ (k[i] \oplus l[i])_{i \le t-1} = f(x) \\ (K[i] - L[i])_{i \le t-1} = (\Delta \cdot l[i] \bmod p - 1)_{i \le t-1} $$

*Proof.* The first part of Lemma 17 follows immediately from the linearity of $f: \mathbb{F}_{2^m} \to \mathbb{F}_2^l$. As for the second part, since we have $L - K = \Delta \cdot \mathrm{Eval}_N(l) \bmod p - 1$ by assumption, the conditions of Lemma 13 are satisfied. Applying Lemma 13 with $q = t$, we get for $i = 0$ to $t-1$:

$$ L[i] - K[i] = \Delta \cdot \mathrm{Bit}_i(f(\mathrm{toPoly}_N(\mathrm{Eval}_N(l)))) \bmod p - 1 \\ = \Delta \cdot \mathrm{Bit}_i(f(l)) = \Delta \cdot l[i] \bmod p - 1 $$

<figure><img src="image_4.png" /></figure>

Eventually, we define UnpackXOR<sup>H</sup> and UnpackAND<sup>H</sup> as the above general procedures with $f$ set to either $\Phi^{-1}$ or $\Psi$ and hardcoded in the function:

* UnpackXOR<sup>H</sup><sub>G</sub>(msk, $k$, $K$, salt) := Unpack<sup>H</sup><sub>G</sub>(Φ<sup>-1</sup>, msk, $k$, $K$, salt)

* UnpackXOR<sup>H</sup><sub>E</sub>(mpk, $\ell$, $L$, salt, shift) := Unpack<sup>H</sup><sub>E</sub>(Φ<sup>-1</sup>, mpk, $\ell$, $L$, salt, shift)

* UnpackAND<sup>H</sup><sub>G</sub>(msk, $k$, $K$, salt) := Unpack<sup>H</sup><sub>G</sub>(Ψ, msk, $k$, $K$, salt)

* UnpackAND<sup>H</sup><sub>E</sub>(mpk, $\ell$, $L$, salt, shift) := Unpack<sup>H</sup><sub>E</sub>(Ψ, mpk, $\ell$, $L$, salt, shift)

## 6.5 Batch-XOR Gadget

The procedures below are used by the garbler and the evaluator, who hold as inputs $\mathbb{F}_{2^m}$-shares $(k_l, l_l)$ of $x_l \in \mathbb{F}_{2^m}$, $\mathbb{F}_{2^m}$-shares $(k_r, l_r)$ of $x_r \in \mathbb{F}_{2^m}$, and $\mathbb{Z}_{p-1}$-shares $(K_l, L_l)$ and $(K_r, L_r)$ of $\Delta \cdot x_l(N)$ and $\Delta \cdot x_r(N)$ respectively. The procedure outputs $\mathbb{F}_{2^m}$-shares $(k_{\mathrm{out}}, l_{\mathrm{out}})$ of $x_l + x_r$, and $\mathbb{Z}_{p-1}$-shares $(K_{\mathrm{out}}, L_{\mathrm{out}})$ of $\Delta \cdot \mathrm{Eval}_N(x_l \oplus x_r)$. Let $S_{N,m}$ denote the set of sums of two elements from $\mathbb{I}_{N,m}$.

**Algorithm BatchXOR<sup>H</sup><sub>G</sub>(msk, (k<sub>l</sub>, K<sub>l</sub>), (k<sub>r</sub>, K<sub>r</sub>), salt)**

**Input.** Master secret key msk. Packed keys $(k_l, K_l)$, $(k_r, K_r)$. Salt salt. Parse msk := (mpk, $\Delta$, $h_0$).

**Procedure.**

* $k_{\mathrm{out}} := k_l + k_r \triangleright \mathrm{Over} \mathbb{F}_{2^m}$

* $\tilde{K}_{\mathrm{out}} := K_l + K_r \bmod p - 1$

* (shift, $K_{\mathrm{out}}$) := $S_{N,m}$-BatchfAuth<sup>H</sup><sub>G</sub>(msk, $\Delta$, $\tilde{K}_{\mathrm{out}}$, Mod<sub>N</sub>(·, 2), salt)

**Output.** $((k_{\mathrm{out}}, K_{\mathrm{out}}), \mathrm{shift})$

Algorithm 9: Garbler batch-XOR gadget
**Algorithm BatchXOR<sup>H</sup><sub>E</sub>(mpk, (l<sub>l</sub>, L<sub>l</sub>), (l<sub>r</sub>, L<sub>r</sub>), salt, shift)**

**Input.** Master public key mpk. Packed keys $(k_l, K_l)$, $(k_r, K_r)$. Salt salt, garbling material shift.

**Procedure.**

• $\tilde{\ell}_{\text{out}} := \ell_l + \ell_r \triangleright \text{Over } \mathbb{Z}[X]$

• $\ell_{\text{out}} := \tilde{\ell}_{\text{out}} \bmod 2 \triangleright \ell_{\text{out}} \in \mathbb{F}_{2^m}$

• $\tilde{L}_{\text{out}} := L_l + L_r \bmod p - 1$

• $L_{\text{out}} := S_{N,m}$-BatchfAuth<sub>E</sub><sup>H</sup>(mpk, $\tilde{\ell}_{\text{out}}(N)$, $\tilde{L}_{\text{out}}$, Mod<sub>N</sub>(-, 2), salt, shift)

**Output.** $(\ell_{\text{out}}, L_{\text{out}})$

**Algorithm 10: Evaluator batch-XOR gadget**

**Lemma 18** (Correctness of batch-XOR). Fix(mpk, msk, $(k_l, K_l, \ell_l, L_l)$, $(k_r, K_r, \ell_r, L_r)$, salt) where msk := (mpk, $\Delta$, $h_0$).
Assume that for $u \in \{l, r\}$, $L_u - K_u = \Delta \cdot \text{Eval}_N(\ell_u) \bmod p - 1$. Then, denoting

$$x_u := k_u + \ell_u \text{ for } u \in \{l, r\} \triangleright \text{over } \mathbb{F}_{2^m}$$

$$((k_{\text{out}}, K_{\text{out}}), \text{shift}) := \text{BatchXOR}_{\text{G}}^{\text{H}}(\text{msk}, (k_l, K_l), (k_r, K_r), \text{salt})$$

$$(\ell_{\text{out}}, L_{\text{out}}) := \text{BatchXOR}_{\text{E}}^{\text{H}}(\text{mpk}, (\ell_l, L_l), (\ell_r, L_r), \text{salt, shift}),$$

it holds that

$$k_{\text{out}} + \ell_{\text{out}} = x_l + x_r \triangleright \text{over } \mathbb{F}_{2^m}$$

$$K_{\text{out}} - L_{\text{out}} = \Delta \cdot \text{Eval}_N(\ell_{\text{out}}) \bmod p - 1$$

*Proof.* The first part of Lemma 18 follows immediately from the fact that $\ell_{\text{out}} = \tilde{\ell}_{\text{out}} \bmod 2$ with $\tilde{\ell}_{\text{out}} = \ell_l + \ell_r$ over $\mathbb{Z}[X]$, hence $\ell_{\text{out}} = \ell_l + \ell_r$ over $\mathbb{F}_{2^m}$. As for the second part, since we have

$$\begin{align*}
\tilde{L}_{\text{out}} - \tilde{K}_{\text{out}} &= (L_l - K_l) + (L_r - K_r) \bmod p - 1 \\
&= \Delta \cdot (\text{Eval}_N(\ell_l) + \text{Eval}_N(\ell_r)) \bmod p - 1 \quad \triangleright \text{by assumption of Lemma 18} \\
&= \Delta \cdot \text{Eval}_N(\ell_l + \ell_r) \bmod p - 1 \quad \triangleright \text{sum over } \mathbb{Z}[X], \text{ since } N \gg 2 \\
&= \Delta \cdot \tilde{\ell}_{\text{out}}(N) \bmod p - 1
\end{align*}$$

hence the conditions of Lemma 13 are satisfied. Applying Lemma 13, we get:

$$\begin{align*}
L_{\text{out}} - K_{\text{out}} &= \Delta \cdot \text{Mod}_N(\tilde{\ell}_{\text{out}}(N), 2) \bmod p - 1 \\
&= \Delta \cdot \text{Eval}_N(\ell_{\text{out}}) \bmod p - 1 \quad \triangleright \text{by definition of } \text{Mod}_N(\cdot, 2).
\end{align*}$$

## 6.6 Batch-AND Gadget
**Algorithm BatchAND<sup>H</sup><sub>G</sub>(msk, (k<sub>l</sub>, K<sub>l</sub>), (k<sub>r</sub>, K<sub>r</sub>), salt)**

**Input.** Master secret key msk. Packed keys $(k_l, K_l), (k_r, K_r)$. Salt salt. Parse msk $:= (mpk, \Delta, h_0)$. For $i = 1$ to 6, let $salt_i := salt || i$.

**Procedure.**

• $(k'_l, k'_r) \leftarrow \$ \text{Pert}_c(k_l) \times \text{Pert}_c(k_r)$

• (shift<sub>a</sub>, ă<sub>G</sub>) $:= \mathbb{Z}-\text{VtO}_{\text{G}}^{\text{H}_0}$(msk, $k'_l(N)$, K<sub>r</sub>, salt<sub>1</sub>)
▷ ă<sub>G</sub> = $\langle k'_l(N) \ell_r(N) \rangle_{\text{G}}$

• (shift<sub>b</sub>, b̃<sub>G</sub>) $:= \mathbb{Z}-\text{VtO}_{\text{G}}^{\text{H}_0}$(msk, $k'_r(N)$, K<sub>l</sub>, salt<sub>2</sub>)
▷ b̃<sub>G</sub> = $\langle k'_r(N) \ell_l(N) \rangle_{\text{G}}$

• $a_G := [\text{toPoly}_N(\tilde{a}_G) \text{ mod } 2, P]$ ▷ $a_G \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $b_G := [\text{toPoly}_N(\tilde{b}_G) \text{ mod } 2, P]$ ▷ $b_G \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $k_{\text{out}} := k_l k_r + a_G + b_G$ ▷ over $\mathbb{F}_{2^m}$

• (shift<sub>α</sub>, α<sub>G</sub>) $:= \text{VtO}_{\text{G}}^{\text{H}}$(msk, $\Delta k'_l(N)$, K<sub>r</sub>, salt<sub>3</sub>)
▷ α<sub>G</sub> = $\langle \Delta k'_l(N) \cdot \ell_r(N) \rangle_{\text{G}}$

• (shift<sub>β</sub>, β<sub>G</sub>) $:= \text{VtO}_{\text{G}}^{\text{H}}$(msk, $\Delta k'_r(N)$, K<sub>l</sub>, salt<sub>4</sub>)
▷ β<sub>G</sub> = $\langle \Delta k'_r(N) \cdot \ell_l(N) \rangle_{\text{G}}$

• (shift<sub>γ</sub>, γ<sub>G</sub>) $:= \text{VtO}_{\text{G}}^{\text{H}}$(msk, K<sub>l</sub>, K<sub>r</sub>, salt<sub>5</sub>) ▷ γ<sub>G</sub> = $\langle K_l \cdot \ell_r(N) \rangle_{\text{G}}$

• $\tilde{K}_{\text{out}} := \alpha_G + \beta_G - \gamma_G + \Delta(\tilde{a}_G + \tilde{b}_G)$ ▷ $\tilde{K}_{\text{out}} = \langle \Delta \tilde{\ell}_{\text{out}} \rangle_{\text{G}}$

• (shift<sub>K</sub>, K<sub>out</sub>) $:= [N^m]$-BatchfAuth<sup>H</sup><sub>G</sub>(msk, Δ, K̃<sub>out</sub>, Mod<sub>N</sub>(·, 2, P), salt<sub>6</sub>) ▷ K<sub>out</sub> = $\langle \Delta \ell_{\text{out}} \rangle_{\text{G}}$

• $S_{\text{out}} := (\text{shift}_a, \text{shift}_b, \text{shift}_\alpha, \text{shift}_\beta, \text{shift}_\gamma, \text{shift}_K)$

**Output.** ($(k_{\text{out}}, K_{\text{out}}), S_{\text{out}}$)

Algorithm 11: Garbler batch-AND gadget. Unlike the other gadgets, BatchAND<sup>H</sup><sub>G</sub> is a randomized procedure.

**Algorithm BatchAND<sup>H</sup><sub>E</sub>(msk, (l<sub>l</sub>, L<sub>l</sub>), (l<sub>r</sub>, L<sub>r</sub>), salt, S)**

**Inputs.** Master public key mpk. Packed labels $(l_l, L_l), (l_r, L_r)$, salt salt and garbling material S. Parse S $:= (\text{shift}_a, \text{shift}_b, \text{shift}_\alpha, \text{shift}_\beta, \text{shift}_\gamma, \text{shift}_K)$. For $i = 1$ to 6, let $salt_i := salt || i$.

**Procedure.**

• ă<sub>E</sub> $:= \mathbb{Z}-\text{VtO}_{\text{E}}^{\text{H}_0}$(mpk, $\ell_r(N)$, L<sub>r</sub>, salt<sub>1</sub>, shift<sub>a</sub>)
▷ ă<sub>E</sub> = $\langle k'_l(N) \ell_r(N) \rangle_{\text{E}}$

• b̃<sub>E</sub> $:= \mathbb{Z}-\text{VtO}_{\text{E}}^{\text{H}_0}$(mpk, $\ell_l(N)$, L<sub>l</sub>, salt<sub>2</sub>, shift<sub>b</sub>) ▷ b̃<sub>E</sub> = $\langle k'_r(N) \ell_l(N) \rangle_{\text{E}}$

• $\tilde{\ell}_{\text{out}} := \ell_l(N) \ell_r(N) + \tilde{a}_E + \tilde{b}_E$

• $a_E := [\text{toPoly}_N(\tilde{a}_E) \text{ mod } 2, P]$ ▷ $a_E \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$
• $b_E := [\text{toPoly}_N(\tilde{b}_E) \mod 2, P] \triangleright b_E \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $\ell_{\text{out}} := \ell_1\ell_r + a_E + b_E \triangleright \ell_{\text{out}} = \text{Mod}_N(\ell_{\text{out}}) \in \mathbb{F}_{2^m}$

• $\alpha_E := \text{VtO}_E^H(\text{mpk}, \ell_r(N), L_r, \text{salt}_3, \text{shift}_\alpha)$
$\triangleright \alpha_E = \langle \Delta k'_1(N) \cdot \ell_r(N) \rangle_E$

• $\beta_E := \text{VtO}_E^H(\text{mpk}, \ell_1(N), L_\ell, \text{salt}_4, \text{shift}_\beta)$
$\triangleright \beta_E = \langle \Delta k'_1(N) \cdot \ell_1(N) \rangle_E$

• $\gamma_E := \text{VtO}_E^H(\text{mpk}, \ell_r(N), L_r, \text{salt}_5, \text{shift}_\gamma) \triangleright \gamma_E = \langle K_1 \cdot \ell_r(N) \rangle_E$

• $\tilde{L}_{\text{out}} := \alpha_E + \beta_E - \gamma_E + L_1\ell_r(N) \triangleright \tilde{L}_{\text{out}} = \langle \Delta \tilde{\ell}_{\text{out}} \rangle_E$

• $L_{\text{out}} := [N^m]$-BatchfAuth$_E^H(\text{mpk}, \tilde{\ell}_{\text{out}}, \tilde{L}_{\text{out}}, \text{Mod}_N(\cdot, 2, P), \text{salt}_6, \text{shift}_K) \triangleright L_{\text{out}} = \langle \Delta \ell_{\text{out}} \rangle_E$

**Output.** ($\ell_{\text{out}}, L_{\text{out}}$)

<caption>Algorithm 12: Evaluator batch-AND gadget</caption>

**Lemma 19 (Correctness of batch-AND).** *Fix* (mpk, msk, ($k_1, K_1, \ell_1, L_1$), ($k_r, K_r, \ell_r, L_r$), salt) *where* msk := (mpk, $\Delta, h_0$).
*Assume that for* $u \in \{l, r\}, L_u - K_u = \Delta \cdot \text{Eval}_N(\ell_u) \mod p - 1$. *Then, denoting*

$$
\begin{align*}
x_u &:= k_u + \ell_u \quad \text{for } u \in \{l, r\} \quad \triangleright \text{ over } \mathbb{F}_{2^m} \\
((k_{\text{out}}, K_{\text{out}}), S) &:= \text{BatchAND}_{\text{G}}^{\text{H}}(\text{msk}, (k_l, K_l), (k_r, K_r), \text{salt}) \\
(\ell_{\text{out}}, L_{\text{out}}) &:= \text{BatchAND}_{\text{E}}^{\text{H}}(\text{mpk}, (\ell_l, L_l), (\ell_r, L_r), \text{salt}, S),
\end{align*}
$$

it holds that

$$
\begin{align*}
k_{\text{out}} + \ell_{\text{out}} &= x_l \cdot x_r \quad \triangleright \text{ over } \mathbb{F}_{2^m} \\
K_{\text{out}} - L_{\text{out}} &= \Delta \cdot \text{Eval}_N(\ell_{\text{out}}) \mod p - 1
\end{align*}
$$

*Proof.* Using the assumptions of Lemma 19, the conditions of Lemma 11 are satisfied. Hence, we have
by Lemma 11 that

$$
\begin{align*}
\tilde{a}_E - \tilde{a}_G &= \ell_r(N) \cdot k'_1(N) \\
\tilde{b}_E - \tilde{b}_G &= \ell_1(N) \cdot k'_r(N).
\end{align*}
$$

Then since $N > c \cdot m$, using Lemma 8 with $T = 1$, we get

$$
\begin{align*}
\ell_r \cdot k_l &:= \text{toPoly}_N(\text{Mod}_N(\ell_r(N) \cdot k'_1(N), 2)) \\
\ell_l \cdot k_r &:= \text{toPoly}_N(\text{Mod}_N(\ell_l(N) \cdot k'_r(N), 2)),
\end{align*}
$$

where the products on the left are computed over $\mathbb{F}_2[X]$. Furthermore, by definition of $\text{VtO}_G$, we have

$$
\begin{align*}
\tilde{a}_G &= \sum_{x \in I_{N,m}} x \cdot \mathbf{F}^{H_0}(k, x, \text{salt}_1) \\
\tilde{b}_G &= \sum_{x \in I_{N,m}} x \cdot \mathbf{F}^{H_0}(k, x, \text{salt}_2),
\end{align*}
$$
where each term $F^{H_0}(k, x, \text{salt}_i)$ is a term of the form map $(H(h_x^{sk}, \text{salt}_i))$. By definition of map, each such term is of the form $r(N)$ where $r \in \mathbb{Z}[X; m]$ is a polynomial with coefficients bounded by $\|r\|_{\infty} \le c$. Then, applying Lemma 8 using $T = |I_{N,m}|+1 = 2^m+1$ (which is possible because $N = 2c \cdot m \cdot (2^m+1)+1 > c \cdot m \cdot T$), we get

$$ \text{toPoly}_N(\tilde{a}_E) = \text{toPoly}_N(\ell_r(N) \cdot k'_l(N) + \tilde{a}_G) = \ell_r \cdot k'_l + \text{toPoly}_N(\tilde{a}_G) $$

$$ \text{toPoly}_N(\tilde{b}_E) = \text{toPoly}_N(\ell_l(N) \cdot k'_r(N) + \tilde{b}_G) = \ell_l \cdot k'_r + \text{toPoly}_N(\tilde{b}_G), $$

and since the map $[\cdot, 2, P]$ is linear, we obtain

$$ a_E = \ell_r \cdot k_l + a_G \quad \triangleright \text{ over } \mathbb{F}_{2^m} = \mathbb{F}_2[X]/P(X) $$

$$ b_E = \ell_l \cdot k_r + b_G \quad \triangleright \text{ over } \mathbb{F}_{2^m} = \mathbb{F}_2[X]/P(X), $$

and therefore (note that $+$ and $-$ coincide over $\mathbb{F}_{2^m}$)

$$ \begin{aligned} \ell_{\text{out}} + k_{\text{out}} &= (k_r k_l + a_G + b_G) + (k_l k_r + a_E + b_E) \\ &= k_r k_l + k_r \ell_l + k_l \ell_r + \ell_r \ell_l \\ &= (k_r + \ell_r) \cdot (k_l + \ell_l) = x_l \cdot x_r. \quad \triangleright \text{ over } \mathbb{F}_{2^m} = \mathbb{F}_2[X]/P(X) \end{aligned} $$

Moving on to the last part of Lemma 19, we start by observing that

$$ \begin{aligned} \ell_{\text{out}} &= \ell_l \ell_r + a_E + b_E \\ &= [\text{toPoly}_N(\ell_r(N) \cdot k'_l(N)) + \text{toPoly}_N(\tilde{a}_E) + \text{toPoly}_N(\tilde{b}_E) \mod 2, P] \\ &= [\text{toPoly}_N(\tilde{\ell}_{\text{out}}) \mod 2, P], \end{aligned} $$

where the second equality is by linearity of the map $[\cdot, 2, P]$, and the last is by applying Lemma 8 with $T = 2^{m+1} + 1$, using this time the fact that $N = 2c \cdot m \cdot (2^m + 1) + 1 > c \cdot m \cdot T$. We therefore have $\ell_{\text{out}}(N) = \text{Mod}_N(\tilde{\ell}_{\text{out}}, 2, P)$.

Then, using the assumptions of Lemma 19, the conditions of Lemma 11 are satisfied. Hence, we have by Lemma 11 that

$$ \alpha_E - \alpha_G = \ell_r(N) \cdot (\Delta k'_l(N)) $$

$$ \beta_E - \beta_G = \ell_l(N) \cdot (\Delta k'_r(N)) $$

$$ \gamma_E - \gamma_G = \ell_r(N) \cdot K_l. $$

Then,

$$ \begin{aligned} \tilde{L}_{\text{out}} - \tilde{K}_{\text{out}} &= \alpha_E + \beta_E - \gamma_E + L_l \ell_r(N) - (\alpha_G + \beta_G - \gamma_G + \Delta(\tilde{a}_G + \tilde{b}_G)) \\ &= (\alpha_E - \alpha_G) + (\beta_E - \beta_G) - (\gamma_E - \gamma_G) + \Delta(\tilde{a}_G + \tilde{b}_G) + L_l \ell_r(N) \\ &= \Delta \cdot (\ell_r(N) \cdot k'_l(N) + \ell_l(N) \cdot k'_r(N)) - \ell_r(N) \cdot K_l \\ &\quad + \Delta(\tilde{a}_E - \ell_r(N) \cdot k'_l(N) + \tilde{b}_E - \ell_l(N) \cdot k'_r(N)) + L_l \ell_r(N) \\ &= \Delta \cdot (\tilde{a}_E + \tilde{b}_E) + \ell_r(N) \cdot (L_l - K_l) \\ &= \Delta \cdot (\tilde{a}_E + \tilde{b}_E + \ell_r(N) \cdot \ell_l(N)) \quad \triangleright L_l - K_l = \Delta \cdot \ell_l(N) \\ &= \Delta \cdot \tilde{\ell}_{\text{out}}, \end{aligned} $$
and the conditions of Lemma 13 are satisfied. Applying Lemma 13, we get:

$$L_{\text{out}} - K_{\text{out}} = \Delta \cdot \text{Mod}_N(\ell_{\text{out}}, 2, P) \mod p - 1 \\ = \Delta \cdot \ell_{\text{out}}(N) \mod p - 1,$$

which concludes the proof.

<figure><img src="image_5.png" /></figure>

# 7 Security Analysis

In this section, we prove the following theorem:

**Theorem 20.** The garbling scheme of Section 6 is private.

Fix a security parameter $\lambda$, a circuit $C$, and an input $x$. We prove privacy through a sequence of games. The initial game samples $(\hat{C}, e, d) \leftarrow_S \text{GC.Garble}(1^{\lambda}, C)$, $\hat{x} \leftarrow_S \text{GC.Enc}(e, x_{\lambda})$, and outputs $(\hat{C}, \hat{x}, d)$.

## 7.1 The Hybrids

**Hybrid**_1. In the first hybrid, we describe a simulator $\text{SimGC}_1(1^{\lambda}, C, x)$. The simulator is obtained by making a few simple changes to GC.Garble:

* During the initialization phase of GC.Garble(1^λ, C), instead of sampling $(k_i, K_i) \leftarrow_S \{0, 1\} \times \mathbb{Z}_{p-1}$ for each input wire $i \le n$, $\text{SimGC}_1$ samples labels $(\ell_i, L_i) \leftarrow_S \{0, 1\} \times \mathbb{Z}_{p-1}$ for $i = 1$ to $n$ and sets $(k, K_i) := (\ell_i \oplus x_i, L_i - \Delta \cdot \ell_i \mod p - 1)$. This is the *only place* where $\text{SimGC}_1$ uses the input $x$. Observe that $(k_i, K_i)_{i \le n}$ is distributed exactly as in the initial game, and furthermore GC.Enc($e, x$) = $(\ell_i, L_i)_{i \le n}$.

* $\text{SimGC}_1$ runs the rest of the simulation identically to GC.Garble to compute $(\hat{C}, d)$, and sets $\hat{x} := (\ell_i, L_i)_{i \le n}$. It outputs $(\hat{C}, \hat{x}, d)$.

The change between Hybrid_1 and the initial game is purely cosmetic, and the games are distributed identically.

**Hybrid**_2. In this game, we replace $\text{SimGC}_1(1^{\lambda}, C, x)$ with $\text{SimGC}_2(1^{\lambda}, C, x)$. At a high level, $\text{SimGC}_2$ computes $(\hat{C}, \hat{x}, d)$ without using msk anymore. Instead, $\text{SimGC}_2$ receives mpk from the challenger for the security game of the TCCR hash for exponential correlations with $2N^m - 1$ auxiliary powers over $\mathbb{G}$ (Definition 7). Whenever msk is required in a procedure to compute a value, $\text{SimGC}_2$ computes the same value using instead a call to the oracle $O := O_{H,\Delta,h_0}$ defined in Definition 7. While the full description of the game hop is involved (as it requires adapting all the subprocedures of GC.Garble), the change is purely syntactical: when executed with the same random tape $R$, $\text{SimGC}_1(1^{\lambda}, C, x)$ and $\text{SimGC}_2(1^{\lambda}, C, x)$ compute exactly the same functionality and produce the same output:

**Lemma 21.** For every Boolean circuit $C$ and input $x \in \{0, 1\}^n$, for every random tape $R$, it holds that

$$\text{SimGC}_1(1^{\lambda}, C, x; R) = \text{SimGC}_2(1^{\lambda}, C, x; R).$$

We defer the full description of $\text{SimGC}_2$ and the proof of Lemma 21 to Section 7.2.

**Hybrid**_3. In this game, the oracle $O$ is replaced with a random oracle $\mathcal{R}: \mathbb{Z}_{p-1} \times \{0, 1\}^* \times \mathbb{Z}_{p-1} \to \mathbb{Z}_{p-1}$. We denote $\text{SimGC}_3$ the resulting algorithm. We have the following immediate lemma:
mSimVtO<sup>H,R</sup>(mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, a, b, salt)

1 : psk := F.Punct(mpk, ⟨Δv<sub>E</sub>⟩<sub>E</sub>)

2 : k* := (mpk, psk)

3 : **for** x ∈ I<sub>N,m</sub> \ {v<sub>E</sub>} :

4 : y<sub>x</sub> := pF<sup>H</sup>(k*, v<sub>E</sub>, x, salt)

5 : **shift** ← $Z_{p-1}$

6 : z<sub>E</sub> := VtO<sup>H</sup><sub>E</sub>(mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt, shift)

7 : **return** (shift, z<sub>E</sub>)

mSim'VtO<sup>H,R</sup>(mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, map, b,salt)

1 : psk := F.Punct(mpk, ⟨Δv<sub>E</sub>⟩<sub>E</sub>)

2 : k* := (mpk, psk)

3 : **for** x ∈ I<sub>N,m</sub> \ {v<sub>E</sub>} :

4 : y<sub>x</sub> := map (pF<sup>H</sup>(k*, v<sub>E</sub>, x, salt))

5 : s ← $\mathcal{D}_{m,c}$ ▷ defined in Lemma 8

6 : **shift** := $\sum_{x \in I_{N,m} \setminus \{v_E\}} y_x + s$

7 : z<sub>E</sub> := VtO<sup>H<sub>0</sub></sup><sub>E</sub>(mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt, shift)

8 : **return** (shift, z<sub>E</sub>)

mSimBatchfAuth<sup>H,R</sup>(mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt)

1 : psk := F.Punct(mpk, ⟨Δv<sub>E</sub>⟩<sub>E</sub>)

2 : k* := (mpk, psk)

3 : **for** x ∈ I<sub>N,m</sub> \ {v<sub>E</sub>} :

4 : y<sub>x</sub> := pF<sup>H</sup>(k*, v<sub>E</sub>, x, salt)

5 : **shift** ← $Z_{p-1}$

6 : z<sub>E</sub> := BatchfAuth<sup>H</sup><sub>E</sub>(mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt, shift)

7 : **return** (shift, z<sub>E</sub>)

Figure 1: Modifications of SimVtO, Sim'VtO, and SimBatchfAuth used by SimGC<sub>4</sub>, with changes compared to the original procedures highlighted in red.

**Lemma 22.** *Assume that H is a TCCR hash for exponential correlations with 2N<sup>m</sup> - 1 auxiliary powers over G (Definition 7). Then Hybrid<sub>2</sub> is computationally indistinguishable from Hybrid<sub>1</sub>.*

The straightforward reduction is given access to an oracle $O_?$ that is either $O$ or $R$, and given a distinguisher for the TCCR game with advantage $\epsilon$, runs $SimGC_2^{H,O_?}$ and distinguishes between Hybrid<sub>2</sub> and Hybrid<sub>3</sub> with advantage exactly $\epsilon$. Note that the condition that all queries $(x, y, z)$ to $O$ have distinct $(x, y)$ is enforced by the fact that all calls to $O$ in all procedures used by $SimGC_2$ use a unique and distinct salt.

**Hybrid<sub>4</sub>.** In this game, we define the algorithm $SimGC_4$ identically to $SimGC_3$, except that we modify the procedures $SimVtO$, $Sim'VtO$, and $SimBatchfAuth$ that it uses internally. We replace them with *modified procedures*, where the changes compared to the original procedures are highlighted in red, represented on Figure 1

* On line 5 of $mSimVtO^H$, shift is sampled uniformly at random. This is distributed exactly as in $SimVtO^{H,R}$, where shift is masked by the output of $R$ on a query that involves a unique salt (hence is never repeated).

* On line 6 of $mSim'VtO^H$, shift is computed as $\sum_{x \in I_{N,m} \setminus \{v_E\}} \text{map}(pF^H(k^*, v_E, x, \text{salt}))+s$, where $s \leftarrow \mathcal{D}_{t,c}$. In $Sim'VtO^{H,R}$, the only difference is that $s$ is computed as $\text{map}(O(\text{psk}, \text{salt}, 0))+b$. As salt is a unique
salt, map (O(psk, salt, 0)) + b is distributed as a random sample from $D_{t,c}^{(b)}$. By Lemma 8, the statistical distance between $D_{t,c}^{(b)}$ and $D_{t,c}$ is at most $t/2^c$.

* Eventually, on line 5 of mSimBatchfAuth<sup>H</sup>, shift is sampled uniformly at random. This is distributed exactly as in SimBatchfAuth<sup>H,R</sup>, where shift is masked by the output of <sup>R</sup> on a query that involves a unique salt.

To conclude, we observe that the procedures SimVtO, Sim'VtO, and SimBatchfAuth are called at most 9 times in total for a given batch, of which there are at most $|C|/t$. We therefore have the following lemma:

**Lemma 23.** No (possibly unbounded) distinguisher can distinguish between Hybrid<sub>3</sub> and Hybrid<sub>4</sub> with advantage better than $t \cdot |C|/(t \cdot 2^c)$.

**Hybrid<sub>5</sub>.** In this game, we observe that from Hybrid<sub>4</sub>, the values $k_u$ are not required anymore by SimGC<sub>4</sub>, because the modified procedures mSimVtO and mSim'VtO do not expects inputs (a, b) anymore. Formally, we define SimGC<sub>5</sub> as SimGC<sub>4</sub> by removing the parts denoted in blue from all procedures described in Section 7.2. Then, to compute d, it sets

$$d := (\ell_o \oplus y_o)_{o \in O(C)},$$

where $y = C(x)$. Using the invariant lemmas for each of the subprocedures (Lemma 26, Lemma 27, Lemma 28, and Lemma 29), it follows from an analysis identical to the correctness analysis in Section 6.2 that $(\ell_o \oplus y_o)_{o \in O(C)}$ is identical to the values $(k_o)_{o \in O(C)}$ computed by SimGC<sub>4</sub>, hence Hybrid<sub>5</sub> is perfectly indistinguishable from Hybrid<sub>4</sub>. Notice that SimGC<sub>5</sub> does not use the input $x$ anymore; this concludes the proof of Theorem 20.

## 7.2 Lemmas and Proofs for Hybrid<sub>2</sub>

As for GC.Garble, we first describe the high-level structure of SimGC<sub>2</sub>, and the main lemma, before introducing and analyzing the subprocedures it uses.

**Algorithm SimGC<sub>2</sub>(1<sup>λ</sup>, C, x)**

**Input.** A Boolean circuit $C$ with $|C| = s$ gates and depth depth($C$) = $D$ represented as described in Section 6.1; an input $x \in \{0, 1\}^{|I(C)|}$.

**Initialization.** The parts in blue are omitted in Hybrid<sub>5</sub>.

* Receive $(h_i)_{i \in [\pm N^m] \setminus \{0\}}$ from a challenger for the security game of the TCCR hash for exponential correlations with $2N^m - 1$ auxiliary powers over $\mathbb{G}$ (Definition 7).

* Set mpk := $(\mathbb{G}, p, G, (h_i)_{i \in [\pm N^m] \setminus \{0\}})$

* Let $O := O_{H,h_0,\Delta}$ denote the oracle of the TCCR security game.

* For each input wire $i$ receiving an input bit $x_i$, sample $(\ell_i, L_i) \leftarrow \{0, 1\} \times \mathbb{Z}_{p-1}$ and set $k_i := \ell_i \oplus x_i$.

**Procedure.** The simulation proceeds in a layer-by-layer fashion, from $\mathcal{L}_1$ to $\mathcal{L}_D$. After evaluating a layer $\mathcal{L}_d$, it labels each gate $u$ in the layer with a triple $(\ell_u, L_u, k_u)$ and stores a garbling $\hat{\mathcal{L}}_d$ of $\mathcal{L}_d$. The parts in blue are omitted in Hybrid<sub>5</sub>.
On layer $\mathcal{L}_d$. For $i = 1$ to $n_d$,

* Let $\text{Left}_{d,i}$ (resp. $\text{Right}_{d,i}$) denote the multisets of gates that are the left parent (resp. right parent) of a gate in $\mathcal{B}_{i,d}$. Retrieve the triples $(\ell_u, L_u, k_u)$ labeling each $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$ and compute

$$ (\ell_l, L_l, k_l, \text{shift}_{l,d,i}) := \text{SimPack}^{\text{H,O}}(\text{mpk}, (\ell_u, L_u, k_u)_{u \in \text{Left}_{l,d}}, \text{salt}_{i,d,0}) $$

$$ (\ell_r, L_r, k_r, \text{shift}_{r,d,i}) := \text{SimPack}^{\text{H,O}}(\text{mpk}, (\ell_u, L_u, k_u)_{u \in \text{Right}_{r,d}}, \text{salt}_{i,d,1}). $$

* If $\mathcal{L}_d$ is an AND layer:

- $(\ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}, S_{d,i}) := \text{SimBatchAnd}^{\text{H,O}}(\text{mpk}, (\ell_l, L_l, k_l), (\ell_r, L_r, k_r), \text{salt}_{d,i,2})$

- $((\ell[j], L_j, k[j])_{0 \le j \le t-1}, \text{shift}_{\text{out},d,i}) := \text{SimUnpack}^{\text{H,O}}(\Psi, \text{mpk}, \ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}, \text{salt}_{d,i,3})$

- $(\ell_u, L_u, k_u)_{u \in \mathcal{B}_{d,i}} := (\ell[j], L_j, k[j])_{0 \le j \le |\mathcal{B}_{d,i}| - 1}$

* If $\mathcal{L}_d$ is a XOR layer:

- $(\ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}, S_{d,i}) := \text{SimBatchXor}^{\text{H,O}}(\text{mpk}, (\ell_l, L_l, k_l), (\ell_r, L_r, k_r), \text{salt}_{d,i,2})$

- $((\ell[j], L_j, k_j)_{0 \le j \le t-1}, \text{shift}_{\text{out},d,i}) := \text{SimUnpack}^{\text{H,O}}(\Phi^{-1}, \text{mpk}, \ell_{\text{out}}, L_{\text{out}}, \text{salt}_{d,i,3})$

- $(\ell_u, L_u, k_u)_{u \in \mathcal{B}_{d,i}} := (\ell[j], L_j, k[j])_{0 \le j \le |\mathcal{B}_{d,i}| - 1}$

* Label each $u \in \mathcal{B}_{d,i}$ with $(\ell_u, L_u, k_u)$.

$$ \text{Set } \hat{\mathcal{L}}_d := (\text{shift}_{l,d,i}, \text{shift}_{r,d,i}, S_{d,i}, \text{shift}_{\text{out},d,i})_{i \le n_d}. $$

**Output.** Return $\hat{C} = (C, \text{mpk}, (\hat{\mathcal{L}}_d)_{d \le D}), \hat{x} := (\ell_i, L_i)_{i \le n}, \text{ and } d := (k_o)_{o \in O(C)}$.

Algorithm 13: Garbling procedure of the Boolean garbling scheme

The lemma below shows that $\text{Hybrid}_1$ and $\text{Hybrid}_2$ are perfectly indistinguishable (in fact, it shows an even stronger result):

**Lemma 24.** For any Boolean circuit $C$ with $|C|=s$ gates and depth $\text{depth}(C) = D$ represented as described in Section 6.1, any input $x \in \{0, 1\}^{|I(C)|}$, and any random tape $R$, it holds that

$$ \text{SimGC}_1(1^{\lambda}, C, x; R) = \text{SimGC}_2(1^{\lambda}, C, x; R). $$

*Proof.* Fix a Boolean circuit $C$, an input $x \in \{0, 1\}^{|I(C)|}$, and a random tape $R$. We consider a parallel run of $\text{SimGC}_1(1^{\lambda}, C, x; R)$ and $\text{SimGC}_2(1^{\lambda}, C, x; R)$. Both algorithms share a similar structure, up to the following distinction: whenever $\text{SimGC}_1$ invokes a procedure $\text{Proc}(\text{msk}, (\mathbf{k}, \mathbf{K})$, salt), $\text{SimGC}_2$ invokes a corresponding simulated procedure $\text{SimProc}(\text{mpk}, (\ell, \mathbf{L}, \mathbf{k})$, salt). We state a meta-lemma that captures the invariant that these procedures jointly maintain:

**Lemma 25.** (Meta invariant lemma) Let $\text{Proc} \in \{\text{Pack}_G^H, \text{BatchAND}_G^H, \text{UnpackAND}_G^H, \text{BatchXOR}_G^H, \text{UnpackXOR}_G^H\}$, and let $\text{SimProc} \in \{\text{SimPack}^{\text{H,O}}, \text{SimBatchAnd}^{\text{H,O}}, \text{SimUnpack}^{\text{H,O}}(\Psi, \cdot), \text{SimBatchXor}^{\text{H,O}}, \text{SimUnpack}^{\text{H,O}}(\Phi^{-1}, \cdot)\}$ denote the corresponding simulated procedure. Let $(\text{msk}, (\mathbf{k}, \mathbf{K})$, salt) denote the input to $\text{Proc}$ and $(\text{mpk}, (\ell, \mathbf{L}, \mathbf{k})$, salt) denote the input to $\text{SimProc}$ (note that we require that both algorithms receive the same $\mathbf{k}$ as input). Fix a
random tape R. Let Emb, Emb' denote the input and output embeddings defined by Proc. Denote

$$ (\mathbf{k}_1, \mathbf{K}_1, S_1) := \text{Proc}(\text{msk}, (\mathbf{k}, \mathbf{K}), \text{salt}; R) \\ (\ell_2, \mathbf{L}_2, \mathbf{k}_2, S_2) := \text{SimProc}(\text{mpk}, (\ell, \mathbf{L}, \mathbf{k}), \text{salt}; R). $$

Then, if it holds that $\mathbf{L} - \mathbf{K} = \Delta \cdot \text{Emb}(\ell)$, the following holds:

$$ \mathbf{k}_1 = \mathbf{k}_2, \quad S_1 = S_2, \quad \mathbf{L}_2 - \mathbf{K}_1 = \Delta \cdot \text{Emb}'(\ell_2). $$

The above lemma is a template “meta-lemma”: we will prove a corresponding formal lemma for each of the procedures. Then, we observe that the invariant is guaranteed at the input level: $\text{SimGC}_1$ and $\text{SimGC}_2$ first sample identical input labels $(\ell_i, L_i)_{i \le n}$ (as they use the same random tape) and define $k_i := \ell_i \oplus x_i$; $\text{SimGC}_1$ additionally sets $K_i := L_i - \Delta \cdot \ell_i$ (via the canonical embedding of $\mathbb{F}_2$ into $\mathbb{Z}_{p-1}$). It follows immediately that $\text{SimGC}_1$ and $\text{SimGC}_2$ output the same garbled input $\hat{x} := (\ell_i, L_i)_{i \le n}$.

From there, the invariant lemma guarantees that the invariant propagates throughout the entire evaluation of $\text{SimGC}_1$ and $\text{SimGC}_2$, maintaining the same wire key $k_u$ on each wire $u$ and producing the same sets of shifts $S_{d,i}$ for each batch $\mathcal{B}_{d,i}$. Therefore, $\text{SimGC}_1$ and $\text{SimGC}_2$ output identical $\hat{C}$ and $e$. ■

To finish the proof, we introduce each of the simulated procedures, and formally state and prove the corresponding invariant lemma.

**Simulator for the packing procedure.** The parts in blue are omitted in $\text{Hybrid}_5$.

**Algorithm** SimPack$^{H,O}$(mpk, $(\ell_u, L_u, k_u)_{u \in \mathcal{B}}$, salt)

**Input.** Master public key mpk. Wire labels and keys $(\ell_u, L_u, k_u)_{u \in \mathcal{B}} \in (\{0, 1\} \times \mathbb{Z}_{p-1} \times \{0, 1\})^{|\mathcal{B}|}$ for a batch of gates $\mathcal{B}$ of size $|\mathcal{B}| \le t$. Salt salt.

**Procedure.**

* Order the elements of $\mathcal{B}$ lexicographically as $(u_0, \dots, u_{|\mathcal{B}|-1})$, and set $(\ell[i], L[i]] := (\ell_{u_i}, L_{u_i})$ for $i = 0$ to $|\mathcal{B}|-1$. For $i = |\mathcal{B}|$ to $t-1$, set $(\ell[i], L[i]] := (0, 0)$.

* $k_{\text{out}} := \Phi(k[0], \dots, k[t-1])$

* $\ell_{\text{out}} := \Phi(\ell[0], \dots, \ell[t-1])$

* $\tilde{\ell}_{\text{out}} := \sum_{i=0}^{t-1} \ell[i] \cdot 2^i$

* $L \leftarrow \sum_{i=0}^{t-1} L[i] \cdot 2^i \mod p - 1 \quad \triangleright L = \langle \Delta \cdot \tilde{\ell}_{\text{out}} \rangle_{\mathcal{E}}$

* (shift, $L_{\text{out}}) := [2^t]$-SimBatchfAuth$^{H,O}$(mpk, $\tilde{\ell}_{\text{out}}$, L, Eval$_N \circ \Phi \circ \text{toBits}$, salt, shift)

**Output.** $(\ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}$, shift)

**Algorithm 14:** Simulator procedure for packing wire labels before a batch evaluation.

**Lemma 26** (Invariant lemma for packing). Fix (mpk, msk, $(\ell_u, L_u, k_u, K_u)_{u \in \mathcal{B}}$, salt) where msk := (mpk, $\Delta$, $h_0$). Assume that for each $u \in \mathcal{B}$, it holds that

$$ L_u - K_u = \Delta \cdot \ell_u \mod p - 1. $$
Then, denoting

$$ (\ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}, \text{shift}) := \text{SimPack}^{\text{H,O}}(\text{mpk}, (\ell_u, L_u, k_u)_{u \in \mathcal{B}}, \text{salt}) $$

$$ (k'_{\text{out}}, K'_{\text{out}}, \text{shift}') := \text{Pack}_{\text{G}}^{\text{H}}(\text{msk}, (k_u, K_u)_{u \in \mathcal{B}}, \text{salt}) $$

It holds that $k_{\text{out}} = k'_{\text{out}}$, shift = shift', and $L_{\text{out}} - K_{\text{out}} = \Delta \cdot \text{Eval}_{\text{N}}(\ell_{\text{out}}) \mod p - 1$.

*Proof.* Both $\text{SimPack}^{\text{H,O}}(\text{mpk}, (\ell_u, L_u, k_u)_{u \in \mathcal{B}}, \text{salt})$ and $\text{Pack}_{\text{G}}^{\text{H}}(\text{msk}, (k_u, K_u)_{u \in \mathcal{B}}, \text{salt})$ compute $k_{\text{out}}$ identically as $k_{\text{out}} := \Phi(k[0], \dots, k[t-1])$. By construction, we also have

$$ L - K = \sum_{i=0}^{t-1} (L[i] - K[i]) \cdot 2^i = \Delta \cdot \sum_{i=0}^{t-1} \ell[i] \cdot 2^i = \Delta \cdot \tilde{\ell}_{\text{out}} \quad \triangleright \text{ by assumption.} $$

Then, by Lemma 14, denoting $f := \text{Eval}_{\text{N}} \circ \Phi \circ \text{toBits}$, given (shift, $L_{\text{out}}$) := $\text{SimBatchfAuth}^{\text{H,O}}(\text{mpk}, \tilde{\ell}_{\text{out}}, L, f, \text{salt}, \text{shift})$, we have

$$ \text{shift} = \text{BatchfAuth}_{\text{G}}^{\text{H}}(\text{msk}, \Delta, K, f, \text{salt}), \text{ and} $$

$$ L_{\text{out}} = \text{BatchfAuth}_{\text{E}}^{\text{H}}(\text{mpk}, \tilde{\ell}_{\text{out}}, L, f, \text{salt}, \text{shift}). $$

Eventually, by correctness of BatchfAuth (Lemma 13), it holds that $L_{\text{out}} - K_{\text{out}} = \Delta \cdot f(\tilde{\ell}_{\text{out}}) \mod p - 1$, hence $L_{\text{out}} - K_{\text{out}} = \Delta \cdot \text{Eval}_{\text{N}}(\ell_{\text{out}}) \mod p - 1$ (by definition of $f$ and $\ell_{\text{out}}$). This concludes the proof. ■

**Simulator for the unpacking procedure.** The parts in blue are omitted in Hybrid$_5$.

**Algorithm** SimUnpack$^{\text{H,O}}(f, \text{mpk}, \ell, L, k, \text{salt})$

**Input.** Function $f \in \{\Phi^{-1}, \Psi\}$. Master public key msk, packed labels $(\ell, L) \in \mathbb{F}_{2^m} \times \mathbb{Z}_{p-1}$, packed key $k$, salt salt.

**Procedure.**

* $(k[0], \dots, k[t-1]) := f(k)$

* $(\ell[0], \dots, \ell[t-1]) := f(\ell)$

* $(\text{shift}, L_0, \dots, L_{t-1}) := \text{SimBatchfAuth}^{\text{H,O}}(\text{mpk}, \ell(N), L, (\text{Bit}_i \circ f \circ \text{toPoly}_N)_{0 \le i \le t-1})$

**Output.** $((\ell[i], L_i, k[i])_{i \le t-1}, \text{shift})$

**Algorithm 15:** Simulator procedure for unpacking the result of a batch evaluation.

**Lemma 27** (Invariant lemma for unpacking). Fix $(f, \text{mpk}, \text{msk}, \ell, L, k, K, \text{salt})$ where $f \in \{\Phi^{-1}, \Psi\}$ and msk := $(\text{mpk}, \Delta, h_0)$. Assume that it holds that

$$ L - K = \Delta \cdot \text{Eval}_{\text{N}}(\ell_u) \mod p - 1. $$
Then, denoting

$$((\ell[i], L_i, k[i])_{i \le t-1}, \text{shift}) := \text{SimUnpack}^{\text{H,O}}(f, \text{mpk}, \ell, L, k, \text{salt})$$

$$((k'[i], K'_i)_{i \le t-1}, \text{shift}') := \text{Unpack}_G^H(f, \text{msk}, k, K, \text{salt})$$

It holds that $k[i] = k'[i]$ for all $i \le t-1$, shift = shift', and $L_i - K_i = \Delta \cdot (\ell[i]) \mod p - 1$ for all $i \le t-1$.

*Proof.* The first equality follows immediately, as $k[i], k'[i]$ are computed identically in $\text{SimUnpack}^{\text{H,O}}$ and $\text{Unpack}^{\text{H}}$. Then, using the assumptions of Lemma 27, we can invoke the perfect simulation of $\text{SimBatchfAuth}$ to get

$$(\text{shift}, \text{\_}) = \text{BatchfAuth}_G^H(\text{msk}, \Delta, K, (\text{Bit}_i \circ f \circ \text{toPoly}_N)_{0 \le i \le t-1})$$

$$(L_0, \dots, L_{t-1}) = \text{BatchfAuth}_E^H(\text{mpk}, \ell(N), L, (\text{Bit}_i \circ f \circ \text{toPoly}_N)_{0 \le i \le t-1}),$$

and we conclude using the perfect correctness of $\text{Unpack}^{\text{H}}$ (Lemma 17).

<figure><img src="image_6.png" /></figure>

**Simulator for the batch-XOR gadget.** The parts in blue are omitted in $\text{Hybrid}_5$. $S_{N,m}$ denote the set of sums of two elements from $l_{N,m}$.

**Algorithm** SimBatchXor$^{\text{H,O}}$(mpk, $(\ell_l, L_l)$, $(\ell_r, L_r)$, $k_l, k_r$, salt)

**Input.** Master public key mpk. Packed labels $(\ell_l, L_l)$, $(\ell_r, L_r)$, keys $(k_l, k_r)$, and salt salt.

**Procedure.**

* $\tilde{\ell}_{\text{out}} := \ell_l + \ell_r \triangleright \text{Over } \mathbb{Z}[X]$

* $k_{\text{out}} := k_l + k_r \triangleright \text{Over } \mathbb{F}_{2^m}$

* $\ell_{\text{out}} = \tilde{\ell}_{\text{out}} \mod 2 \triangleright \ell_{\text{out}} \in \mathbb{F}_{2^m}$

* $\tilde{L}_{\text{out}} := L_l + L_r \mod p - 1$

* $(\text{shift}, L_{\text{out}}) := S_{N,m} - \text{SimBatchfAuth}^{\text{H,O}}(\text{mpk}, \tilde{\ell}_{\text{out}}, \tilde{L}_{\text{out}}, \text{Mod}_N(\cdot, 2), \text{salt})$

**Output.** $(\ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}, \text{shift})$

<caption>Algorithm 16: Simulator for the batch-XOR gadget</caption>

**Lemma 28** (Invariant lemma for batch-XOR). Fix (mpk, msk, $\ell_l, L_l, \ell_r, L_r, k_l, K_l, k_r, K_r$, salt) where msk := (mpk, $\Delta, h_0$). Assume that for $u \in \{l, r\}$, it holds that

$$L_u - K_u = \Delta \cdot \text{Eval}_N(\ell_u) \mod p - 1.$$

Then, denoting

$$(\ell_{\text{out}}, L_{\text{out}}, k_{\text{out}}, \text{shift}) := \text{SimBatchXor}^{\text{H,O}}(\text{mpk}, (\ell_l, L_l, k_l), (\ell_r, L_r, k_r), \text{salt})$$

$$(k'_{\text{out}}, K'_{\text{out}}, \text{shift}') := \text{BatchXOR}_G^H(\text{msk}, (k_l, K_l), (k_r, K_r), \text{salt}),$$

it holds that $k_{\text{out}} = k'_{\text{out}}$, shift = shift', and $L_{\text{out}} - K_{\text{out}} = \Delta \cdot \text{Eval}_N(\ell_{\text{out}}) \mod p - 1$.
Proof. $\tilde{\ell}_{out}$, $\ell_{out}$, and $\tilde{L}_{out}$ are computed identically in BatchXOR<sup>H</sup><sub>E</sub>. Denoting $\tilde{K}'_{out}$ the value computed in BatchXOR<sup>H</sup><sub>G</sub> as $K_I + K_R \mod p - 1$, we established in the proof of Lemma 18 that

$$ \tilde{L}'_{out} - \tilde{K}'_{out} = \Delta \cdot \tilde{\ell}'_{out}(N) \mod p - 1 $$

and we can therefore invoke the perfect simulation of SimBatchfAuth to get

$$ (\text{shift}, \text{\texttt{}}) = \text{BatchfAuth}_{\text{G}}^{\text{H}}(\text{msk}, \Delta, \tilde{K}_{\text{out}}, \text{Mod}_{\text{N}}(\cdot, 2), \text{salt}) $$

$$ L_{\text{out}} = \text{BatchfAuth}_{\text{E}}^{\text{H}}(\text{mpk}, \tilde{\ell}_{\text{out}}(N), \tilde{L}_{\text{out}}, \text{Mod}_{\text{N}}(\cdot, 2), \text{salt}, \text{shift}) $$

and we conclude using the perfect correctness of BatchXOR<sup>H</sup> (Lemma 18). ■

**Simulation for the batch-AND gadget.** The parts in blue are omitted in Hybrid<sub>5</sub>; because Z-Sim'VtO and SimVtO expect an input there, but this input is not used anymore by the modified subprocedures mSim'VtO and mSimVtO, an arbitrary dummy input (e.g. 0) can be passed as input instead.

**Algorithm SimBatchAnd<sup>H,O</sup>(mpk, (l<sub>1</sub>, L<sub>1</sub>, k<sub>1</sub>), (l<sub>r</sub>, L<sub>r</sub>, k<sub>r</sub>), salt)**

**Input.** Master public key mpk. Packed labels (l<sub>1</sub>, L<sub>1</sub>), (l<sub>r</sub>, L<sub>r</sub>), keys (k<sub>1</sub>, k<sub>r</sub>), and salt salt. For i = 1 to 6, we let salt<sub>i</sub> := salt||i.

**Procedure.**

* $(k'_1, k'_r) \leftarrow \text{Pert}_c(k_I) \times \text{Pert}_c(k_r)$

* $(\text{shift}_a, \tilde{a}_E) := \mathbb{Z}\text{-Sim}'\text{VtO}^{\text{H,O}}(\text{mpk}, \ell_r(N), L_r, \text{map}, k'_I(N), \text{salt}_1)$

* $(\text{shift}_b, \tilde{b}_E) := \mathbb{Z}\text{-Sim}'\text{VtO}^{\text{H,O}}(\text{mpk}, \ell_l(N), L_l, \text{map}, k'_r(N), \text{salt}_2)$

* $\tilde{\ell}_{out} := \ell_l(N)\ell_r(N) + \tilde{a}_E + \tilde{b}_E$

* $a_E := [\text{toPoly}_N(\tilde{a}_E) \mod 2, P] \triangleright a_E \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

* $b_E := [\text{toPoly}_N(\tilde{b}_E) \mod 2, P] \triangleright b_E \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

* $\ell_{out} := \ell_l\ell_r + a_E + b_E \triangleright \ell_{out} = \text{Mod}_N(\tilde{\ell}_{out}) \in \mathbb{F}_{2^m}$

* $k_{out} := \ell_{out} + (\ell_l + k_l) \cdot (\ell_r + k_r) \triangleright \text{over } \mathbb{F}_{2^m}$

* $(\text{shift}_\alpha, \alpha_E) := \text{SimVtO}^{\text{H,O}}(\text{mpk}, \ell_r(N), L_r, k'_I(N), 0, \text{salt}_3)$

* $(\text{shift}_\beta, \beta_E) := \text{SimVtO}^{\text{H,O}}(\text{mpk}, \ell_l(N), L_l, k'_r(N), 0, \text{salt}_4)$

* $(\text{shift}_\gamma, \gamma_E) := \text{SimVtO}^{\text{H,O}}(\text{mpk}, \ell_r(N), L_r, -k_l(N), L_l, \text{salt}_5)$

* $\tilde{L}_{out} := \alpha_E + \beta_E - \gamma_E + L_l\ell_r(N) \triangleright \tilde{L}_{out} = \langle \Delta\tilde{\ell}_{out} \rangle_E$

* $(\text{shift}_K, L_{out}) := [N^m]$- SimBatchfAuth<sup>H,O</sup>(mpk, $\tilde{\ell}_{out}$, $\tilde{L}_{out}$, $\text{Mod}_{N}(\cdot, 2, P)$, salt<sub>6</sub>)

* $S_{out} := (\text{shift}_a, \text{shift}_b, \text{shift}_\alpha, \text{shift}_\beta, \text{shift}_\gamma, \text{shift}_K)$

**Output.** $(\ell_{out}, L_{out}, k_{out}, S_{out})$

<caption>Algorithm 17: Simulation for the batch-AND gadget</caption>
**Lemma 29** (Invariant lemma for batch-AND). Fix (mpk, msk, $\ell_l$, $L_l$, $\ell_r$, $L_r$, $k_l$, $K_l$, $k_r$, $K_r$, salt) where msk := (mpk, $\Delta$, $h_0$). Assume that for $u \in \{l, r\}$, it holds that

$$L_u - K_u = \Delta \cdot \mathrm{Eval}_N(\ell_u) \mod p - 1.$$

Then, denoting

$$(\ell_{\mathrm{out}}, L_{\mathrm{out}}, k_{\mathrm{out}}, \mathrm{shift}) := \mathrm{SimBatchAnd}^{H,O}(\mathrm{mpk}, (\ell_l, L_l, k_l), (\ell_r, L_r, k_r), \mathrm{salt})$$

$$(k'_{\mathrm{out}}, K'_{\mathrm{out}}, \mathrm{shift}') := \mathrm{BatchAND}^{H}_G(\mathrm{msk}, (k_l, K_l), (k_r, K_r), \mathrm{salt}),$$

it holds that $k_{\mathrm{out}} = k'_{\mathrm{out}}$, shift = shift', and $L_{\mathrm{out}} - K_{\mathrm{out}} = \Delta \cdot \mathrm{Eval}_N(\ell_{\mathrm{out}}) \mod p - 1$.

**Proof.** The second and third equality can be tracked down by going through the procedures BatchAND<sup>H</sup><sub>G</sub>, BatchAND<sup>H</sup><sub>E</sub>, and SimBatchAnd<sup>H,O</sup>, and relying on the perfect simulation lemmas for VtO and BatchfAuth. Concretely, fix (mpk, msk, $\ell_l$, $L_l$, $\ell_r$, $L_r$, $k_l$, $K_l$, $k_r$, $K_r$, salt) and consider a run of SimBatchAnd<sup>H,O</sup>(mpk, ($\ell_l$, $L_l$, $k_l$), ($\ell_r$, $L_r$, $k_r$), salt). Using perfect simulation of Sim'VtO (the second part of Lemma 12) together with the assumptions of Lemma 29 yields

$$(\mathrm{shift}_a, -) = \mathbb{Z}-\mathrm{VtO}^{H_0}_G(\mathrm{msk}, k'_l(N), K_r, \mathrm{salt}_1)$$

$$\tilde{a}_E = \mathbb{Z}-\mathrm{VtO}^{H_0}_E(\mathrm{mpk}, \ell_r(N), L_r, \mathrm{salt}_1, \mathrm{shift}_a)$$

$$(\mathrm{shift}_b, -) = \mathbb{Z}-\mathrm{VtO}^{H_0}_G(\mathrm{msk}, k'_r(N), K_l, \mathrm{salt}_2)$$

$$\tilde{b}_E = \mathbb{Z}-\mathrm{VtO}^{H_0}_E(\mathrm{mpk}, \ell_l(N), L_l, \mathrm{salt}_2, \mathrm{shift}_b).$$

From there, the computation of ($a_E$, $b_E$, $\tilde{\ell}_{\mathrm{out}}$, $\ell_{\mathrm{out}}$) proceeds identically to BatchAND<sup>H</sup><sub>E</sub>. Hence, denoting ($\ell'_{\mathrm{out}}$, $L'_{\mathrm{out}}$) := BatchAND<sup>H</sup><sub>E</sub>(msk, ($\ell_l$, $L_l$), ($\ell_r$, $L_r$), salt, $S$), we get $\ell'_{\mathrm{out}} = \ell_{\mathrm{out}}$. By correctness of BatchAND<sup>H</sup><sub>E</sub> (Lemma 19), $k'_{\mathrm{out}} + \ell_{\mathrm{out}} = (\ell_l + k_l) \cdot (\ell_r + k_r)$, and it follows that $k_{\mathrm{out}} = k'_{\mathrm{out}}$.

Using now perfect simulation of SimVtO (the first part of Lemma 12) together with the assumptions of Lemma 29 yields

$$(\mathrm{shift}_\alpha, -) = \mathrm{VtO}^{H}_G(\mathrm{msk}, \Delta k'_l(N), K_r, \mathrm{salt}_3)$$

$$\alpha_E = \mathrm{VtO}^{H}_E(\mathrm{mpk}, \ell_r(N), L_r, \mathrm{salt}_3, \mathrm{shift}_\alpha)$$

$$(\mathrm{shift}_\beta, -) = \mathrm{VtO}^{H}_G(\mathrm{msk}, \Delta k'_r(N), K_l, \mathrm{salt}_4)$$

$$\beta_E = \mathrm{VtO}^{H}_E(\mathrm{mpk}, \ell_l(N), L_\ell, \mathrm{salt}_4, \mathrm{shift}_\beta)$$

$$(\mathrm{shift}_\gamma, -) = \mathrm{VtO}^{H}_G(\mathrm{msk}, K_l, K_r, \mathrm{salt}_5)$$

$$\gamma_E = \mathrm{VtO}^{H}_E(\mathrm{mpk}, \ell_r(N), L_r, \mathrm{salt}_5, \mathrm{shift}_\gamma).$$

Then, the computation of $\tilde{L}_{\mathrm{out}}$ proceeds identically to BatchAND<sup>H</sup><sub>E</sub>. In particular, denoting $\tilde{K}'_{\mathrm{out}}$, $\tilde{L}'_{\mathrm{out}}$ the values computed in BatchAND<sup>H</sup><sub>G</sub> and BatchAND<sup>H</sup><sub>E</sub> respectively, we get $\tilde{L}'_{\mathrm{out}} = \tilde{L}_{\mathrm{out}}$. Furthermore, in the proof of Lemma 19, we established

$$\tilde{L}'_{\mathrm{out}} - \tilde{K}'_{\mathrm{out}} = \Delta \cdot \tilde{\ell}_{\mathrm{out}} \mod p - 1.$$

Therefore, the assumptions of Lemma 14 are satisfied and we can invoke perfect simulation of SimBatchfAuth<sup>H,O</sup> (Lemma 14) to get

$$(\mathrm{shift}_K, -) = \mathrm{BatchfAuth}^{H}_G(\mathrm{msk}, \Delta, \tilde{K}_{\mathrm{out}}, \mathrm{Mod}_N(\cdot, 2, P), \mathrm{salt}_6)$$

$$L_{\mathrm{out}} = \mathrm{BatchfAuth}^{H}_E(\mathrm{mpk}, \tilde{\ell}_{\mathrm{out}}, \tilde{L}_{\mathrm{out}}, \mathrm{Mod}_N(\cdot, 2, P), \mathrm{salt}_6, \mathrm{shift}_K),$$

which concludes the proof.

<figure><img src="image_7.png" /></figure>
## 8 $\omega(1/\lambda)$-Rate Boolean Garbling for Layered Circuits in the Standard Model

In this section, we describe a boolean garbling scheme that achieves a rate of $\lambda/\sqrt{\log \lambda}$, with security reducing to the power-DDH assumption (Definition 4) and a TCR hash function for exponential correlations (Definition 6). Thus, compared to the garbling scheme in Section 6, the security of this scheme no longer requires the GGM. However, this comes at the cost of supporting only layered circuits and incurring an overhead in the concrete size of the garbled circuit.

In more detail, the garbling scheme follows the same template as the one presented in Section 6, except that it uses the leveled TCCR hash function from Definition 8. As a result, unlike the GGM-secure TCCR hash (Definition 7), we can no longer “encrypt” linear functions of the PPRF secret key using PPRF evaluations. This, in turn, implies that we cannot directly use the PPRF secret key as input to the BatchfAuth procedure in our garbling gadgets. To circumvent this issue, we adopt a standard key-switching technique: the garbler samples multiple PPRF keys and the evaluator’s share for the output of gates at each level are authenticated using a fresh key. It is easy to see that security then follows immediately from our definition of the leveled TCCR hash. However, since our garbling scheme packs multiple boolean values together when evaluating each gate, the key-switching technique requires that all of the packed values are authenticated under the same key. Consequently, we can only support layered circuits (see Section 3), where every wire in the circuit is between gates at consecutive layers. Moreover, the garbler must now send 4D PPRF public keys, where $D$ is the depth of the circuit, adding an overhead to the size of the garbled circuit. However, for circuits that are sufficiently wide, this does not impact the rate. We note that layered circuits are expressive enough to capture a variety of useful computations, including FFT circuits, symmetric cryptographic primitives like block ciphers, and dynamic programming algorithms like longest common subsequence. We refer the reader to [Cou19] for a more detailed discussion.

Next, we describe the parameters and algorithms used in the garbling scheme and then proceed to present the complete description of the scheme.

**Parameters.** We use the same parameters as the garbling scheme in Section 6. Specifically, let $(\mathcal{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$. Let $t = \sqrt{\log \lambda}$ denote the batch parameter and $(\Phi, \Psi)$ be a $(t, m)_2$-reverse multiplication friendly embedding with $m = O(t)$. Let $c = \omega(1)$ denote a statistical security parameter with $c \le 2^{\sqrt{\log \lambda}}$ and set $N = 2c \cdot m \cdot (2^m+1)+1$ (note that $N^m = \text{poly}(\lambda)$). Let $H = \{H_\lambda : \mathcal{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}\}_{\lambda \in \mathbb{N}}$ denote a TCR hash family for exponential correlation with auxiliary powers over $\mathcal{G}$ (Definition 6). Let $H_0 := \text{map} \circ H$, where $\text{map} = \text{map}_{N,m,c}$ is the mapping from Definition 9.

**Algorithms.** As discussed earlier, employing the leveled TCCR hash necessitates the use of multiple PPRF keys. However, this does not require any modification to $(\text{Pack}_G^H, \text{UnpackAND}_G^H, \text{BatchXOR}_G^H, \text{UnpackXOR}_G^H)$ from Section 6, as these procedures take the PPRF public key as input and only use it to authenticate the evaluator's share in a call to BatchfAuth. During evaluation, we simply invoke them with different keys as needed. On the other hand, we modify the garbler's algorithms $(\text{Pack}_G^H, \text{UnpackAND}_G^H, \text{BatchXOR}_G^H, \text{UnpackXOR}_G^H)$ to additionally take as input $\Delta_{\text{out}}$, which is the PPRF secret key for the next layer. These algorithms then invoke $\text{BatchfAuth}(\text{msk}, \Delta_{\text{out}}, \cdot, \cdot, \cdot)$ in the last step when authenticating the evaluator's share. Finally, since the gadget used for garbling and evaluating AND gates makes multiple use of the PPRF key, we modify them to use a different PPRF key for intermediate computations. The modified variants are described in Algorithms 18 and 19.
**Algorithm BatchAND<sup>H</sup><sub>G</sub>(msk, msk', Δ<sub>out</sub>, (k<sub>l</sub>, K<sub>l</sub>), (k<sub>r</sub>, K<sub>r</sub>), salt)**

**Input.** Master secret keys msk and msk', and $\Delta_{\text{out}} \in \mathbb{Z}_{p-1}$. Packed keys $(k_l, K_l), (k_r, K_r)$. Salt salt. Parse msk := (mpk, Δ, $h_0$) and msk' := (mpk', Δ', $h'_0$). For $i = 1$ to 7, let salt$_i$ := salt$||$7.

**Procedure.**

• $(k', k') \leftarrow \$ \text{Pert}_c(k_l) \times \text{Pert}_c(k_r)$

• (shift<sub>a</sub>, $\tilde{a}_G$) := $\mathbb{Z}$-VtO<sup>H<sub>0</sub></sup><sub>G</sub>(msk, $k'_l(N)$, $K_r$, salt<sub>1</sub>)
▷ $\tilde{a}_G = \langle k'_l(N) \ell_r(N) \rangle_G$

• (shift<sub>b</sub>, $\tilde{b}_G$) := $\mathbb{Z}$-VtO<sup>H<sub>0</sub></sup><sub>G</sub>(msk, $k'_r(N)$, $K_l$, salt<sub>2</sub>)
▷ $\tilde{b}_G = \langle k'_r(N) \ell_l(N) \rangle_G$

• $a_G := [\text{toPoly}_N(\tilde{a}_G) \bmod 2, P]$ ▷ $a_G \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $b_G := [\text{toPoly}_N(\tilde{b}_G) \bmod 2, P]$ ▷ $b_G \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $k_{\text{out}} := k_l k_r + a_G + b_G$ ▷ over $\mathbb{F}_{2^m}$

• (shift<sub>α</sub>, $\alpha_G$) := VtO<sup>H</sup><sub>G</sub>(msk, $\Delta'k'_l(N)$, $K_r$, salt<sub>3</sub>)
▷ $\alpha_G = \langle \Delta'k'_l(N) \cdot \ell_r(N) \rangle_G$

• (shift<sub>β</sub>, $\beta_G$) := VtO<sup>H</sup><sub>G</sub>(msk, $\Delta'k'_r(N)$, $K_l$, salt<sub>4</sub>)
▷ $\beta_G = \langle \Delta'k'_r(N) \cdot \ell_l(N) \rangle_G$

• (shift<sub>K'</sub>, $K'_l$) := VtO<sup>H</sup><sub>G</sub>(msk, $\Delta'$, $K_l$, salt<sub>5</sub>)
▷ $K'_l = \langle \Delta' \tilde{\ell}_l \rangle_G$

• (shift<sub>γ</sub>, $\gamma_G$) := VtO<sup>H</sup><sub>G</sub>(msk, $K'_l$, $K_r$, salt<sub>6</sub>) ▷ $\gamma_G = \langle K'_l \cdot \ell_r(N) \rangle_G$

• $\tilde{K}_{\text{out}} := \alpha_G + \beta_G - \gamma_G + \Delta'(\tilde{a}_G + \tilde{b}_G)$ ▷ $\tilde{K}_{\text{out}} = \langle \Delta' \tilde{\ell}_{\text{out}} \rangle_G$

• (shift<sub>K</sub>, $K_{\text{out}}$) := [$N^m$]-BatchfAuth<sup>H</sup><sub>G</sub>(msk', $\Delta_{\text{out}}$, $\tilde{K}_{\text{out}}$, Mod<sub>N</sub>(·, 2, P), salt<sub>7</sub>)
▷ $K_{\text{out}} = \langle \Delta_{\text{out}} \ell_{\text{out}} \rangle_G$

• $S_{\text{out}} := (\text{shift}_a, \text{shift}_b, \text{shift}_\alpha, \text{shift}_\beta, \text{shift}_{K'}, \text{shift}_\gamma, \text{shift}_K)$

**Output.** ($(k_{\text{out}}, K_{\text{out}}), S_{\text{out}}$)

Algorithm 18: Garbler batch-AND gadget using the leveled TCCR hash. We highlight the changes from Algorithm 11 in red.

**Algorithm BatchAND<sup>H</sup><sub>E</sub>(mpk, mpk', (l<sub>l</sub>, L<sub>l</sub>), (l<sub>r</sub>, L<sub>r</sub>), salt, S)**

**Inputs.** Master public keys mpk and mpk'. Packed labels $(l_l, L_l), (l_r, L_r)$, salt salt and garbling material $S$. Parse $S := (\text{shift}_a, \text{shift}_b, \text{shift}_\alpha, \text{shift}_\beta, \text{shift}_{K'}, \text{shift}_\gamma, \text{shift}_K)$. For $i = 1$ to 7, let salt$_i$ := salt$||$i.

**Procedure.**

• $\tilde{a}_E := \mathbb{Z}$-VtO<sup>H<sub>0</sub></sup><sub>E</sub>(mpk, $\ell_r(N)$, $L_r$, salt<sub>1</sub>, shift<sub>a</sub>)
▷ $\tilde{a}_E = \langle k'_l(N) \ell_r(N) \rangle_E$
• $\tilde{b}_E := \mathbb{Z}-VtO_E^H(\text{mpk}, \ell_1(N), L_1, \text{salt}_2, \text{shift}_b) \succ \tilde{b}_E = \langle k'_r(N)\ell_1(N) \rangle_E$

• $\tilde{\ell}_{\text{out}} := \ell_1(N)\ell_r(N) + \tilde{a}_E + \tilde{b}_E$

• $a_E := [\text{toPoly}_N(\tilde{a}_E) \bmod 2, P] \succ a_E \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $b_E := [\text{toPoly}_N(\tilde{b}_E) \bmod 2, P] \succ b_E \in \mathbb{F}_2[X]/P(X) \cong \mathbb{F}_{2^m}$

• $\ell_{\text{out}} := \ell_1\ell_r + a_E + b_E \succ \ell_{\text{out}} = \text{Mod}_N(\tilde{\ell}_{\text{out}}) \in \mathbb{F}_{2^m}$

• $\alpha_E := \text{VtO}_E^H(\text{mpk}, \ell_r(N), L_r, \text{salt}_3, \text{shift}_\alpha)$

$$ \succ \alpha_E = \langle \Delta' k'_1(N) \cdot \ell_r(N) \rangle_E $$

• $\beta_E := \text{VtO}_E^H(\text{mpk}, \ell_1(N), L_1, \text{salt}_4, \text{shift}_\beta)$

$$ \succ \beta_E = \langle \Delta' k'_r(N) \cdot \ell_1(N) \rangle_E $$

• $L'_1 := \text{VtO}_E^H(\text{mpk}, \ell_1(N), L_1, \text{salt}_5, \text{shift}_{K'}) \succ L'_1 = \langle \Delta' \tilde{\ell}_1 \rangle_E$

• $\gamma_E := \text{VtO}_E^H(\text{mpk}, \ell_r(N), L_r, \text{salt}_6, \text{shift}_\gamma) \succ \gamma_E = \langle K_1 \cdot \ell_r(N) \rangle_E$

• $\tilde{L}_{\text{out}} := \alpha_E + \beta_E - \gamma_E + L'_1\ell_r(N) \succ \tilde{L}_{\text{out}} = \langle \Delta' \tilde{\ell}_{\text{out}} \rangle_E$

• $L_{\text{out}} := [N^m]$-BatchfAuth$_E^H(\text{mpk}', \tilde{\ell}_{\text{out}}, \tilde{L}_{\text{out}}, \text{Mod}_N(\cdot, 2, P), \text{salt}_7, \text{shift}_K)$

$$ \succ L_{\text{out}} = \langle \Delta_{\text{out}} \ell_{\text{out}} \rangle_E $$

**Output.** ($\ell_{\text{out}}, L_{\text{out}}$)

**Algorithm 19:** Evaluator batch-AND gadget using the leveled TCCR hash. We highlight the changes from Algorithm 12 in red.

**Input.** The input to GC.Garble is a layered boolean circuit $C$ with $|C|=s$ gates and $n = |I(C)|$ inputs such that the gates can be partitioned into layers ($\mathcal{L}_1, \dots, \mathcal{L}_D$), where every wire only connects adjacent layers. Let $\mathcal{L}_d^{\text{and}}$ and $\mathcal{L}_d^{\text{xor}}$ denote the set of AND gates and XOR gates in the $d$-th layer. In each layer $\mathcal{L}_d$, we separately partition the set of AND gates and XOR gates into $n_d := \lceil |\mathcal{L}_d^{\text{and}}|/t \rceil + \lceil |\mathcal{L}_d^{\text{xor}}|/t \rceil$ batches ($\mathcal{B}_{d,1}, \dots, \mathcal{B}_{d,n_d}$) containing at most $t$ gates each. For $d=1$ to $D$, let $\text{salt}_{d,1}, \dots, \text{salt}_{d,n_d}$ denote unique identifiers for each batch of gate, and write $\text{salt}_{d,i,j} := \text{salt}_{d,i} \parallel j$ for $j \in \{0, 1, 2, 3\}$. We assume that all these data can be parsed from the description $C$ of the circuit.

**Garbling scheme.** We next proceed to describe the leveled garbling scheme. The encoding and decoding algorithms GC.Enc and GC.Dec are identical to those described in Section 6, namely Algorithms 2 and 4. We present GC.Garble and GC.Eval in Algorithms 3 and 13, respectively.

**Algorithm GC.Garble(1$^{\lambda}$, C)**

**Input.** A **layered** boolean circuit $C$ with $|C|=s$ gates and depth $\text{depth}(C) = D$. The input gates are indexed from 1 to $n$.

**Initialization.**

• Sample $(\text{mpk}_0, \text{msk}_0), \dots, (\text{mpk}_{4D}, \text{msk}_{4D}) \leftarrow \text{F}\text{Setup}(1^{\lambda}, N^m)$. Parse each $\text{msk}_i := (\text{mpk}_i, \Delta_i, g_0)$.

• For each input wire $i$, sample $(k_i, K_i) \leftarrow \{0, 1\} \times \mathbb{Z}_{p-1}$.
**Procedure.** The garbling proceeds in a layer-by-layer fashion, from $\mathcal{L}_1$ to $\mathcal{L}_D$. After evaluating a layer $\mathcal{L}_d$, it labels each gate $u$ in the layer with a pair $(k_u, K_u)$ and stores a garbling $\hat{\mathcal{L}}_d$ of $\mathcal{L}_d$.

On layer $\mathcal{L}_d$. For $i = 1$ to $n_d$,

* Let $\text{Left}_{d,i}$ (resp. $\text{Right}_{d,i}$) denote the multisets of gates that are the left parent (resp. right parent) of a gate in $\mathcal{B}_{d,i}$. Retrieve the pairs $(k_u, K_u)$ labeling each $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$ and compute

$$ (k_l, K_l, \text{shift}_{l,d,i}) := \text{Pack}_{\text{G}}^{\text{H}}(\text{msk}_{4d-4}, \Delta_{4d-3}, (k_u, K_u)_{u \in \text{Left}_{d,i}}, \text{salt}_{d,i,0}) $$

$$ (k_r, K_r, \text{shift}_{r,d,i}) := \text{Pack}_{\text{G}}^{\text{H}}(\text{msk}_{4d-4}, \Delta_{4d-3}, (k_u, K_u)_{u \in \text{Right}_{d,i}}, \text{salt}_{d,i,1}). $$

* If $\mathcal{B}_{d,i}$ is a batch of AND gates:

- $(k_{\text{out}}, K_{\text{out}}, S_{d,i}) \leftarrow \text{BatchAND}_{\text{G}}^{\text{H}}(\text{msk}_{4d-3}, \text{msk}_{4d-2}, \Delta_{4d-1}, (k_l, K_l), (k_r, K_r), \Delta, \text{salt}_{d,i,2})$

- $((k[j], K_j)_{0 \le i \le t-1}, \text{shift}_{\text{out},d,i}) := \text{UnpackAND}_{\text{G}}^{\text{H}}(\text{msk}_{4d-1}, \Delta_{4d}, k_{\text{out}}, K_{\text{out}}, \text{salt}_{d,i,3})$

- $(k_u, K_u)_{u \in \mathcal{B}_{d,i}} := (k[j], K_j)_{0 \le j \le |\mathcal{B}_{d,i}|-1}$

* If $\mathcal{B}_{d,i}$ is a batch of XOR gates:

- $(k_{\text{out}}, K_{\text{out}}, S_{d,i}) \leftarrow \text{BatchXOR}_{\text{G}}^{\text{H}}(\text{msk}_{4d-3}, \Delta_{4d-1}, (k_l, K_l), (k_r, K_r), \Delta, \text{salt}_{d,i,2})$

- $((k[j], K_j)_{0 \le j \le t-1}, \text{shift}_{\text{out},d,i}) := \text{UnpackXOR}_{\text{G}}^{\text{H}}(\text{msk}_{4d-1}, \Delta_{4d}, k_{\text{out}}, K_{\text{out}}, \text{salt}_{d,i,3})$

- $(k_u, K_u)_{u \in \mathcal{B}_{d,i}} := (k[j], K_j)_{0 \le j \le |\mathcal{B}_{d,i}|-1}$

* Label each $u \in \mathcal{B}_{d,i}$ with the key pair $(k_u, K_u)$.

$$ \text{Set } \hat{\mathcal{L}}_d := (\text{shift}_{l,d,i}, \text{shift}_{r,d,i}, S_{d,i}, \text{shift}_{\text{out},d,i})_{i \le n_d}. $$

**Output.** Return $e := ((k_i, K_i)_{i \le n}, \Delta_0)$, $\hat{C} := (C, \{\text{mpk}_i\}_{i=0}^{4D}, (\hat{\mathcal{L}}_d)_{d \le D})$, and $d := (k_0)_{0 \in O(C)}$.

Algorithm 20: Garbling procedure of the leveled Boolean garbling scheme. We highlight the key changes to Algorithm 13 in red.

**Algorithm GC.Eval($\hat{C}$, $\hat{x}$)**

**Inputs.** Parse $\hat{C}$ as $(C, \{\text{mpk}_i\}_{i=0}^{4D}, (\hat{\mathcal{L}}_d)_{d \le D})$ and $\hat{x}$ as $(\ell_i, L_i)_{i \le n} \in (\mathbb{F}_2 \times \mathbb{Z}_{p-1})^n$.

**Procedure.** The evaluation proceeds in a layer-by-layer fashion, from $\mathcal{L}_1$ to $\mathcal{L}_D$. After evaluating a layer $\mathcal{L}_d$, it labels each gate $u$ in the layer with a pair $(\ell_u, L_u)$.

On layer $\mathcal{L}_d$. For $i = 1$ to $n_d$,

* Parse $\hat{\mathcal{L}}_d$ as $\hat{\mathcal{L}}_d := (\text{shift}_{l,d,i}, \text{shift}_{r,d,i}, S_{d,i})_{i \le n_d}, \text{shift}_{\text{out},d,i})$.

* Let $\text{Left}_{d,i}$ (resp. $\text{Right}_{d,i}$) denote the multisets of gates that are the left parent (resp. right parent) of a gate in $\mathcal{B}_{d,i}$. Retrieve the pairs $(\ell_u, L_u)$ labeling each $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$ and
compute

$$ (l_i, L_i) := \text{Pack}_E^H(\text{mpk}_{4d-4}, (l_u, L_u)_{u \in \text{Left}_{d,i}}, \text{salt}_{i,d,0}, \text{shift}_{l,d,i}) $$

$$ (l_r, L_r) := \text{Pack}_E^H(\text{mpk}_{4d-4}, (l_u, L_u)_{u \in \text{Right}_{d,i}}, \text{salt}_{i,d,1}, \text{shift}_{r,d,i}). $$

* If $\mathcal{B}_{d,i}$ is a batch of AND gates:

- $(l_{\text{out}}, L_{\text{out}}) := \text{BatchAND}_E^H(\text{mpk}_{4d-3}, \text{mpk}_{4d-2}, (l_i, L_i), (l_r, L_r), \text{salt}_{d,i,2}, S_{d,i})$

- $(l[j], L_j)_{0 \le j \le t-1} := \text{UnpackAND}_E^H(\text{mpk}_{4d-1}, l_{\text{out}}, L_{\text{out}}, \text{salt}_{d,i,3}, \text{shift}_{\text{out},d,i})$

- $(l_u, L_u)_{u \in \mathcal{B}_{d,i}} := (l[j], L_j)_{0 \le j \le |\mathcal{B}_{d,i}|-1}$

* If $\mathcal{L}_d$ is a XOR layer:

- $(l_{\text{out}}, L_{\text{out}}) := \text{BatchXOR}^H(\text{mpk}_{4d-3}, (l_i, L_i), (l_r, L_r), \text{salt}_{d,i,2}, S_{d,i})$

- $(l[j], L_j)_{0 \le i \le t-1} := \text{UnpackXOR}_E^H(\text{mpk}_{4d-1}, l_{\text{out}}, L_{\text{out}}, \text{salt}_{d,i,3}, \text{shift}_{\text{out},d,i})$

- $(l_u, L_u)_{u \in \mathcal{B}_{d,i}} := (l[j], L_j)_{0 \le i \le |\mathcal{B}_{d,i}|-1}$

* Label each $u \in \mathcal{B}_{d,i}$ with $(l_u, L_u)$.

**Output.** Return $\hat{y} := (l_o)_{o \in O(C)}$.

**Algorithm 21:** Evaluator algorithm of the leveled Boolean garbling scheme. We highlight the key changes to Algorithm 3 in red.

**Theorem 30.** Let $\lambda$ be the security parameter and $N := N(\lambda)$ and $m := m(\lambda)$ be integer valued functions as described above. If the $N^m$-power DDH assumption (Definition 4) holds with respect to GrpGen and if $H$ is a TCR hash for the exponential correlation with respect groups generated by GrpGen (Definition 6) then GC is a boolean garbling scheme for polynomial size layered circuits. Moreover, there exists a polynomial $\text{poly}(\cdot)$ such that for any layered circuit $C$ of depth $D$, the garbled circuit $\hat{C} \leftarrow GC.Garble(1^{\lambda}, C)$ satisfies

$$ |\hat{C}| \in O\left(\lambda \cdot \frac{|C|}{\sqrt{\log \lambda}} + \text{poly}(\lambda) \cdot D\right). $$

**Proof sketch.** We first discuss efficiency, then correctness, and finally argue security of the construction.

**Efficiency.** Let $\mathcal{G}$ be the group output by GrpGen on input $1^{\lambda}$. From the description of $\hat{C}$, we have

$$ |\hat{C}| = |C| + 4D \cdot |\text{mpk}| + \sum_{d=1}^{D} |\hat{\mathcal{L}}_d|, $$

where $|\text{mpk}|$ is the size of a PPRF public key and $\hat{\mathcal{L}}_d$ is the shifts sent for the $d$-th layer. The size of $|\text{mpk}|$ is $2N^m+1$ elements of $\mathcal{G}$, which is polynomial in $\lambda$ since $m = O(\sqrt{\log \lambda})$, $c = 2^{\sqrt{\lambda}}$ and $N = O(2c \cdot m \cdot (2^m + 1))$.

The size of each $\hat{\mathcal{L}}_d$ is $O(\lambda \cdot n_d)$ since it contains $n_d$ constant-length tuples of shifts, and each shift is $O(\lambda)$. Thus, there exists a polynomial $\text{poly}'(\cdot)$ such that

$$ \begin{aligned} |\hat{C}| &= |C| + 4D \cdot \text{poly}'(\lambda) + O(\lambda) \frac{|C|}{t} + O(\lambda) \cdot D \cdot t \\ &\le |C| + D \cdot \text{poly}(\lambda) + O(\lambda) \frac{|C|}{\sqrt{\log \lambda}} \end{aligned} $$
where $\text{poly} \in \omega(\lambda \cdot \log \lambda)$.

**Correctness.** The proof of correctness closely follows the one discussed in Section 6.2 since most of the subprocedures remain largely similar. The primary difference is that the garbling maintains a slightly modified invariant where a different PPRF key is used for authenticating the output of gates in each layer. We first discuss the invariant in more detail and then focus on proving the correctness of the BatchAND<sup>H</sup> gadget. The proof of correctness for the rest of the gadgets follows almost immediately from the proofs of the corresponding lemmas in Section 6.

Let $x$ denote an input $C$. For each gate $u$, let $x_u$ denote the bit output by this gate in computation of $C(x)$. Given a batch $\mathcal{B}$ of gates, let $x_{\mathcal{B}} := (x_u)_{u \in \mathcal{B}}$. The garbling scheme then maintains the following invariant for every layer $\mathcal{L}_d$: for each $i \le n_d$, $x_u = k_u \oplus \ell_u$ and $L_u - K_u = \Delta_{4d} \cdot \ell_u \bmod p - 1$, for all $u \in \text{Left}_{d,i} \cup \text{Right}_{d,i}$. As the base case, for each input gate $i$, we have $k_i \oplus \ell_i = x_i$ and $L_i - K_i = \Delta_0 \ell_i \bmod p - 1$ from the description of $e$ and GC.Enc. Now, assuming the invariant holds for a layer $d-1$, we have the following.

* It follows directly from the proof of Lemma 16 that after running the Pack<sup>H</sup> procedures, $k_l + \ell_l = \Phi(\text{pad}_t(x_{\text{Left}_{d,i}}))$, $k_r + \ell_r = \Phi(\text{pad}_t(x_{\text{Right}_{d,i}}))$, $L_l - K_l = \Delta_{4d-3} \cdot \ell_l(N) \bmod p - 1$, and $L_r - K_r = \Delta_{4d-3} \cdot \ell_r(N) \bmod p - 1$. Let $x_l := \Phi(\text{pad}_t(x_{\text{Left}_{d,i}}))$ and $x_r := \Phi(\text{pad}_t(x_{\text{Right}_{d,i}}))$.

* For each batch of AND gates in $\mathcal{L}_d$, it follows from the claim below, that after running the BatchAND<sup>H</sup> procedure $k_{\text{out}} + \ell_{\text{out}} = x_l \cdot x_r$ and $L_{\text{out}} - K_{\text{out}} = \Delta_{4d-1} \cdot \ell_{\text{out}}(N) \bmod p - 1$.

* For each batch of AND gates in $\mathcal{L}_d$, it follows from the proof of Lemma 17 that running the Unpack<sup>H</sup> procedure outputs $(k[i] \oplus \ell[i])_{i \le t-1} = \Psi(x_l \cdot x_r)$ and $L[i] - K[i] = \Delta_{4d} \cdot \ell[i] \bmod p - 1$ for $i = 0$ to $t-1$.

* Similarly, for each batch of XOR gates in $\mathcal{L}_d$, by the proof of Lemma 18 and Lemma 17, it that after running the BatchXOR<sup>H</sup> and Unpack<sup>H</sup> procedures that $(k[i] \oplus \ell[i])_{i \le t-1} = \Phi^{-1}(x_l \oplus x_r)$ and $L[i] - K[i] = \Delta_{4d} \cdot \ell[i] \bmod p - 1$ for $i = 0$ to $t-1$.

It follows that after each AND layer, the gates in $\mathcal{B}_{d,i}$ are labeled with the first $|\mathcal{B}_{d,i}|$ entries of $\Psi(\Phi(\text{pad}_t(x_{\text{Left}_{d,i}})))$. By definition of the RMFE maps (Definition 5), this is value equal to $\text{pad}_t(x_{\text{Left}_{d,i}}) \odot \text{pad}_t(x_{\text{Right}_{d,i}})$, hence its first $|\mathcal{B}_{d,i}|$ entries are exactly the products $x_{u_l} \cdot x_{u_r}$, where $u_l, u_r$ denote the left and right parents of each gate $u \in \mathcal{B}_{d,i}$ respectively. Similarly, after each XOR layer, each gate $u$ of the layer gets labeled with $x_{u_l} \oplus x_{u_r}$. Eventually, after all layers have been computed, it holds that $k_o \oplus \ell_o = x_o$ for each output gate $o$, and we have $(x_o)_{o \in O(C)} = y = C(x)$.

We are left to prove that the invariant indeed holds for the output of BatchAND<sup>H</sup>.

**Claim.** Fix(mpk, msk, mpk', msk', $\Delta_{\text{out}}$, $(k_l, K_l, \ell_l, L_l)$, $(k_r, K_r, \ell_r, L_r)$, salt) where msk := (mpk, $\Delta$, $h_0$) and msk' := (mpk', $\Delta'$, $h'_0$). Assume that for $u \in \{l, r\}$, $L_u - K_u = \Delta \cdot \text{Eval}_N(\ell_u) \bmod p - 1$. Then, denoting

$$x_u := k_u + \ell_u \quad \text{for } u \in \{l, r\} \quad \triangleright \text{over } \mathbb{F}_{2^m}$$

$$((k_{\text{out}}, K_{\text{out}}), S) := \text{BatchAND}_{\text{G}}^{\text{H}}(\text{msk}, \text{msk}', \Delta_{\text{out}}, (k_l, K_l), (k_r, K_r), \text{salt})$$

$$(\ell_{\text{out}}, L_{\text{out}}) := \text{BatchAND}_{\text{E}}^{\text{H}}(\text{mpk}, \text{mpk}', (\ell_l, L_l), (\ell_r, L_r), \text{salt}, S),$$

it holds that

$$k_{\text{out}} + \ell_{\text{out}} = x_l \cdot x_r \quad \triangleright \text{over } \mathbb{F}_{2^m}$$

$$L_{\text{out}} - K_{\text{out}} = \Delta_{\text{out}} \cdot \text{Eval}_N(\ell_{\text{out}}) \bmod p - 1$$
*Proof.* Since the computation of $\ell_{out}$ and $k_{out}$ in Algorithms 18 and 19 remains identical to that in Algorithms 11 and 12, it follows from the proof of Lemma 19 that

$$ \ell_{out} + k_{out} = x_l \cdot x_r. \quad \triangleright \text{over } \mathbb{F}_{2^m} = \mathbb{F}_2[X]/P(X) $$

Similarly, we have

$$ \alpha_E - \alpha_G = \ell_r(N) \cdot (\Delta' k'_l(N)) $$

$$ \beta_E - \beta_G = \ell_l(N) \cdot (\Delta' k'_r(N)). $$

Now, since the conditions of Lemma 11 are satisfied, we have

$$ L'_l - K'_l = \Delta' \cdot \ell_l(N), $$

which in turn implies that

$$ \gamma_E - \gamma_G = K'_l \cdot \ell_r(N). $$

Thus, we have

$$
\begin{align*}
\tilde{L}_{\text{out}} - \tilde{K}_{\text{out}} &= \alpha_E + \beta_E - \gamma_E + L'_l \ell_r(N) - (\alpha_G + \beta_G - \gamma_G + \Delta'(\tilde{a}_G + \tilde{b}_G)) \\
&= (\alpha_E - \alpha_G) + (\beta_E - \beta_G) - (\gamma_E - \gamma_G) + \Delta(\tilde{a}_G + \tilde{b}_G) + L'_l \ell_r(N) \\
&= \Delta' \cdot (\ell_r(N) \cdot k'_l(N) + \ell_l(N) \cdot k'_r(N)) - \ell_r(N) \cdot K'_l \\
&\quad + \Delta(\tilde{a}_E - \ell_r(N) \cdot k'_l(N) + \tilde{b}_E - \ell_l(N) \cdot k'_r(N)) + L'_l \ell_r(N) \\
&= \Delta' \cdot (\tilde{a}_E + \tilde{b}_E) + \ell_r(N) \cdot (L'_l - K'_l) \\
&= \Delta' \cdot (\tilde{a}_E + \tilde{b}_E + \ell_r(N) \cdot \ell_l(N)) \quad \triangleright L'_l - K'_l = \Delta' \cdot \ell_l(N) \\
&= \Delta' \cdot \tilde{\ell}_{\text{out}},
\end{align*}
$$

Consequently, apply Lemma 13, we have

$$
\begin{align*}
L_{\text{out}} - K_{\text{out}} &= \Delta_{\text{out}} \cdot \operatorname{Mod}_N(\tilde{\ell}_{\text{out}}, 2, P) \bmod p - 1 \\
&= \Delta_{\text{out}} \cdot \tilde{\ell}_{\text{out}}(N) \bmod p - 1.
\end{align*}
$$

□

**Security.** The proof of security closely follows the one discussed in Section 7 and we only highlight the differences. In more detail, Hybrid$_1$ remains identical, while in Hybrid$_2$ we modify the simulator SimBatchAnd$^{H,O}$ to simulate $L'_l$ using SimVtO and compute $\tilde{L}_{\text{out}} := \alpha_E + \beta_E - \gamma_E + L'_l \ell_r(N)$. In the simulator for each gadget, we modify use the modified variant of SimBatchfAuth$^{H,O}$ as discussed in Remark 2. Using a similar argument as the one used in Section 7, it follows that Hybrid$_1$ is identical to Hybrid$_2$. In Hybrid$_3$, we replace the oracle $\mathcal{O}$ with a random oracle $\mathcal{R}$. Observe that calls by SimBatchfAuth$^{H,O}$ to $\mathcal{O}$, under the same PPRF public key mpk, can be batched and can thus be computed using the leveled TCCR hash of Definition 8. This is because simulating the shift and evaluator's output share for Pack$^H$ only requires the evaluator's shares computed as the output of the previous layer. Similarly, simulating BatchXOR$^H$ and Unpack$^H$ only requires the evaluator's share computing using Pack$^H$, and BatchAND$^H$ or BatchXOR$^H$ in the current layer. Finally, it is easy to see that this is true for BatchAND$^H$ too since shift$_\alpha$, shift$_\beta$, shift$_K'$
and $\alpha_E, \beta_E$, and $L'_i$ can be simulated in parallel. It then follows from Theorem 7 that $\text{Hybrid}_3$ is indistinguishable from $\text{Hybrid}_2$. The proof then proceeds similarly to that in Section 7.1 where in $\text{Hybrid}_4$, SimVtO and SimBatchfAuth$^{\text{H.O}}$ are modified to not require the garbler's shares and subsequently, in $\text{Hybrid}_5$, we rely on the correctness of the scheme to set $d := (\ell_o \oplus y_o)_{o \in O(C)}$. It follows that the garbling scheme is secure. ■

The following corollary immediately follows from Theorem 30 and the definition of rate of a boolean garbling scheme.

**Corollary 31.** Let $\lambda$ be the security parameter. If for every integer-valued polynomial $B := B(\lambda)$ the B-power DDH holds with respect to a group generator and there exists a TCR hash for the exponential correlation with respect to this group generator, then there exists a boolean garbling scheme for polynomial size layered circuits with rate $\frac{\lambda}{\sqrt{\log \lambda}}$.

## References

[AIK11] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. How to garble arithmetic circuits. In Rafail Ostrovsky, editor, *52nd Annual Symposium on Foundations of Computer Science*, pages 120–129, Palm Springs, CA, USA, October 22–25, 2011. IEEE Computer Society Press.

[AMN$^{+}$18] Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa. Constrained PRFs for $NC^1$ in traditional groups. In Hovav Shacham and Alexandra Boldyreva, editors, *Advances in Cryptology – CRYPTO 2018, Part II*, volume 10992 of *Lecture Notes in Computer Science*, pages 543–574, Santa Barbara, CA, USA, August 19–23, 2018.

[BCM$^{+}$24] Dung Bui, Geoffroy Couteau, Pierre Meyer, Alain Passelègue, and Mahshid Riahinia. Fast public-key silent OT and more from constrained Naor-Reingold. In Marc Joye and Gregor Leander, editors, *Advances in Cryptology – EUROCRYPT 2024, Part VI*, volume 14656 of *Lecture Notes in Computer Science*, pages 88–118, Zurich, Switzerland, May 26–30, 2024.

[BGI16] Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the circuit size barrier for secure computation under DDH. In Matthew Robshaw and Jonathan Katz, editors, *Advances in Cryptology – CRYPTO 2016, Part I*, volume 9814 of *Lecture Notes in Computer Science*, pages 509–539, Santa Barbara, CA, USA, August 14–18, 2016.

[BGL$^{+}$15] Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. Succinct randomized encodings and their applications. In Rocco A. Servedio and Ronitt Rubinfeld, editors, *47th Annual ACM Symposium on Theory of Computing*, pages 439–448, Portland, OR, USA, June 14–17, 2015. ACM Press.

[BHR12] Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, *ACM CCS 2012: 19th Conference on Computer and Communications Security*, pages 784–796, Raleigh, NC, USA, October 16–18, 2012. ACM Press.

[BLLL23] Marshall Ball, Hanjun Li, Huijia Lin, and Tianren Liu. New ways to garble arithmetic circuits. In Carmit Hazay and Martijn Stam, editors, *Advances in Cryptology – EUROCRYPT 2023, Part II*, volume 14005 of *Lecture Notes in Computer Science*, pages 3–34, Lyon, France, April 23–27, 2023.
[CCXY18] Ignacio Cascudo, Ronald Cramer, Chaoping Xing, and Chen Yuan. Amortized complexity of information-theoretically secure MPC revisited. In Hovav Shacham and Alexandra Boldyreva, editors, *Advances in Cryptology – CRYPTO 2018, Part III*, volume 10993 of *Lecture Notes in Computer Science*, pages 395–426, Santa Barbara, CA, USA, August 19–23, 2018.

[CG20] Ignacio Cascudo and Jaron Skovsted Gundersen. A secret-sharing based MPC protocol for boolean circuits with good amortized complexity. In Rafael Pass and Krzysztof Pietrzak, editors, *TCC 2020: 18th Theory of Cryptography Conference, Part II*, volume 12551 of *Lecture Notes in Computer Science*, pages 652–682, Durham, NC, USA, November 16–19, 2020.

[CHHK25] Geoffroy Couteau, Carmit Hazay, Aditya Hegde, and Naman Kumar. Breaking the $1/\lambda$-rate barrier for arithmetic garbling. In *Advances in Cryptology – EUROCRYPT 2025*, 2025.

[CKKZ12] Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, and Hong-Sheng Zhou. On the security of the “free-XOR” technique. In Ronald Cramer, editor, *TCC 2012: 9th Theory of Cryptography Conference*, volume 7194 of *Lecture Notes in Computer Science*, pages 39–53, Taormina, Sicily, Italy, March 19–21, 2012.

[CNs07] Jan Camenisch, Gregory Neven, and abhi shelat. Simulatable adaptive oblivious transfer. In Moni Naor, editor, *Advances in Cryptology – EUROCRYPT 2007*, volume 4515 of *Lecture Notes in Computer Science*, pages 573–590, Barcelona, Spain, May 20–24, 2007.

[Cou19] Geoffroy Couteau. A note on the communication complexity of multiparty computation in the correlated randomness model. In Yuval Ishai and Vincent Rijmen, editors, *Advances in Cryptology – EUROCRYPT 2019, Part II*, volume 11477 of *Lecture Notes in Computer Science*, pages 473–503, Darmstadt, Germany, May 19–23, 2019.

[DGM23] Nico Döttling, Phillip Gajland, and Giulio Malavolta. Laconic function evaluation for Turing machines. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part II*, volume 13941 of *Lecture Notes in Computer Science*, pages 606–634, Atlanta, GA, USA, May 7–10, 2023.

[DI05] Ivan Damgård and Yuval Ishai. Constant-round multiparty computation using a black-box pseudorandom generator. In Victor Shoup, editor, *Advances in Cryptology – CRYPTO 2005*, volume 3621 of *Lecture Notes in Computer Science*, pages 378–394, Santa Barbara, CA, USA, August 14–18, 2005.

[DIK10] Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In Henri Gilbert, editor, *Advances in Cryptology – EUROCRYPT 2010*, volume 6110 of *Lecture Notes in Computer Science*, pages 445–465, French Riviera, May 30 – June 3, 2010.

[EHL$^+$23] Daniel Escudero, Cheng Hong, Hongqing Liu, Chaoping Xing, and Chen Yuan. Degree-D reverse multiplication-friendly embeddings: Constructions and applications. In Jian Guo and Ron Steinfeld, editors, *Advances in Cryptology – ASIACRYPT 2023, Part I*, volume 14438 of *Lecture Notes in Computer Science*, pages 106–138, Guangzhou, China, December 4–8, 2023.

[GJM03] Philippe Golle, Stanislaw Jarecki, and Ilya Mironov. Cryptographic primitives enforcing communication and storage complexity. In Matt Blaze, editor, *FC 2002: 6th International Conference*