Breaking the

1/λ

-Rate Barrier for Arithmetic Garbling

Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar

► To cite this version:

Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar. Breaking the

1/λ

-Rate Barrier for Arithmetic Garbling. EUROCRYPT 2025, May 2025, Madrid, Spain. pp.182-213, 10.1007/978-3-031-91095-1_7 . hal-05376870

HAL Id: hal-05376870

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

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
Breaking the 1/λ-Rate Barrier
for Arithmetic Garbling

Geoffroy Couteau¹, Carmit Hazay², Aditya Hegde³*, and Naman Kumar⁴

1 Université Paris Cité, CNRS, IRIF couteau@irif.fr

² Bar-Ilan University carmit.hazay@biu.ac.il

³ Johns Hopkins University ahegde@cs.jhu.edu

⁴ Oregon State University kumarnam@oregonstate.edu

**Abstract.** Garbled circuits, introduced in the seminal work of Yao (FOCS, 1986), have received considerable attention in the boolean setting due to their efficiency and application to round-efficient secure computation. In contrast, arithmetic garbling schemes have received much less scrutiny. The main efficiency measure of garbling schemes is their rate, defined as the bit size of each gate's output divided by the size of the (amortized) garbled gate. Despite recent progress, state-of-the-art garbling schemes for arithmetic circuits suffer from important limitations: all existing schemes are either restricted to B-bounded integer arithmetic circuits (a computational model where the arithmetic is performed over $\mathbb{Z}$ and correctness is only guaranteed if no intermediate computation exceeds the bound $B$) and achieve constant rate only for very large bounds $B = 2^{\Omega(\lambda^3)}$, or have a rate at most $O(1/\lambda)$ otherwise, where $\lambda$ denotes a security parameter. In this work, we improve this state of affairs in both settings.

- As our main contribution, we introduce the first arithmetic garbling scheme over modular rings $\mathbb{Z}_B$ with rate $O(\log \lambda/\lambda)$, breaking for the first time the 1/λ-rate barrier for modular arithmetic garbling. Our construction relies on the power-DDH assumption.

- As a secondary contribution, we introduce a new arithmetic garbling scheme for B-bounded integer arithmetic that achieves a constant rate for bounds $B$ as low as $2^{O(\lambda)}$. Our construction relies on a new non-standard KDM-security assumption on Paillier encryption with small exponents.

# 1 Introduction

Garbled circuits, first introduced by Yao in the 1980s [Yao86], have become a fundamental and versatile tool in modern cryptography. Since their inception, a substantial body of work has expanded on Yao's construction, offering various optimizations, abstractions, and extensions. In addition to being one of the fundamental paradigms for achieving constant-round secure computation [Yao86, BMR90, FKN94, IK00, LP09], garbled circuits have also found applications in many other cryptographic areas. Their popularity stems from the ability to encode a function $f$, represented as a boolean circuit, in such a way that evaluating the encoded function on some input $x$ reveals no information other than $f(x)$. Despite all the efforts to improve these constructions, the current state of the art of garbled circuits, based solely on symmetric-key assumptions, implies a multiplicative factor of $O(\lambda)$ in the encoded circuit size. Namely, the rate between the original circuit size $C$ and the garbled circuit size $\hat{C}$ is $1/O(\lambda)$, where $\lambda$ is the security parameter. This implies limited scalability as the size of the circuit increases.

Another restriction of boolean circuits is their limited suitability for capturing a broader class of function representations, such as arithmetic circuits, when the computation is performed over integers, real numbers, or rings. Arithmetic circuits are often used to represent computations over real-world data, such as financial transactions, machine learning, or privacy-preserving protocols for statistics and data mining. For such applications, applying naive boolean garbling techniques to the arithmetic setting proves too inefficient. In particular, while traditional garbled circuits are better suited to boolean operations such as bitwise comparison, many real-world computations are more naturally expressed using arithmetic operations performed over larger domains.

Compared to the vast literature on garbled circuits for boolean circuits, not much progress has been made in the field of arithmetic garbling. This is partly because the traditional techniques do not scale with the underlying ring. Consequently, arithmetic garbling requires new approaches that

<footnote>* This work was done in part while the author was at IRIF.</footnote>
get beyond the bit representation of the circuit wires. The arithmetic computation model can be
captured by two different representations: (1) *Bounded integer computations*. This computational
model considers circuits defined over the integer ring $\mathbb{Z}$ with addition and multiplication gates and
a predefined bound $B$, where *any* wire value falls within $[-B, B]$. (2) *Modular arithmetic*. Here the
computations are performed over a finite ring $\mathcal{R} = \mathbb{Z}_p$ (where $p$ is not necessarily a prime number).

A popular approach to arithmetic garbling in the bounded integer setting reduces the problem to a variant of Yao's original garbling scheme, but this typically requires bit decomposition [BGG+14, BMR16], meaning that arithmetic operations need to be broken down into individual bit-wise operations, which increases the rate. An alternative construction was proposed by Applebaum et al. [AIK11], offering a way to garble computations over bounded integers directly without bit decomposition. This method allows for computations over integers $\mathbb{Z}$ within a bounded domain $[-B, B]$, where $B$ can be large, possibly exponential, and the security of this scheme is based on the Learning With Errors (LWE) assumption. However, their rate is still proportional to the security parameter for the LWE assumption.

Building on the work of Applebaum et al. [AIK11], Ball et al. [BLLL23] introduced an instantiation of the key expansion gadget introduced in [AIK11] using a variant of Paillier's key and message linearly homomorphic encryption scheme [Pai99, DJN10]. This approach achieves the first constant multiplicative communication overhead relative to the bit-length representation of the computed arithmetic circuit (when given in the clear). In more detail, Ball et al. introduced two variants of arithmetic garbling schemes under the Decisional Composite Residuosity (DCR) assumption with a rate of 1/36 and under the short exponent DCR assumption with a rate of 1/24. In both cases, the bound $B$ is of the order of $B \approx 2^{4000}$. Both papers further study the modular arithmetic setting with $O(1/\lambda)$ rate.

A recent work by Meyer et al. [MORS24] improves on the concrete constants of [BLLL23] by incorporating a different technique for computing the multiplication gates using Homomorphic Secret Sharing (HSS). This approach enables to achieve rate 1/2 assuming DCR and rate-1 garbling by additionally assuming key-dependent message (KDM) security. However, these approaches are fundamentally limited to the model of $B$-bounded integer computation, and furthermore, their achieved bound $B$ is still large on the order of $N^2 \approx 2^{\Omega(\lambda^3)}$ due to incorporating the same cryptographic building blocks of Paillier. In another concurrent work [Hea24], Heath proposed a garbling scheme based only on symmetric-key assumptions that garbles a circuit $C$ over $\mathbb{Z}_m$ for an arbitrary $m$ with rate $O(1/\lambda)$.

Two important questions are at hand in light of this state of affairs. (1) Can we surpass the $1/\lambda$ barrier for modular arithmetic garbling? (2) To what extent can we reduce the bound $B$ while maintaining a constant rate?

## 1.1 Our Contributions

**A Rate-ω(1/λ) Arithmetic Garbling Scheme.** We construct the first arithmetic garbling scheme that provides an asymptotic improvement in rate over 1/λ for modular arithmetic computation. The security of our scheme is based on a mild variant of the well-known Power-DDH Assumption [GJM03, CNs07]. Our scheme forms part of a unified approach towards arithmetic garbling, which we introduce as the ‘VOLE-to-OLE’ framework that interprets the (both arithmetic as well as boolean) garbling of a gate as a single-message conversion from a VOLE (Vector Oblivious Linear Evaluation) correlation to an OLE (Oblivious Linear Evaluation). Our viewpoint unifies several recent developments in garbling ([ZRE15, HKN24, Hea24, MORS24]) as an instantiation of the same general framework. While previous approaches have achieved better (even constant) rates for schemes based on $B$-bounded integer computation, all known schemes set the value of $B$ to be *exponential* in the size of the security parameter. Our scheme is the first to improve the rate over $1/\lambda$ for garbling over $\mathbb{Z}_B$, for small, polynomial-size domains, from a standard cryptographic assumption.

**Theorem 1 (Modular Garbling from Power-DDH, Informal).** Let $\lambda$ be a security parameter, $B$ be a polynomial-size modulus $B \in \text{poly}(\lambda)$, and $c$ be any arbitrarily slow growing function $\omega(1)$. Set $B' = B^2 + c \cdot \lambda \cdot B^3$. Then, assuming the $B'$-power-DDH assumption and the existence of tweakable correlation-robust hash functions (a property of hash functions that holds unconditionally in the random oracle model), there exists an arithmetic garbling scheme for $\mathbb{P}/\text{poly}$ that supports $\mathbb{Z}_B$-modular arithmetic computation, has statistical correctness failure probability $O(1/2^c)$, and achieves a rate $O(\log B/\lambda)$.
**A New PPRF from Power-DDH.** Puncturable Pseudorandom Functions are primitives that support a master key $sk$ and a punctured key $sk_x$ such that an underlying PRF can be evaluated at all points in the domain with $sk$ and on all but one point, $x$, with the punctured key $sk_x$. In this work, we make use of a PPRF that features multiple attractive properties: the key size is small, consisting of only a single element of $\mathbb{Z}_p^*$, and it supports *reusable setup*, i.e., the same setup, that generates a master secret key and a (possibly large) master public key, can be reused for multiple key generations, which is advantageous in the amortized setting (i.e., although the master public key can be large, its size overhead can be amortized over many instances). We use this PPRF to realize our VOLE-to-OLE framework, in which it features the additional advantage that provided a VOLE correlation in the form of setup, the punctured key $sk_x$ can be derived *at runtime without interaction*. The security of our PPRF relies on the standard Power-DDH assumption (plus the existence of a suitable correlation-robust hash function, in the reusable-setup setting), and we believe the construction is of independent interest.

**Improved Constant-Rate Garbling for Small Integers.** Our third contribution is a concrete improvement over the HSS-based garbling scheme of [MORS24], which provides a constant rate for an improved class of integers. In particular, our scheme provides constant-rate arithmetic garbling for $B$-bounded integers where $B$ can be as small as $2^{2^\lambda}$. We instantiate our scheme with Homomorphic Secret Sharing from the Paillier-ElGamal cryptosystem ([OSY21]) with short exponent, a scheme believed to be secure under the DCR and the SEI assumptions. We base the security of our garbling scheme under a strong variant of circular security for the underlying Paillier-ElGamal cryptosystem combined with a computational one-time encryption scheme we term *circular security of the hybrid*.

**Theorem 2 (Small-integer Arithmetic Garbling from Circular Security of Paillier-ElGamal, Informal).** Let $\lambda$ be a security parameter. Then, assuming (a variant of) circular security of Paillier-ElGamal with small exponent and the existence of a pseudorandom function in $NC^1$, for every $B < 2^{O(\lambda)}$ there exists an arithmetic garbling scheme for $P/poly$ that supports $B$-bounded integer computation and achieves rate $1/2 - \epsilon$ for arbitrary constant $\epsilon$.

**Organization.** In Section 2, we provide a detailed overview of our main contribution. We introduce our new PPRF in Section 3 and our modular arithmetic garbling scheme in Section 4. Being quite different in nature, our secondary contribution is deferred to the Appendix. In Appendix A and Appendix B, we provide additional preliminaries on arithmetic garbling and homomorphic secret sharing. Appendix C covers our rate-1/2 arithmetic garbling scheme for $B$-bounded arithmetic with $B = 2^{O(\lambda)}$. We give a detailed technical overview in Appendix C.1 and the formal construction in Appendix C.2.

**Follow-up works.** In a follow-up work [CHHK25], the same authors uses the techniques introduced in the power-DDH-based arithmetic garbling scheme to construct a Boolean garbling scheme with $\lambda/\sqrt{\log \lambda}$ bits per gate, beating the $O(\lambda)$-bit per gate barrier without resorting to heavy-hammer cryptography, and making only a black-box use of cryptography.

In other subsequent works, Meyer, Orlandi, Roy, and Scholl [MORS25] and Ishai, Li, and Lin [ILL25] introduced the first sublinear garbling scheme for Boolean circuits from DCR. Their scheme essentially subsumes our second contribution, and is incomparable to our first contribution and to [CHHK25] (in particular and unlike these works, both our work and the follow-up make a black-box use of cryptography).

# 2 Technical Overview: Modular Arithmetic Garbling from Power-DDH

We start with an overview of our construction of a modular arithmetic garbling scheme with rate $\omega(1/\lambda)$. Our starting point is a natural view on a common template for (boolean and arithmetic) garbling as a non-interactive procedure from vector oblivious linear evaluation (VOLE) to oblivious linear evaluation (OLE). We elaborate below.

## 2.1 Preliminaries on Power-DDH

We let $GrpGen(1^\lambda)$ denote a deterministic algorithm that, on inputs the security parameter $\lambda$ in unary, outputs a tuple $(G, p, g)$ where $G$ is (the description of) a cyclic group of order $p$, $p$ is a prime of
length $2\lambda$ bits, and $g$ is a generator of $\mathbb{G}$. Given an integer $n$, we write $[\pm n]$ for the set $\{-n, \dots, n\}$ and $[n]$ for the set $\{0, \dots, n\}$.

**Definition 3 (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:

$$ \begin{aligned} \mathcal{D}_0 &:= \left\{ (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)]} \right\} \\ \mathcal{D}_1 &:= \left\{ (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)]} \right\}. \end{aligned} $$

The traditional formulation of the power-DDH assumption [GJM03, CNs07] states that given $(h, h^{\alpha}, \dots, h^{\alpha^{B-1}})$, one cannot distinguish $h^{\alpha^B}$ from random. Other common variants [AMN$^{+18}$], often called power-DDH as well (or DH-inversion), ask that it is hard to distinguish $h^{1/\alpha}$ from random given $(h, h^{\alpha}, \dots, h^{\alpha^{B-1}})$. In this work, we use yet another slight variant, where we ask that given $(h^{\alpha^{-B}}, \dots, h^{\alpha^{-1}}, h^{\alpha}, \dots, h^{\alpha^B})$, it should be hard to distinguish the missing “center term” $h$ from random. All variants can be shown to be equivalent, up to a factor-2 loss in the bound $B$. Before we sketch the simple proof, we introduce the “all-random” power-DDH variant below:

**Definition 4 (All-random B-power-DDH assumption).** Let $B = B(\cdot)$ be a polynomial. The all-random 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:

$$ \begin{aligned} \mathcal{D}_0^{\text{ar}} &:= \left\{ (g_i)_{i \in [B(\lambda)]} : \alpha \leftarrow \mathbb{Z}_p^*, h \leftarrow \mathbb{G}, (g_i)_{i \in [B(\lambda)]} \leftarrow (h^{\alpha^i})_{i \in [B(\lambda)]} \right\} \\ \mathcal{D}_1^{\text{ar}} &:= \left\{ (g_i)_{i \in [\pm B(\lambda)]} : (g_i)_{i \in [B(\lambda)]^*} \leftarrow \mathbb{G}^{B(\lambda)} \right\}. \end{aligned} $$

**Theorem 5.** If the B-power-DDH assumption holds, then the all-random B-power-DDH assumption holds.

Note that there is a slight loss in the parameters in Theorem 5 because the B-power-DDH assumption involves $2B + 1$ exponents, while the all-random B-power-DDH assumption only involves $B + 1$ exponents. Before we proceed with the proof, we note that the all-random B-power-DDH assumption implies all known flavors of power-DDH, including those from [GJM03, CNs07] and [AMN$^{+18}$]. Given that all variants are equivalent, in this work, we simply call our variant “power-DDH”.

*Proof.* We proceed through a sequence of hybrid distributions, moving gradually from $\mathcal{D}_0^{\text{ar}}$ to $\mathcal{D}_1^{\text{ar}}$. We start with the distribution $\mathcal{D}_0^{\text{ar}}$ (“Hybrid$_{-1}$).

**Hybrid$_0$.** We modify $\mathcal{D}_0^{\text{ar}}$ by replacing $g_0 \leftarrow h^{\alpha^0}$ with $g_0 \leftarrow \mathbb{G}$, leaving everything else the same. We denote $\mathcal{D}_{0,0}^{\text{ar}}$ the new distribution.

**Hybrid$_1$.** We modify $\mathcal{D}_{0,0}^{\text{ar}}$ by replacing $g_1 \leftarrow h^{\alpha^1}$ with $g_1 \leftarrow \mathbb{G}$, leaving everything else the same. We denote $\mathcal{D}_{0,1}^{\text{ar}}$ the new distribution.

**Hybrid$_{i+1}$.** We modify $\mathcal{D}_{0,i}^{\text{ar}}$ by replacing $g_{i+1} \leftarrow h^{\alpha^{i+1}}$ with $g_{i+1} \leftarrow \mathbb{G}$, leaving everything else the same.

**Hybrid$_B$.** This is the distribution $\mathcal{D}_{0,B}^{\text{ar}} = \mathcal{D}_1^{\text{ar}}$.

*Claim.* Under the B-power-DDH assumption, Hybrid$_{-1}$ and Hybrid$_0$ are indistinguishable.

*Proof.* The reduction receives a challenge $(g_i)_{i \in \pm [B(\lambda)-1]}$ from either $\mathcal{D}_0$ or $\mathcal{D}_1$. It sets $(g'_0, \dots, g'_B) \leftarrow (g_0, \dots, g_B)$ and runs the distinguisher on $(g'_i)_{i \in [B(\lambda)]}$. Observe that if the challenge comes from $\mathcal{D}_0$, $(g'_i)_{i \in [B(\lambda)]}$ is distributed as in Hybrid$_0$, while if the challenges comes from $\mathcal{D}_1$, $(g_i)_{i \in [B(\lambda)]}$ is distributed as in Hybrid$_1$. $\blacksquare$

*Claim.* Under the $(B - i - 1)$-power-DDH assumption, Hybrid$_i$ and Hybrid$_{i+1}$ are indistinguishable.

*Proof.* The reduction receives a challenge $(g_j)_{j \in \pm [B(\lambda)-i-1]}$ from either $\mathcal{D}_0$ or $\mathcal{D}_1$. It first samples $(g'_0, \dots, g'_i) \leftarrow \mathbb{G}^{i+1}$ and sets $(g'_{i+1}, \dots, g'_B) \leftarrow (g_0, \dots, g_{B-i-1})$. Then, it runs the distinguisher on $(g'_j)_{j \in [B(\lambda)]}$. Observe that if the challenge comes from $\mathcal{D}_0$, $(g'_j)_{j \in [B(\lambda)]}$ is distributed as in Hybrid$_i$, while if the challenges comes from $\mathcal{D}_1$, $(g_j)_{j \in [B(\lambda)]}$ is distributed as in Hybrid$_{i+1}$. $\blacksquare$

Eventually, we observe that the $(B - i - 1)$-power-DDH assumptions are all implied by the B-power-DDH assumption for $i = -1$ to $B - 1$. This concludes the proof. $\blacksquare$
## 2.2 A Template for Arithmetic Garbling

We start by outlining a template used, implicitly or explicitly, in various recent works [ZRE15, HKN24, Hea24, MORS24]. For each wire $x$, the garbler generates a key $K_x$ associated with the label $L_x = \Delta x + K_x$ where $\Delta$ is a (randomly generated) global parameter known only to the garbler. Here, $(L_x, K_x)$ can also be interpreted as a secret sharing $(\Delta x)$; similarly, the garbler can also generate $(l_x, k_x)$ to be a sharing of $x$, and the parties maintain an invariant sharing $(\langle x \rangle, \langle \Delta \cdot x \rangle)$ with the garbler’s share being $(l_x, L_x)$, and the evaluator’s share being $(k_x, K_x)$ for each wire $x$.

With this invariant in place, the garbled circuit evaluation procedure reduces to computing successive output wire values $(\langle g(x, y) \rangle, \langle \Delta \cdot g(x, y) \rangle)$. For additive gates, this follows for free by the additively homomorphic property of secret sharing – the garbler and the evaluator can compute their shares as $(\langle x + y \rangle, \langle \Delta \cdot (x + y) \rangle) = (\langle x \rangle + \langle y \rangle, \langle \Delta \cdot x \rangle + \langle \Delta \cdot y \rangle)$. For a multiplication gate consider the identities

$$z = x \cdot y = \langle x \rangle_E \cdot \langle y \rangle_E + \langle x \rangle_E \cdot \langle y \rangle_G + \langle y \rangle_E \cdot \langle x \rangle_G + \langle x \rangle_G \cdot \langle y \rangle_G \quad (1)$$

$$\Delta \cdot z = \Delta x \cdot y = \langle \Delta x \rangle_E \cdot \langle y \rangle_E + \langle \Delta x \rangle_E \cdot \langle y \rangle_G + \langle y \rangle_E \cdot \langle \Delta x \rangle_G + \langle \Delta x \rangle_G \cdot \langle y \rangle_G \quad (2)$$

The first terms of both these identities can be computed without interaction by the evaluator, while the garbler can calculate the last terms without interaction. Note, however, that the remaining ‘cross’ terms are secret-dependent – computing them requires garbling material.

**The case of boolean circuits.** The work of [ZRE15] was the first to use this identity explicitly to design a (boolean) garbling scheme. We sketch the main intuition; we assume that $x, y$ are bits, and we focus for now on the cross term $\langle x \rangle_G \cdot \langle y \rangle_E$. Recall that the parties hold shares $\langle \Delta y \rangle$. Observe that $\langle \Delta y \rangle_G - \Delta \cdot \langle y \rangle_G$ (which the garbler can compute locally) and $\langle \Delta y \rangle_E$ form shares of $\Delta y - \Delta \cdot \langle y \rangle_G = \Delta \cdot \langle y \rangle_E$. Abstracting out, the garbler and the evaluator therefore hold shares $(\langle \Delta y \rangle_E \langle y \rangle_E, \langle \Delta y \rangle_E \langle y \rangle_E)$ of $\Delta y \rangle_E$.<fnref n="5" /> Note that the evaluator share $\langle \Delta y \rangle_E$ satisfies $\langle \Delta y \rangle_E = -\langle \Delta y \rangle_E$ if $\langle y \rangle_E = 0$, and $\langle \Delta y \rangle_E = \Delta - \langle \Delta y \rangle_E$ if $\langle y \rangle_E = 1$. Then, the parties proceed as follows:

**Garbler:** pick a random bit $r_G$ and add $(h_0, h_1) := (H(-\langle \Delta y \rangle_E \rangle_G) - r_G, H(\Delta - \langle \Delta y \rangle_E \rangle_G) + (\langle x \rangle_G - r_G))$ to the garbling of the gate. Define $G$’s share of $\langle x \rangle_G \cdot \langle y \rangle_E$ to be $r_G$.

**Evaluator:** given the gate garbling $(h_0, h_1)$, compute $r_E := h_{\langle y \rangle_E} - H(\langle \Delta y \rangle_E)$ and output $r_E$.

Observe that $h_{\langle y \rangle_E} = H(\langle \Delta y \rangle_E - \langle \Delta y \rangle_E \rangle_G) + (\langle y \rangle_E \langle x \rangle_G - r_G) = H(\langle \Delta y \rangle_E \rangle_E) + (\langle y \rangle_E \langle x \rangle_G - r_G)$ by construction, hence $r_G$ and $r_E$ form additive shares of $\langle y \rangle_E \langle x \rangle_G$: this takes care of the first cross term. A similar strategy is used to handle the cross terms $\langle y \rangle_G \langle x \rangle_E$ and $\langle y \rangle_E \langle \Delta x \rangle_G$ (where each time we use the fact that a bit known to $E$ “selects” between two possible strings known to $G$). Eventually, the remaining cross term $\langle \Delta x \rangle_E \langle y \rangle_G$ is slightly more tedious, but we can rewrite it as

$$\langle \Delta x \rangle_E \langle y \rangle_G = (\Delta x - \langle \Delta x \rangle_G) \cdot \langle y \rangle_G = (\Delta (\langle x \rangle_G + \langle x \rangle_E) - \langle \Delta x \rangle_G) \cdot \langle y \rangle_G \\ = (\Delta \langle x \rangle_G - \langle \Delta x \rangle_G) \cdot \langle y \rangle_G + \langle x \rangle_E \cdot (\Delta \langle y \rangle_G),$$

where in the last term, the leftmost part can be computed locally by $G$, and the rightmost part is again the product of a bit known to $E$ and a value known to $G$, hence can be handled via the same approach as before.

Security of the garbling scheme hinges upon the fact that $H(\Delta - \langle \Delta y \rangle_E)$ looks random to $E$, which holds assuming a suitable notion of circular correlation robustness for $H$. We note that in [ZRE15], $r_G$ was chosen so that $h_0 = 0$ to avoid having to send it, reducing the size of the garbled gate to $2\lambda + 2$ bits (where $\lambda$ is such that $\Delta \in \mathbb{F}_{2^\lambda}$), but we omit this row-reduction optimization here for simplicity (our focus is on asymptotic security and we do not optimize the constants).

**The VOLE-to-OLE viewpoint.** From a bird’s-eye view, the approach of [ZRE15] consists of applying the celebrated IKNP protocol [IKNP03] to convert many pairs of “$\Delta$-correlated oblivious transfers” (where the sender’s inputs are pairs of strings whose difference is always $\Delta$) into truly random oblivious transfers (OTs) via a correlation-robust hash function, and then “derandomizing” these OTs (by adding the derandomization messages to the garbled gate) to obtain the target shares of the cross terms.

<footnote n="5">⁵ Over $\mathbb{F}_2$, addition and subtraction coincide, but we keep the distinction to facilitate the discussion when we generalize later to other rings.</footnote>
This view suggests an immediate generalization to more general arithmetic structures (rings or fields). Fix a ring $\mathcal{R}$. The garbler and the evaluator will want to compute shares of terms of the form $u \cdot v$, where $u \in \mathcal{R}$ is known to the evaluator, and $v$ is known to the garbler. The parties initially hold shares of $\Delta \cdot u$ (where $\Delta$ is a global constant known to the garbler), and the computation should proceed via a single message from $G$ to $E$ (this message will be appended to the garbling of the gate). In secure computation, computing shares of $u \cdot v$ is often called executing an OLE (for Oblivious Linear Evaluation: the evaluator should obliviously obtain $f(u) = u \cdot v - r_G$ where $r_G$ is the garbler's share and $f$ is an affine function), while shares of $\Delta u$ for many $u$'s but a single global $\Delta$ (known to $G$) are generally called a VOLE (for vector-OLE: denoting $\mathbf{u}$ the vector of all the $u$'s, and $\mathbf{r}_E$ the vector of all the evaluator's shares of the $\Delta u$'s, the garbler holds $g(\Delta) = \Delta \cdot \mathbf{u} - \mathbf{r}_E$, which is an OLE between two vectors held by $E$). Using this terminology, we want to achieve the following: the garbler and the evaluator hold a single large VOLE (where the garbler plays the role of the receiver) and want to convert it into a large number of OLEs (where the roles are swapped) using a single $G$-to-$E$ message.

## 2.3 Instantiating the Non-Interactive VOLE-to-OLE

The literature provides a few options for converting a VOLE into many OLEs using a single message. One option is to use homomorphic secret sharing (HSS) [BGI16, BGI17, BCG$^{+}$17]; this was the route taken in the recent work of [MORS24]. For sufficiently large rings, this approach yields a minimal communication overhead: it achieves rate-1 garbling, where the (amortized) size of a garbling gate amounts to a single element of $\mathcal{R}$. However, this optimal rate is only achieved over extremely large rings, and due to limitations inherent to HSS-based OLEs, their construction is limited to $B$-bounded arithmetic: that is, arithmetic circuits over the integers (without modular reduction) where all intermediate values of the computation (for all possible “admissible” inputs) are guaranteed to be bounded by $B$.

Another one-message VOLE-to-OLE transform was recently described by Roy in [Roy22]. The approach of Roy is a direct generalization of IKNP [IKNP03] to larger fields. Under the hood, the method of Roy is the one used in the recent works of [HKN24, Hea24] to garble general lookup tables (in [HKN24]) and arithmetic circuits (in [Hea24]). A convenient way to describe the approach at a high level is to rely on puncturable pseudorandom functions (PPRFs). A PPRF is a pseudorandom function equipped with a puncturing algorithm which, given a PRF key $K$ and a point $z$, output a punctured key $K_z$. Given a punctured key $K_z$, one can evaluate the PPRF $F_{K_z}(x) = F_K(x)$ at all points except $x = z$. Furthermore, given $K_z$, the value $F_K(z)$ should remain indistinguishable from random. Now, assume for now that the garbler holds a PPRF key $K$ and that the evaluator somehow managed to obtain the corresponding key $K_u$ punctured at the point $u$. Further, assume that the ring $\mathcal{R}$ has polynomial size. The garbler computes the following values: $a := \sum_{z \in \mathcal{R}} F_K(z)$, $b := \sum_{z \in \mathcal{R}} z \cdot F_K(z)$. Observe that the evaluator can compute $c := \sum_{z \in \mathcal{R}} (u-z) \cdot F_K(z) = u \cdot a - b$, because $K_u$ allows computing all terms $F_K(z)$ except for $F_K(u)$, and this missing term is multiplied by $u-z=0$. Therefore, $b$ and $c$ form additive shares of $u \cdot a$. Furthermore, the garbler can send $v-a$, allowing the evaluator to compute $c+u \cdot (v-a) = u \cdot v - b$, obtaining shares of $u \cdot v$. Because $a = F_K(u) + \sum_{z \neq u} F_K(z)$ is pseudorandom from the viewpoint of $E$ (under the security of the PPRF), $v-a$ computationally hides $v$.

It remains at this stage to explain how the evaluator can obtain the punctured key $K_u$. In [HKN24, Hea24], this is done via the following steps:

- First, the PPRF is instantiated via the GGM PPRF [GGM86, KPTZ13, BW13, BGI14].

- To securely distribute the punctured key $K_u$ (where $G$ holds $K$ and $E$ holds $u$), [HKN24, Hea24] use under the hood the Doerner-shelat protocol [Ds17] that distributes a punctured PPRF key for the GGM PPRF in two rounds via $\log |\mathcal{R}|$ parallel calls to a 2-round oblivious transfer.

- To obtain the necessary OTs (with a single $G$-to-$E$ message), the same approach as [ZRE15] is used: using shares of $\Delta \cdot u_i$ for all the bits $u_i$ of $u$, the parties derive pseudorandom oblivious transfers using a circular correlation robust hash function, and the garbler derandomizes the OTs using a single message (added to the garbled gate).

We note that the above description is (voluntarily) oversimplified and uses a language very different from the terminology used in [HKN24, Hea24] (we believe that the authors of [HKN24, Hea24] are
aware of this “MPC-style” view of their construction, but found more convenient to describe it with a different terminology). Nevertheless, it captures the intuition of their constructions.

The main downside of the approach taken in [HKN24, Hea24] is that to execute the Doerner-shelat protocol, the parties must hold a “bitwise” VOLE for $u$-i.e., they must hold shares of $\Delta \cdot u_i$ for all bits $u_i$ of $u$. Concretely, this means that the size of the labels must scale as $\Omega(\lambda \cdot \log |\mathcal{R}|)$. In turn, because each of the $\log |\mathcal{R}|$ OTs must be derandomized by adding material to the garbled gate, the size of each garbled gate also scales as $\Omega(\lambda \cdot \log |\mathcal{R}|)$. Therefore, the rate of the scheme is $O(1/\lambda)$.

## 2.4 A Garbling-Friendly PPRF from Power-DDH

We overcome the limitations of the previous approaches by introducing a new construction of puncturable pseudorandom function. Our PPRF enjoys the following appealing feature: given additive shares of $\Delta \cdot u$, the parties can compute a pair $(K, K_u)$ (where $K$ is a PPRF key and $K_u$ is the key punctured at $u$) using zero communication. Our PPRF enjoys very short key size (a single element of $\mathbb{Z}_p$, where $p$ is the order of a discrete-log-hard group) in an amortized setting (where many pair $(K, K_u)$ are generated) and can be computed with low complexity (evaluating the PPRF boils down to computing a single exponentiation, which can be done in the complexity class $\mathbb{NC}^1$). We believe that our new PPRF could enjoy other applications.

The security of our PPRF reduces to the following assumption (B is some polynomial bound): fix a group $\mathbb{G}$ of order $p$ with generator $g$. Sample $\alpha \leftarrow \mathbb{Z}_p$ and $h \leftarrow \mathbb{G}$. Then, given

$$ (h^{\alpha^{-B}}, h^{\alpha^{-B+1}}, \dots, h^{\alpha^{-2}}, h^{\alpha^{-1}}, h^{\alpha^1}, h^{\alpha^2}, \dots, h^{\alpha^{B-1}}, h^{\alpha^B}), $$

(that is, all terms $h^{\alpha^i}$ for $i = -B$ to $B$ except for $i = 0$), it should be infeasible to distinguish $h = h^{\alpha^0}$ from random. This assumption is a static and falsifiable variant of the standard power-DDH assumption [GJM03, CNs07]. It follows from existing meta-theorems that it holds in the generic group model. For simplicity, we call it B-power-DDH in this work. We describe our PPRF construction with domain $[B] = \{0, \dots, B\}$ below:

**Setup.** Output the description of a group $\mathbb{G}$ of order $p$ with generator $g$, as well as a “master public key” $(g_i)_{i \in [\pm B]^*} := (h^{\alpha^i})_{i \in [\pm B]^*}$, where $[\pm B]$ stands for $\{-B, \dots, B\} \setminus \{0\}$. Set $g_0 := h$. Set $\alpha$ to be the corresponding master secret key.

**KeyGen.** Sample a secret key $\mathbf{sk} \leftarrow \mathbb{Z}_p$.

**Eval.** On input $x \in [B]$, output $g_x^{\mathbf{sk}} = h^{\alpha^x \mathbf{sk}}$.

**Puncture.** Given a point $z \in [B]$, output $\mathbf{psk} := \alpha^z \cdot \mathbf{sk}$.

**Punctured Eval.** On input $x \in [B]$, if $x \neq z$, output $g_{x-z}^{\mathbf{psk}}$.

Correctness can be checked easily, as $g_{x-z}^{\mathbf{psk}} = h^{\alpha^{x-z}} \cdot \mathbf{psk} = h^{\alpha^{x-z}} \cdot \alpha^z \mathbf{sk} = h^{\alpha^z \mathbf{sk}} = g_x^{\mathbf{sk}}$. Security follows from the fact that when $x = z$, then $g_{x-z} = h$ is indistinguishable from random under the B-power-DDH assumption. In our scheme, the output of the PPRF will additionally be hashed into an element of $\mathbb{Z}_{p-1}$, using a hash function satisfying a suitable correlation-robustness property (the reader can think of this hash as a random oracle for simplicity). In our construction, the hash will also take some salt as input; we omit the details in this simplified overview.

**From VOLE to punctured keys with zero communication.** Recall that our goal is to let $\mathbb{G}$ and $\mathbb{E}$ agree on PPRF keys $(K, K_u)$ where $K_u$ is a key punctured at a value $u$ known to $\mathbb{E}$. Assume for now that we want to perform arithmetic computations over $\mathbb{Z}_B$, and therefore have $u \in \mathbb{Z}_B$. Furthermore, assume that $\mathbb{G}$ and $\mathbb{E}$ hold shares of $\Delta \cdot u$ over $\mathbb{Z}_{p-1}$.

The core observation is the following: let $\mathbb{G}$ denote a generator of $\mathbb{Z}_p^*$, and let $\alpha := G^\Delta \mod p$. Assume that the master public key $(g_i)_{i \in [\pm B]^*} := (h^{\alpha^i})_{i \in [\pm B]^*}$ was generated and added to the garbling by $\mathbb{G}$ (as a “header” of the garbled circuit). Then, if we denote $\mathbf{sk} := G^{\langle \Delta u \rangle_G} \mod p$, it holds that

$$ G^{\langle \Delta u \rangle_E} = G^{\Delta u - \langle \Delta u \rangle_G} = \alpha^u \cdot G^{\langle \Delta u \rangle_G} = \alpha^u \cdot \mathbf{sk} \mod p, $$

hence the evaluator can set $\mathbf{psk} := G^{\langle \Delta u \rangle_E}$ and obtain the punctured key at $u$ with respect to the secret key $\mathbf{sk}$.
## 2.5 Rate-$\Omega(1/\lambda)$ Modular Arithmetic Garbling

Fix a security parameter $\lambda$ and a polynomial modulus $B = B(\lambda)$. The previous scheme suggests the following garbling scheme over $\mathbb{Z}_B$ (below, the sharing is done modulo $p-1$):

- The garbler initially generates $\Delta \leftarrow \mathbb{Z}_{p-1}$, sets $\alpha := G^{\Delta} \bmod p$, and samples the master public key $(g_i)_{i \in [\pm B]^*}$ using exponent $\alpha$.

- For each input wire, the garbler samples her shares $(\langle x \rangle_G, \langle \Delta x \rangle_G)$ of the (yet-undefined) input $x$ uniformly at random. Once $x$ is defined, the input labels will be constructed as the corresponding evaluator shares $(\langle x \rangle_E, \langle \Delta x \rangle_E)$ of $x$. We will maintain the invariant that, before "computing" each gate with inputs $x_0, x_1$ during the evaluation of the circuit on $x$, the garbler and the evaluator will hold shares $(\langle x_b \rangle, \langle \Delta \cdot x_b \rangle)$ for $b = 0, 1$.

- For each multiplication gate and for each of the 4 cross-products $u \cdot v$ of the gate, where $u \in \mathbb{Z}_B$ will be known to $E$ and $v$ is known to $G$, the garbler computes a PPRF key $\mathbf{sk} := G^{\langle \Delta u \rangle_G}$. Then, she computes $a := \sum_{z \in [\pm B]} \mathbf{F}_{\mathbf{sk}}(z)$ and $b := \sum_{z \in [\pm B]} z \cdot \mathbf{F}_{\mathbf{sk}}(z)$. She sets her share of $u \cdot v$ to $b$ and adds $v - a$ to the garbled gate.

Given the garbled circuit and the input labels, the evaluator will iteratively compute the labels of each outgoing wire of a gate from the labels of the incoming wire. For each cross-product $u \cdot v$ in a multiplication gate $\gamma : x, y \mapsto z = x \cdot y$, the evaluator sets $\mathbf{psk} := G^{\langle \Delta^u \rangle_E}$ and uses it to compute $u \cdot (v-a) + \sum_{z \in \mathcal{R}} (u-z) \cdot \mathbf{F}_K(z) = u \cdot v - b$ (over $\mathbb{Z}_{p-1}$). Using the template for arithmetic garbling described in Section 2.2, this allows him to obtain shares $\langle xy \rangle_E, \langle \Delta xy \rangle_E$, i.e., the label of the outgoing wire $z$.

Overall, assuming that $\log p = O(\lambda)$ and that the group elements have $O(\lambda)$-bit representations, the size of a garbling of a $\mathbb{Z}_B$-arithmetic circuit is bounded by $O(\lambda \cdot B + |C| \cdot \lambda)$. Asymptotically, when $|C|$ becomes larger than $B$, this translates to an amortized cost of $O(\lambda)$ bits per gate over $\mathbb{Z}_B$. However, the method described above does not work – in fact, it is not even correct!

**Modulus mismatch, and how to fix it.** The issue stems from a modulus mismatch between the $\mathbb{Z}_B$-arithmetic computation, and the computation modulo $\mathbb{Z}_{p-1}$. Concretely, we would ideally like to have the following: a label for a wire $w$ carrying a value $x$ is a pair $(\langle x \rangle_E, \langle \Delta x \rangle_E)$, and the corresponding key (computed independently of $x$) is $(\langle x \rangle_G, \langle \Delta x \rangle_G)$, where

- $\langle x \rangle_E, \langle x \rangle_G$ form additive shares of $x$ over $\mathbb{Z}_B$, and

- $\langle \Delta \cdot x \rangle_E, \langle \Delta \cdot x \rangle_G$ form additive shares of $\Delta \cdot x$ over $\mathbb{Z}_{p-1}$.

However, this cannot work. First, adding shares of $\Delta x$ and $\Delta y$ yields shares of $\Delta(x+y)$ over $\mathbb{Z}_{p-1}$, but $(x+y)$ is not reduced modulo $B$. Second, going back to the template described in Section 2.2, recall that to compute shares of the cross term $\langle x \rangle_G \cdot \langle y \rangle_E$ (when computing the keys and labels for a product gate with inputs $x$ and $y$), the first step was for the parties to compute shares of $\Delta \langle y \rangle_E$ of the form $(\langle \Delta y \rangle_G - \Delta \cdot \langle y \rangle_G, \langle \Delta y \rangle_E)$. However, this is incorrect, because $y - \langle y \rangle_G$ is not equal to $\langle y \rangle_E$ when the computation is done modulo $p-1$.

We could attempt to fix this by letting $\langle x \rangle_G, \langle x \rangle_E$ be shares of a value $x$ over $\mathbb{Z}_{p-1}$. However, we would not anymore be computing a circuit over $\mathbb{Z}_B$ (but rather a bounded integer arithmetic circuit), missing our target goal. But even more fundamentally, recall that our PPRF-based method is restricted to puncturing values from a polynomial-sized set. In our context, to compute shares of the cross term $\langle x \rangle_G \cdot \langle y \rangle_E$, the evaluator wants to obtain a key punctured at $\langle y \rangle_E$. That is, we inherently require the shares themselves to be small. Alas, even fixing the input labels to be small does not work: first, we cannot mask over the integers with polynomial-size values (and we cannot use rejection-sampling-based methods as the garbler shares must be picked before the inputs to be masked are even defined), and second, the size of the shares will increase significantly after each gate (by a factor at least $B^2$).

**First idea: PPRF-based modular reduction.** The above issues are non-trivial to solve, and our solution combines several ideas to address each of the shortcomings of the naive approach. We start by changing the invariant that we wish to maintain. For each wire carrying a value $x$, the parties will hold:

- values $(k_x, \ell_x) := (\langle x \rangle_E, \langle x \rangle_G) \in \mathbb{Z}_B$ forming additive shares of $x$ over $\mathbb{Z}_B$, and

- values $(K_x, L_x) := (\langle \Delta \cdot x \rangle_E, \langle \Delta \cdot x \rangle_G)$ forming additive shares of $\Delta \cdot x \in \mathbb{Z}_{p-1}$, where $\langle x \rangle_E$ is viewed as an element of $\{0, \dots, B-1\}$ embedded into $\mathbb{Z}_{p-1}$.
We must now explain how we maintain the invariant, which is non-trivial even for addition gates. We start with addition gates, as they are simpler and already use one of our core ideas. Given an addition gates with incoming wires carrying values $x$ and $y$, the garbler sets $\tilde{k}_z := k_x + k_y$ and $\tilde{K}_z := K_x + K_y$, while the evaluator sets $\tilde{l}_z := \ell_x + \ell_y$ and $\tilde{L}_z := L_x + L_y$. Observe that $(\tilde{K}_z, \tilde{L}_z)$ form additive shares of $\Delta \cdot (\ell_x + \ell_y) = \Delta \cdot \tilde{l}_z \bmod p - 1$. However, while $(\tilde{k}_z, \tilde{l}_z)$ sum to $x + y$ when reduced mod $B$, they are not elements of $\mathbb{Z}_B$ as the sum is computed over the integers.

To control the growth, we build a gadget allowing the parties, given shares of $\Delta \cdot \tilde{l}_z$, to compute shares of $\Delta \cdot [\tilde{l}_z \bmod B]$ (where $[\tilde{l}_z \bmod B]$ denotes the remainder of the euclidean division of $\tilde{l}_z$ by $B$, which belongs to $\mathbb{Z}_B$). This is done by relying on the fact that in a PPRF-based OLE, the parties can actually compute an arbitrary function of the punctured point for free. Indeed, fix an arbitrary function $f$ and let $\mathbf{sk} := G^{\tilde{K}_z}$ and $\mathbf{psk} := G^{\tilde{L}_z} = \alpha^{\tilde{l}_z} \cdot \mathbf{sk}^{-1} \bmod p$. Using $\mathbf{sk}$, let the garbler compute

$$a := \sum_{i \in [2B]} \mathbf{F}_{\mathbf{sk}}(i) \bmod p - 1,$$

$$K_z := \sum_{i \in [2B]} f(i) \cdot \mathbf{F}_{\mathbf{sk}}(i) \bmod p - 1.$$

Above, the PPRF is assumed to have domain $[2B]$ because $\tilde{l}_z = \ell_x + \ell_y$ can be as large as $2B$. Then, the evaluator can compute

$$c := \sum_{i \in [2B], i \neq \tilde{l}_z} (f(\tilde{l}_z) - f(i)) \cdot \mathbf{F}_{\mathbf{psk}}(i) = f(\tilde{l}_z) \cdot a - K_z \bmod p - 1.$$

Hence, $\mathbf{G}$ and $\mathbf{E}$ hold shares of $f(\tilde{l}_z) \cdot a$ over $\mathbb{Z}_p - 1$. Eventually, the garbler sends $a - \Delta$ to let the evaluator shift his share to a share $L_z$ of $\Delta \cdot f(\tilde{l}_z)$. Setting $f: x \mapsto [x \bmod B]$, the parties ultimately obtain shares $(K_z, L_z)$ of $\Delta \cdot \ell_z$ with $\ell_z := [\tilde{l}_z \bmod B]$, and set $(k_z, \ell_z) := ([k_z \bmod B], [\tilde{l}_z \bmod B])$, maintaining the invariant.

**Second idea: leakage-resilient computation on small shares.** The above idea suffices to maintain the invariant for addition gates. However, for multiplication gates, we still have the issue that after executing a PPRF-based OLE, the shares obtained are large. Concretely, consider a multiplication gate with inputs $x$ and $y$, where the garbler holds the keys $(k_x, K_x)$ and $(k_y, K_y)$, and the evaluator holds the labels $(\ell_x, L_x)$ and $(\ell_y, L_y)$. The parties start by computing

$$- \tilde{k}_z := k_x k_y + \langle k_x \ell_y \rangle_{\mathbf{G}} + \langle k_y \ell_x \rangle_{\mathbf{G}} \text{ (over the integers)}$$

$$- \tilde{l}_z := \ell_x \ell_y + \langle k_x \ell_y \rangle_{\mathbf{E}} + \langle k_y \ell_x \rangle_{\mathbf{E}} \text{ (over the integers)},$$

where we crucially require the shares of the cross terms $k_x \ell_y$ and $k_y \ell_x$ to be computed over the integers. It now remains for the parties to compute shares of $\Delta \cdot \tilde{l}_z$; after that, both parties will apply the same modular reduction step as for addition gates to obtain shares of $\Delta \cdot [\tilde{l}_z \bmod B] \bmod p - 1$. The issue is that, unlike for addition gates, the size of $\tilde{l}_z$ is influenced by the size of the shares $\langle k_x \ell_y \rangle_{\mathbf{E}}$, $\langle k_y \ell_x \rangle_{\mathbf{E}}$. Hence, to let the evaluator obtain a key punctured at $\tilde{l}_z$, we must guarantee that $\tilde{l}_z$ remains polynomially bounded.

To do that, we let the PPRF (used to compute the shares of the cross terms) output polynomially-bounded values. Concretely, let us focus on the cross term $k_x \ell_y$. Let $\mathbf{sk} := G^{\langle \Delta \ell_y \rangle_{\mathbf{G}}} \bmod p$ and $\mathbf{psk} := G^{\langle \Delta \ell_y \rangle_{\mathbf{E}}} = \alpha^{\ell_y} \cdot \mathbf{sk} \bmod p$. Let $\tilde{B}$ be a (polynomial) bound on $\mathbf{F}_{\mathbf{sk}}(i)$ (for any $i \in [B]$). Recall that $\langle k_x \ell_y \rangle_{\mathbf{E}}$ is computed as $\ell_x \cdot (k_x - a) + \sum_{i \neq \ell_y} (\ell_y - i) \cdot \mathbf{F}_{\mathbf{psk}}(i)$, where $a = \sum_i \mathbf{F}_{\mathbf{sk}}(i)$. Then, the size of $\langle k_x \ell_y \rangle_{\mathbf{E}}$ is approximately bounded by $B^2 \cdot \tilde{B}$. This translates to a bound on the size of $\tilde{l}_z$ of about $2B^2 \tilde{B}$. Hence, to execute the PPRF-based modular reduction procedure described above, it suffices at this stage to rely on another PPRF with domain $[2B^2 \tilde{B}]$ and outputs over $\mathbb{Z}_{p-1}$.

The main issue of this approach is that setting $\tilde{B}$ to a polynomial introduces leakage on $k_x$. Concretely, the evaluator is given $k_x - a$, where $a = \sum_i \mathbf{F}_{\mathbf{sk}}(i)$. Subtracting the terms that $\mathbf{E}$ can compute, we are left with $k_x - \mathbf{F}_{\mathbf{sk}}(\ell_x)$: the (secret) wire key $k_x$ is masked with $\mathbf{F}_{\mathbf{sk}}(\ell_x)$ over the integers, but $\mathbf{F}_{\mathbf{sk}}(\ell_x)$ is bounded by $\tilde{B}$! Fortunately, we can measure precisely the leakage that this value induces: concretely, if $k_x - \mathbf{F}_{\mathbf{sk}}(\ell_x)$ belongs to $\{B - \tilde{B}, \dots, 0\}$, no leakage occurs; else, $\mathbf{E}$ learns information of the form “$k_x \le i$” or “$k_x \ge i$” (for example, if $k_x - \mathbf{F}_{\mathbf{sk}}(\ell_x) = 2$, $\mathbf{E}$ learns that $k_x \ge 2$).

To handle this leakage, we adopt the following strategy: instead of using $k_x$ directly in the computation, the garbler shares $k_x$ into $c$ shares $(k_x^1, \dots, k_x^c)$ over $\mathbb{Z}_B$, where $c$ is a value to be determined later. The intermediate values $\tilde{k}_z, \tilde{l}_z$ are computed via the modified equations below (over the integers):
$$ - \tilde{k}_z := \sum_{i,j \le c} k_x^i k_y^j + \sum_{i=1}^c (\langle k_x^i \ell_y \rangle_G + \langle k_y^i \ell_x \rangle_G) $$

$$ - \tilde{\ell}_z := \ell_x \ell_y + \sum_{i=1}^{c} (\langle k_x^i \ell_y \rangle_E + \langle k_y^i \ell_x \rangle_E). $$

Above, each of the shares $\langle k_x^i \ell_y \rangle_E$, $\langle k_y^i \ell_x \rangle_E$ are computed via the PPRF-based procedure, using a polynomial bound $\tilde{B} := \lambda \cdot B$. In addition, we rely on a “salted” variant of the PPRF to ensure independent executions: $F_{sk}$ now takes as input a pair $(i, \text{salt})$ where salt is any string, and the PPRF security game is extended to a multi-instance security notion where multiple values $(F_{sk}(i, \text{salt}_j))_j$ are simultaneously indistinguishable from random even given the punctured key psk punctured at $i$, provided that the salt$_j$ are pairwise distinct.

Observe that the probability that a leakage occurs, that is, e.g., $k_x^i - F_{sk}(\ell_x, \text{salt}_i)$ does not belong to $\{B - \lambda B, \dots, 0\}$, happens with probability $1/\lambda$. For $k_x$ to leak, it must happen that all the $k_x^i$ leak simultaneously, which happens with probability $1/\lambda^c$. Setting $c$ to be any superconstant function suffices to make this quantity negligible. An important observation$^6$, that yields a factor-$c$ efficiency improvement in the garbled circuit size, is that to compute the sum $\sum_{i=1}^c (\langle k_x^i \ell_y \rangle_E + \langle k_y^i \ell_x \rangle_E)$, it is not necessary to transmit all masked values $\text{shift}_x^i := k_x^i - a_x^i$ and $\text{shift}_y^i := k_y^i - a_y^i$ (even though it would be secure to do so): the evaluator computes this sum as $\sum_{i=1}^c \ell_x \cdot (k_x^i - a_x^i) + \sum_{i=1}^c \ell_y \cdot (k_y^i - a_y^i)$ (where the $a_x^i$, $a_y^i$ denote the values $\sum_j F_{sk}(j, \text{salt}_i^x)$, $\sum_j F_{sk}(j, \text{salt}_i^y)$ for appropriate distinct salts). Therefore, as $\ell_x$ and $\ell_y$ factor out, it suffices to let the evaluator transmit only $\sum_{i=1}^c (k_x^i - a_x^i)$ and $\sum_{i=1}^c (k_y^i - a_y^i)$. As a consequence, we can set $c := \Omega(\lambda)$ to achieve a leakage probability of $O(1/2^\lambda)$ without harming the rate of our garbling scheme.

Using the above ideas, the parties have all the required ingredients to compute shares $(\tilde{K}_z, \tilde{L}_z)$ of $\Delta \cdot \tilde{\ell}_z$ mod $p-1$ (using this time PPRF computations with domain $\mathbb{Z}_{p-1}$). Concretely, the parties compute

$$ - \tilde{K}_z := \langle K_x \ell_y \rangle_G - \Delta \cdot (\sum_{i=1}^c (\langle k_x^i \ell_y \rangle_G + \langle k_y^i \ell_x \rangle_G) + \sum_{i=1}^c (\langle \Delta k_x^i \ell_y \rangle_G + \langle \Delta k_y^i \ell_x \rangle_G) \mod p - 1, \text{and} $$

$$ - \tilde{L}_z := \langle K_x \ell_y \rangle_E + L_x \ell_y + \sum_{i=1}^{c} (\langle \Delta k_x^i \ell_y \rangle_E + \langle \Delta k_y^i \ell_x \rangle_E) \mod p - 1. $$

For the same reason as before, the term $\sum_{i=1}^c (\langle \Delta k_x^i \ell_y \rangle_E + \langle \Delta k_y^i \ell_x \rangle_E)$ can be computed by $E$ using only two $O(\lambda)$-bit “sums of shifts” from $G$, instead of $2c$. A simple (but slightly tedious) calculation shows that $\tilde{K}_z + \tilde{L}_z = \Delta \cdot \tilde{\ell}_z$ mod $p-1$. Furthermore, the value of $\tilde{\ell}_z$ is bounded by (approximately) $2c \cdot \lambda B^3$, which is polynomial; hence, the parties can use the previous PPRF-based modular reduction to compute shares $(K_z, L_z)$ of $\Delta \cdot [\tilde{\ell}_z \mod B]$ over $\mathbb{Z}_{p-1}$ obtaining the desired invariant.

**Dealing with circular security.** An issue that we have overlooked so far is that the construction uses PPRF outputs to hide terms that depend on $\Delta$, but $\Delta$ is (the discrete log of) the master secret key of the PPRF itself. While the construction sketched above is plausibly secure, proving security requires assuming a non-standard circularly secure flavor of the power-DDH assumption. To get a reduction to power-DDH, we take instead a leveled approach, using $D$ different keys $\Delta_1, \dots, \Delta_D$ for each of the $D = \text{depth}(C)$ levels of the circuit $C$, and make sure that every time a $\Delta_i$ is masked with a term $F_{sk_j}(x)$, it holds that $j < i$. This introduces additional overhead, as the garbled circuit must now contain $D$ master secret keys, and additional complications, as some of the equations we used here break down when we have multiple $\Delta$'s (specifically, the previous equations for computing $\tilde{L}_z, \tilde{K}_z$ don't work anymore). However, correct equations for the leveled setting can be recovered with slightly more work.

**Wrapping up.** Putting everything together, the size of the garbled circuit scales as $|\hat{C}| = O(\lambda \cdot |C| + \lambda B' \cdot \text{depth}(C))$, where $B' = O(c\lambda B^3)$ and $c$ is $\omega(1)$ (we can take $c = \Omega(\lambda)$ to get an exponentially small failure probability). Asymptotically, and for not too “tall-and-skinny” circuits, this yields a circuit with an amortized cost of $O(\lambda)$ bits per gate, a log $B = O(\log \lambda)$ improvement over the state-of-the-art garbling scheme for modular arithmetic from [Hea24] (which uses $O(\lambda \cdot \log B)$ bits per gate), and the first garbling scheme ever to beat the $1/\lambda$-rate barrier for general modular arithmetic circuits.

Eventually, while the construction is tailored to small integer rings $\mathbb{Z}_B$, it immediately extends to rings $\mathbb{Z}_N$ of arbitrary size, provided that $N$ is smooth (i.e., has only polynomial-size coprime factors) by using CRT decomposition and running the modular garbling scheme for each of the coprime factors. It also extends to extension rings of $\mathbb{Z}_B$, isomorphic to $\mathbb{Z}_B^t$, by using “schoolbook” multiplication to write a product over $\mathbb{Z}_B^t$ as $t^2$ cross products over $\mathbb{Z}_B$; in this setting, the rate improves asymptotically over the state of the art as long as $t^2 \ll \log B$, which still suffices to handle superpolynomial-size extension rings.

<footnote n="6">⁶ Due to an anonymous Eurocrypt’25 reviewer</footnote>
# 3 A Puncturable PRF with Short Keys from Power-DDH

## 3.1 Correlation-Robust Hashing

A hash family $H$ is correlation-robust for a class of correlations $C$ if samples of the form $H(C(x, s))$ for public inputs $x$'s and secret $s$ are indistinguishable from random. Common classes of correlations in the literature include additive correlations [IKNP03] ($C(x, s) = x + s$), affine correlations [Ser24] ($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] ($C(x, s) = s^x$ where $s \in \mathbb{G}$ and $x \in \mathbb{Z}_{\text{ord}(\mathbb{G})}$). In this work, we rely on a correlation-robust hash function for the latter correlation. We further need the hash family to be *tweakable*: A hash function $H$ is *tweakable correlation-robust* for a class of correlations $C$ if 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).

**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 introduce below the notion of *tweakable correlation-robustness for exponential correlations*. The definition is reproduced verbatim from [CHHK25]:$^7$

**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} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}$. Given $h \in \mathbb{G}$, let $\mathcal{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 call $y$ the *tweak*.

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

$$|\Pr[\mathcal{A}^{\text{H}, \mathcal{O}_{H,h}}(1^{\lambda}) = 1] - \Pr[\mathcal{A}^{\text{H,RO}}(1^{\lambda}) = 1]| \le \text{negl}(\lambda),$$

where the probability is taken over the random choice of $h \leftarrow \mathbb{G}$ and of a random oracle $\text{RO}: \mathbb{Z}_{p-1} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}$. When $H$ and $\mathcal{O}_{H,h}$ do not take as input a *tweak* $y$, we say that $H$ is correlation-robust for exponential correlations over $\mathbb{G}$.

In particular, we note that random oracles are *tweakable correlation-robust* for exponential correlations, hence security under the existence of a TCR hash implies security in the random oracle model. TCR hashing for exponential correlations is a relatively simple security notion that can be plausibly conjectured for any standard (unstructed) hash function, such as SHA2 or SHA3.

## 3.2 Puncturable Pseudorandom Functions

Pseudorandom functions (PRF), introduced in [GGM86], are keyed functions which are indistinguishable from truly random functions. A *puncturable pseudorandom function* (PPRF) is a PRF $F$ such that given an input $z$, and a PRF key $sk$, one can generate a *punctured key*, denoted $psk$, which allows evaluating $F$ at every point except for $z$, and does not reveal any information about the value $F.Eval(sk, z)$. PPRFs have been introduced in [KPTZ13, BW13, BGI14].

In this work, we introduce and build upon a *puncturable pseudorandom function* which features a reusable master public key and master secret key: the same pair $(mpk, msk)$ can be reused for an arbitrary number of generations of PPRF secret keys $sk$ (and corresponding punctured secret keys $psk$). The main advantage of our construction is its key size: the keys $sk$ and $psk$ contain a single element of $\mathbb{Z}_p^*$ (where $p$ is the order of a dlog-hard group). This is particularly useful in an amortized setting, where the cost of storing $mpk$ is amortized across many PPRF key generations. To capture this setting, we define below a variant of selectively-secure *puncturable pseudorandom functions with setup*.

**Definition 7 (Puncturable Pseudorandom Function).** A *puncturable pseudorandom function* (PPRF) with domain $Y = Y_{B,\lambda}$ is a 5-tuple of probabilistic polynomial-time algorithms (F Gibs, F. KeyGen, F. Eval, F. Punct, F. PEval) such that

<footnote>$^7$ Though [CHHK25] is a follow-up to the current work, our work was updated a posteriori to include the formal definition of this flavor of correlation-robustness, that was first formally defined in [CHHK25].</footnote>
Experiment ExpPPRF(1<sup>λ</sup>, B, b)

**Setup Phase.** Upon receiving a setup query from $\mathcal{A}$, the challenger samples (mpk, msk) ←$F$.Setup(1<sup>λ</sup>, B) and sends mpk to $\mathcal{A}$. Ignore all further setup queries from $\mathcal{A}$.

**Challenge Phase.** Upon receiving a query (challenge, z) from $\mathcal{A}$ with $z \in [B]$, the challenger picks sk ←$F$.KeyGen(mpk). The challenger sends psk ←$F$.Punct(msk, sk, z) to $\mathcal{A}$. If $b = 0$, the challenger additionally sends F.Eval(msk, sk, z) to $\mathcal{A}$; otherwise, if $b = 1$, the challenger picks y ←$F$.Y and sends it to $\mathcal{A}$.

Fig. 1: Selective security game with reusable setup for puncturable pseudorandom functions. The adversary can request an arbitrary number of challenges. At the end of the experiment, $\mathcal{A}$ sends a guess $b'$ and wins if $b' = b$.

- $FSetup(1^\lambda, B)$ outputs a master public key and master secret key (mpk, msk). The integer $B$ specifies the input domain $[B]$ of the PRF, and $(\lambda, B)$ specifies the range $Y_{\lambda,B}$ (we assume that $(\lambda, B)$ are included in mpk).

- $F.KeyGen(mpk)$ outputs a PRF key sk.

- $F.Eval(msk, sk, x)$, where $x \in [B]$, outputs a PPRF evaluation $y \in \{0, 1\}^\lambda$.

- $F.Punct(msk, sk, z)$, outputs a punctured key psk.

- $FPEval(mpk, psk, z, x)$, on input a punctured key psk, a punctured point $z$, and a point $x$, outputs $y \in \{0, 1\}^\lambda$ if $x \neq z$, and $\perp$ otherwise.

A PPRF $F$ is selectively secure with reusable setup no probabilistic polynomial-time adversary wins the experiment ExpPPRF represented on Figure 1 with non-negligible advantage over the random guess.

**Remark 8.** Our definition of PPRFs differs from the standard presentation on two aspects. First, we consider PPRFs where the same setup can be reused for many key generations; we recover the standard selective security game for PPRFs by restricting $\mathcal{A}$ to make a single challenge query. Second, the standard definition of PPRFs typically requires that $FSetup$, $F.KeyGen$, $F.Eval$ is itself a pseudorandom function (note that this is not implied by the selective security game, which only ensures pseudorandomness at the punctured point given the punctured key). This stronger security notion is not needed in our work, but we note that it can be nevertheless shown to hold as well for our construction using a slightly stronger assumption.

## 3.3 An Efficient PPRF from Power-DDH

We represent on Protocol 1 a construction of punctured pseudorandom function over a polynomial-size domain $[B]$ from the power-DDH assumption.

Algorithm Puncturable PRF From Power-DDH

<table><thead><tr><th></th><th>F.setup(1<sup>λ</sup>, B)</th><th>F.punct(msk, sk, z)</th></tr></thead><tbody><tr><td>1:</td><td>(G, p, g) := GrpGen(1<sup>λ</sup>)</td><td>1: parse (p, α) from msk</td></tr><tr><td>2:</td><td>(α, h) ←$Z_p^*$ × G</td><td>2: return psk = α<sup>z</sup>sk mod p</td></tr><tr><td>3:</td><td>for i ∈ [±B], g<sub>i</sub> := h<sup>α<sup>i</sup></sup></td><td>F.PEval<sup>H</sup>(mpk, psk, z, x)</td></tr><tr><td>4:</td><td>mpk := (G, p, (g<sub>i</sub>)<sub>i∈[±B]*</sub>)</td><td>1: parse (g<sub>i</sub>)<sub>i≠0</sub> from mpk</td></tr><tr><td>5:</td><td>msk := (mpk, α, g<sub>0</sub>)</td><td>2: return H(g<sub>x-z</sub><sup>psk</sup>)</td></tr><tr><td>6:</td><td>return (mpk, msk)</td><td></td></tr><tr><td></td><td>F.KeyGen(mpk)</td><td>F.Eval<sup>H</sup>(msk, sk, x)</td></tr><tr><td>1:</td><td>parse p from mpk</td><td>1: parse (g<sub>i</sub>)<sub>i∈[±B]</sub> from msk</td></tr><tr><td>2:</td><td>return sk ←$Z_p^*$</td><td>2: return H(g<sub>x</sub><sup>sk</sup>)</td></tr></tbody></table>
Protocol 1: Puncturable PRF from the power-DDH assumption.

The construction involves a large master public key mpk, containing $\Omega(B)$ elements of a group $\mathbb{G}$ of order $p$. However, in an amortized setting where the same master public key is reused across $n \gg B$ generations of PRF keys, it features extremely compact keys: both the secret key sk and the punctured secret key psk contain a single element of $\mathbb{Z}_p^*$. The procedures F.Eval$^H$ and F.PEval$^H$ rely on a hash function $H: \mathbb{G} \to \mathcal{Y}$, where $\mathcal{Y} = Y_{\lambda,B}$ is the range of the PPRF. Formally, $H$ is a family of functions $H_{\lambda,B}$ parametrized by $(\lambda, B)$ (note that $\mathbb{G}$ is fully determined by $\lambda$ as GrpGen is a deterministic procedure), but we drop the transcript for readability. We require $H$ to be a TCR hash for exponential correlations (see Definition 6).

**Theorem 9.** *Assume that the B-power-DDH assumption holds (Definition 3) and that $H$ is a tweakable correlation-robust hash for exponential correlations over $\mathbb{G}$. Then the construction (F.setup$_B$, F.KeyGen, F.Eval, F.Punct, F.PEval) from Protocol 1 is a selectively-secure puncturable pseudorandom function with reusable setup with polynomial-size input domain $[B]$.*

We note that this basic version of the PPRF does not use tweaks: standard (non-tweakable) correlation-robustness actually suffices (but the tweak will be necessary in the version used in our construction, that we discuss next).

*Proof of Theorem 9.* First, we argue correctness. Fix any mpk = $(\mathbb{G}, p, (g_i)_{i \in [\pm B]^*})$ and msk = (mpk, $\alpha, g_0$) in the support of F.setup$_B$. Fix any sk ∈ $\mathbb{Z}_p^*$, and $x, z \in [\pm B]$ with $x \neq z$. Then,

$$F.Eval(msk, sk, x) = H(g_x^{\text{sk}}) = H(g^{\alpha^x \cdot \text{sk}}) = H(g^{\alpha^{x-z} \cdot (\alpha^z \text{sk})}) = H(g_{x-z}^{\text{psk}}) = F.PEval(mpk, psk, z, x).$$

We now argue security through a sequence of straightforward game hops:

**Game 0.b.** This is the experiment ExpPPRF($1^{\lambda}$, $B$, $b$) from Figure 1:

**Setup Phase.** The challenger picks $(\mathbb{G}, p, g) := \text{GrpGen}(1^{\lambda})$ and samples $\alpha, h \leftarrow \mathbb{Z}_p^* \times \mathbb{G}$. It sets $(g_i)_{i \in [\pm B]} := (h^{\alpha^i})_{i \in [\pm B]}$ and sends $(\mathbb{G}, p, (g_i)_{i \in [\pm B]^*})$ to $\mathcal{A}$. Upon receiving $z \in [\pm B]$, it samples sk $\leftarrow \mathbb{Z}_p^*$.

**Challenge Phase.** The challenger sets psk := $\alpha^z \text{sk}$. If $b = 0$, the challenger sets $y := H(g_0^{\text{psk}})$; else, the challenger sets $y \leftarrow \mathcal{Y}$. The challenger sends (psk, $y$) to $\mathcal{A}$.

**Game 1.b.** In this game, the challenger does not construct psk as $\alpha^z \text{sk}$ in the challenge phase; Instead, it samples psk $\leftarrow \mathbb{Z}_p^*$. Because sk is uniformly distributed over $\mathbb{Z}_p^*$, so is $\alpha^z \text{sk}$, hence Game 1.b is perfectly indistinguishable from Game 0.b.

**Game 2.b.** In this game, the challenger sets $(g_i)_{i \in [\pm B]^*} := (h^{\alpha^i})_{i \in [\pm B]^*}$, but behaves differently in the challenge phase:

- If $b = 0$, it behaves as in Game 1.0, sets $g_0 := h$ and sends $y := H(g_0^{\text{psk}})$.

- If $b = 1$, it samples instead a fresh uniform $g_0 \leftarrow \mathbb{G}$, and sends $y := H(g_0^{\text{psk}})$.

The only difference with Game 1.b happens when $b = 1$, where $y$ is computed as $H(g_0^{\text{psk}})$ for a fresh uniformly random group element $g_0$. Observe that with overwhelming probability, all punctured secret keys psk are distinct. Therefore, by the tweakable correlation-robustness of $H$ for exponential correlations over $\mathbb{G}$ (Definition 6), the distribution of every $y$ is indistinguishable from the uniform distribution over $\mathbb{G}$, hence Game 1.b and Game 2.b are indistinguishable.

*Claim.* Under the B-power-DDH assumption, the advantage of any adversary in distinguishing Game 2.0 and Game 2.1 is negligible.

*Proof.* We show how to turn an adversary against Game 2.b into an adversary with the same advantage against the B-power-DDH assumption. The reduction receives a sample $((h^{\alpha^i})_{i \in [\pm B]^*}, g_0)$ from the distribution $\mathcal{D}_b$ from Definition 3. The reduction sends $(h^{\alpha^i})_{i \in [\pm B]^*}$ to $\mathcal{A}$ in the setup phase. In the
challenge phase, it ignores the value $z$ received from $\mathcal{A}$, samples $\text{psk} \leftarrow_S \mathbb{Z}_p^*$, and computes $y := \text{H}(g_0^{\text{psk}})$. It sends $(\text{psk}, y)$ to $\mathcal{A}$. Observe that the view of $\mathcal{A}$ is perfectly identical to Game 2.b. Upon receiving a guess $b'$ from $\mathcal{A}$, the reduction outputs the guess $b = b'$; the advantage of the reduction against $\mathcal{B}$-power-DDH is exactly that of $\mathcal{A}$ in distinguishing Game 2.0 and Game 2.1. This concludes the proof. ■

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

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

Remark 10 (Pseudorandomness). As noted in Remark 8, the standard definition of PPRFs typically requires that $\text{F}\cdot\text{Setup}$, $\text{F}\cdot\text{KeyGen}$, $\text{F}\cdot\text{Eval}$) is itself a pseudorandom function, and this property is not implied by the selective security game. We note that our candidate can straightforwardly be shown to be a PRF assuming the all-random power-DDH assumption (Definition 4), which is equivalent to the $\mathcal{B}$-power-DDH assumption (see Theorem 5).

## 3.4 A Modified PPRF Procedure

In the previous section, we described the PPRF ($\text{F}\cdot\text{Setup}$, $\text{F}\cdot\text{KeyGen}$, $\text{F}\cdot\text{Eval}$, $\text{F}\cdot\text{Punct}$, $\text{F}\cdot\text{PEval}$) in a self-contained way. In this section, we introduce several modifications of the PPRF that facilitate its use within our modular garbling scheme. At a high level, we introduce two types of modifications:

- We change the procedures ($\text{F}\cdot\text{Setup}$, $\text{F}\cdot\text{KeyGen}$, $\text{F}\cdot\text{Punct}$) to generate pairs $(\text{sk}, \text{psk})$ (where $\text{psk}$ is a key punctured at $z \in [B]$) from subtractive shares of $\Delta z$ where $\Delta \in \mathbb{Z}_{p-1}$ is a value such that $\alpha = G^\Delta \bmod p$ (for some generator $G$ of $\mathbb{Z}_p$).

- We let $\text{H}$ take an auxiliary salt $\text{salt}$ as input. Looking ahead, we will use this salt to ensure independence across various events in our analysis. For simplicity, we keep the notation $\text{F}\cdot\text{Eval}^\text{H}$ and $\text{F}\cdot\text{PEval}^\text{H}$ and treat salt as an additional optional input (when salt is not passed as input, we assume that it is replaced with the dummy string $0^\lambda$).

Let $G$ be a generator of $\mathbb{Z}_p^*$ and let $\alpha = G^\Delta \bmod p$ for some $\Delta \in \mathbb{Z}_{p-1}$. Consider a secret key $\text{sk} \leftarrow_S \text{F}\cdot\text{KeyGen}(\text{mpk})$ and a punctured key $\text{psk} := \text{F}\cdot\text{Punct}(\text{msk}, \text{sk}, z)$. Write $\text{sk} = G^\Gamma \bmod p$. Then, by construction, we have $\text{psk} = G^{\Delta z + \Gamma} \bmod p$. That is, the pair $(\text{psk}, \text{sk})$ can be viewed as a pair of subtractive shares $(\Gamma_G, \Gamma_E) = (\Gamma, \Delta z + \Gamma)$ of $\Delta z$ lifted to the exponent of $G$. We call $\Gamma_E$ the evaluator share and $\Gamma_G$ the garbler share. We make use of this observation by defining alternative PPRF algorithms $\text{F}\cdot\text{Setup}^*$, $\text{F}\cdot\text{KeyGen}^*$, $\text{F}\cdot\text{Punct}^*$ that generate secret keys $\text{sk}$ and punctured secret keys $\text{psk}$ respectively from shares of $\Delta z$. In the procedures below, $\text{GrpGen}^*(1^\lambda)$ refers to an algorithm that behaves identically to $\text{GrpGen}(1^\lambda)$ and additionally outputs a generator $G$ of $\mathbb{Z}_p^*$.

In the procedure below, $(\Gamma_G, \Gamma_E)$ are assumed to form subtractive shares of $\Delta z$ over $\mathbb{Z}_{p-1}$ (where $z \in [B]$ is the point to be punctured), that is, $\Gamma_E + \Gamma_G = \Delta z \bmod p - 1$. When the garbler share $\Gamma_G$ is uniformly distributed, these alternative procedures yield keys $(\text{sk}, \text{psk})$ distributed identically as with the procedures $\text{F}\cdot\text{KeyGen}$ and $\text{F}\cdot\text{Punct}$. The main advantage of these alternative procedures is that if the two parties, the garbler and the evaluator, happen to have shares $(\Gamma_G, \Gamma_E)$ of $\Delta z$, then they can compute PPRF keys $\text{sk}$ and $\text{psk}$ respectively without any interaction simply by lifting their shares to the exponent of $G$.

### F.Setup*(1^λ, B)

1: $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$

2: $(\Delta, h) \leftarrow_S \mathbb{Z}_{p-1} \times \mathbb{G}, \alpha := G^\Delta \bmod p$

3: **for** $i \in [\pm B], g_i := h^{\alpha^i}$

4: $\text{mpk} := (\mathbb{G}, p, G, (g_i)_{i \in [\pm B]^*})$

5: $\text{msk} := (\text{mpk}, \Delta, g_0)$

6: **return** $(\text{mpk}, \text{msk})$

### F.KeyGen*(mpk, Γ_G)

1: **parse** $p, G$ from mpk

2: **return** $\text{sk} = G^{\Gamma_G} \bmod p$

### F.Punct*(mpk, Γ_E)

1: **parse** $p, G$ from mpk

2: **return** $\text{psk} = G^{\Gamma_E} \bmod p$

### F.PEval^H(mpk, psk, z, x, salt)

1: **parse** $(g_i)_{i \neq 0}$ from mpk

2: **return** $\text{H}(g_{x-z}^{\text{psk}}, \text{salt})$

### F.Eval^H(msk, sk, x, salt)

1: **parse** $(g_i)_{i \in [\pm B]}$ from msk

2: **return** $\text{H}(g_x^{\text{sk}}, \text{salt})$
## 3.5 Security of the Modified PPRF

We show that the modified PPRF remains selectively secure (with reusable inputs) as long as $\Gamma_E$ is statistically independent of $\Delta$. Formally, we consider the following modified selective security experiment $\text{ExpPPRF}^*(1^{\lambda}, B, b, \text{salt})$ (for an arbitrary value of salt):

**Setup Phase.** Upon receiving a setup query from $\mathcal{A}$, the challenger samples, the challenger picks $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$ and samples $\Delta, h \leftarrow \mathbb{Z}_{p-1} \times \mathbb{G}$. It sets $\alpha := G^{\Delta}$, $(g_i)_{i \in [\pm B]} := (h^{\alpha^i})_{i \in [\pm B]}$, and sends $(\mathbb{G}, p, (g_i)_{i \in [\pm B]^*})$ to $\mathcal{A}$. Ignore all further setup queries from $\mathcal{A}$.

**Challenge Phase.** Upon receiving a query (challenge, $z, \Gamma_E$) with $z \in [B]$ and $\Gamma_E \in \mathbb{Z}_{p-1}$ from $\mathcal{A}$, if $b=0$, the challenger sets $y := \text{H}(g_0^{\Gamma_E}, \text{salt})$; else, the challenger sets $y \leftarrow \text{Y}$. The challenger sends $y$ to $\mathcal{A}$.

**Definition 11 (selective security).** Fix $B = B(\lambda) \in \text{poly}(\lambda)$. We say that the modified PPRF (FSetup*, FKeyGen*, FEval, FPunct*, FPEval) is selectively secure with reusable setup if for all large enough $\lambda$ and every salt $\in S$, the advantage of any PPT adversary $\mathcal{A}$ against $\text{ExpPPRF}^*(1^{\lambda}, B, b, \text{salt})$ is negligible.

Note that by defining $\text{sk} := G^{\Gamma_E - \Delta z}$, it holds that $\text{H}(g_0^{\Gamma_E}, \text{salt}) = \text{H}(g_z^{\Gamma_E - \Delta z}, \text{salt}) = \text{F.Eval}^H(\text{msk}, \text{sk}, z, \text{salt})$, hence the case $b=0$ corresponds to the correct evaluation of the PPRF at the punctured point $z$. Security follows via a sequence of game hops similar to the proof of Theorem 9, setting $g_0$ to be either $h$ if $b=0$ or random if $b=1$, embedding a $B$-power-DDH instance, and finally invoking the tweakable correlation-robustness of $H$ for exponential correlations over $\mathbb{G}$ (where salt plays the role of the tweak; note that in this experiment, the tweak is the same for all queries). We omit the straightforward details.

We also consider a $t$-fold variant of the above experiment where the adversary received $t$ PPRF evaluations $y_i$ using different salts. Concretely, we define the $t$-instance selective security of the modified PPRF with the experiment $\textit{t-ExpPPRF}^*(1^{\lambda}, B, b, (\text{salt}_i)_{i \le t})$ below:

**Setup Phase.** Same as before: upon receiving a setup query from $\mathcal{A}$, the challenger picks $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$ and samples $\Delta, h \leftarrow \mathbb{Z}_{p-1} \times \mathbb{G}$. It sets $\alpha := G^{\Delta}$, $(g_i)_{i \in [\pm B]} := (h^{\alpha^i})_{i \in [\pm B]}$, and sends $(\mathbb{G}, p, (g_i)_{i \in [\pm B]^*})$ to $\mathcal{A}$. Ignore all further setup queries from $\mathcal{A}$.

**Challenge Phase.** Upon receiving a query (challenge, $z, \Gamma_E$) with $z \in [B]$ and $\Gamma_E \in \mathbb{Z}_{p-1}$ from $\mathcal{A}$, if $b=0$, for $i=1$ to $t$, the challenger sets $y_i := \text{H}(g_0^{\Gamma_E}, \text{salt}_i)$; else, the challenger sets $y_i \leftarrow \text{Y}$. The challenger sends $(y_1, \dots, y_t)$ to $\mathcal{A}$.

**Definition 12 (t-instance selective security).** Fix $t = t(\lambda)$ and $B = B(\lambda) \in \text{poly}(\lambda)$. We say that the modified PPRF (FSetup*, FKeyGen*, FEval, FPunct*, FPEval) is $t$-instance selectively secure with reusable setup if for all large enough $\lambda$ and every $t$-tuple of pairwise distinct $(\text{salt}_1, \dots, \text{salt}_t) \in S^t$, the advantage of any PPT adversary $\mathcal{A}$ against $\textit{t-ExpPPRF}^*(1^{\lambda}, B, b, (\text{salt}_i)_{i \le t})$ is negligible.

The security analysis is again essentially identical to the analysis in the single-instance setting, up to using the salt as (distinct) tweaks for the TCR hash function.

# 4 Modular Garbling from Power-DDH

In this section, we introduce our modular arithmetic garbling scheme from the power-DDH assumption. Our construction builds upon multiple variants of a PPRF-based VOLE-to-OLE conversion protocol, which we introduce below.

## 4.1 VOLE to OLE Conversion

Fix a security parameter $1^{\lambda}$ and a modulus $B = B(\lambda) \in \text{poly}(\lambda)$. Let $H: \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}$ be a tweakable correlation-robust hash function over $\mathbb{G}$, where $\mathbb{G}, p$ are parsed from $(\mathbb{G}, p, g, G) := \text{GrpGen}^*$ (note that this is a deterministic algorithm).

Let $(mpk, msk) \leftarrow \text{FSetup}^*(1^{\lambda}, B)$. Let $v_{\mathbb{G}} \in \mathbb{Z}_{p-1}$ denote an element of $\mathbb{Z}_{p-1}$ known to the garbler $\mathbb{G} \ v_{\mathcal{E}} \in [B]$ denote a value known to the evaluator $\mathcal{E}$. In this section, we introduce a single-message
deterministic conversion protocol, called VtO, that converts additive shares $(\langle \Delta v_E \rangle_G, \langle \Delta v_E \rangle_E)$ of $\Delta v_E$ over $\mathbb{Z}_{p-1}$ (where $\Delta \in \mathbb{Z}_{p-1}$ is the second component of msk $:= (\text{mpk}, \Delta, g_0)$) to $\mathbb{Z}_{p-1}$-shares $(\langle v_G v_E \rangle_G, \langle v_G v_E \rangle_E) \in \mathbb{Z}_{p-1}^2$ of $v_G v_E$, using the PPRF with reusable inputs of the previous section.

VtO<sub>G</sub><sup>H</sup>(msk, v<sub>G</sub>, ⟨Δv<sub>E</sub>⟩<sub>G</sub>, salt)

1: sk := F.KeyGen*(mpk, ⟨Δv<sub>E</sub>⟩<sub>G</sub>)

2: (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub>) := (−v<sub>G</sub>, 0)

3: **for** x ∈ [B]

4: y<sub>x</sub> := F.Eval<sup>H</sup>(msk, sk, x, salt)

5: shift := shift + y<sub>x</sub> mod p − 1

6: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> := ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> + x · y<sub>x</sub> mod p − 1

7: **return** (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub>)

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

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

2: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> := −v<sub>E</sub> · shift mod p − 1

3: **for** x ∈ [B] \ {v<sub>E</sub>

4: y<sub>x</sub> := F.PEval<sup>H</sup>(mpk, psk, v<sub>E</sub>, x, salt)

5: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> := ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> + (v<sub>E</sub> − x) · y<sub>x</sub> mod p − 1

6: **return** ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>

**Correctness and security.** We require the above procedures to satisfy the following correctness and security properties:

**Definition 13 (Correctness and security of VtO<sup>H</sup>).*

- Correctness. For every (mpk, msk) in the support of F.setup*(1<sup>λ</sup>, B), denoting msk := (mpk, Δ, g<sub>0</sub>), for any v<sub>G</sub> ∈ Z<sub>p−1</sub>, v<sub>E</sub> ∈ [B], any ⟨Δv<sub>E</sub>⟩<sub>G</sub> ∈ Z<sub>p−1</sub>, and any salt salt, denoting ⟨Δv<sub>E</sub>⟩<sub>E</sub> := Δv<sub>E</sub> − ⟨Δv<sub>E</sub>⟩<sub>G</sub> mod p − 1 and

$$ (\text{shift}, \langle v_G v_E \rangle_G) := \text{VtO}_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt}) $$

$$ \langle v_G v_E \rangle_E := \text{VtO}_E^H(\text{mpk}, v_E, \langle \Delta v_E \rangle_G, \text{salt}, \text{shift}), $$

it holds that $\langle v_G v_E \rangle_G + \langle v_G v_E \rangle_E = v_G v_E \mod p - 1$.

- t-instance security. For any t-tuple of pairwise distincts salts salt = (salt<sub>1</sub>, ..., salt<sub>t</sub>), the advantage of any stateful polynomial-time adversary A against the experiment ExpVtO<sup>H</sup> defined below is negligible.

In the experiments below, we assume that A is deterministic; by a standard averaging argument, this is without loss of generality. At the end of the experiment, A outputs a guess b.

ExpVtO<sub>0</sub><sup>H</sup>(1<sup>λ</sup>, B, salt)

1: (mpk, msk) ←$ F.setup*(1<sup>λ</sup>, B)

2: i := 1

3: Upon receiving (v<sub>G</sub>, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>) from A(mpk):

4: i := i + 1; **if** i > t **return** ⊥

5: ⟨Δv<sub>E</sub>⟩<sub>G</sub> := ⟨Δv<sub>E</sub>⟩<sub>E</sub> − Δv<sub>E</sub> mod p − 1

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

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

8: **return** (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>)

ExpVtO<sub>1</sub><sup>H</sup>(1<sup>λ</sup>, B, salt)

1: (mpk, msk) ←$ F.setup*(1<sup>λ</sup>, B)

2: Upon receiving (v<sub>G</sub>, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>) from A(mpk):

3: i := i + 1; **if** i > t **return** ⊥

4: **shift** ←$ \mathbb{Z}_{p-1}$

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

6: **return** (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>)

Correctness and Security of VtO<sup>H</sup>.

**Correctness.** Let (mpk, msk) ←$ F.setup*(1<sup>λ</sup>, B)$ with msk := (mpk, Δ, g<sub>0</sub>), let v<sub>G</sub>, v<sub>E</sub> ∈ [±B] and let $(\langle \Delta v_E \rangle_G, \langle \Delta v_E \rangle_E)$ be two elements of $\mathbb{Z}_{p-1}$ such that $\langle \Delta v_E \rangle_G + \langle \Delta v_E \rangle_E = \Delta v_E \mod p - 1$. Consider the outputs (msg, $\langle v_G v_E \rangle_G$) of VtO<sub>G</sub><sup>H</sup>(msk, v<sub>G</sub>, $\langle \Delta v_E \rangle_G$) and $\langle v_G v_E \rangle_E$ of VtO<sub>G</sub><sup>H</sup>(mpk, v<sub>E</sub>, $\langle \Delta v_E \rangle_G$, msg), and parse msg := (shift, salt). We have:
$$
\begin{align*}
\langle v_G v_E \rangle_E &= -v_E \cdot \text{shift} + \sum_{x \in [\pm B] \setminus \{v_E\}} (v_E - x) \cdot \text{F.Eval}^H(\text{mpk}, \text{psk}, v_E, x, \text{salt}) \bmod p - 1 \\
&= -v_E \cdot \text{shift} + \sum_{x \in [\pm B] \setminus \{v_E\}} (v_E - x) \cdot \text{F.Eval}^H(\text{msk}, \text{sk}, x, \text{salt}) \bmod p - 1 \quad \text{by PPRF security} \\
&= -v_E \cdot \text{shift} + \sum_{x \in [\pm B]} (v_E - x) \cdot \text{F.Eval}^H(\text{msk}, \text{sk}, x, \text{salt}) \bmod p - 1 \quad \text{as } v_E - v_E = 0 \\
&= -v_E \cdot \text{shift} + v_E \cdot \sum_{x \in [\pm B]} \text{F.Eval}^H(\text{msk}, \text{sk}, x, \text{salt}) - \sum_{x \in [\pm B]} x \cdot \text{F.Eval}^H(\text{msk}, \text{sk}, x, \text{salt}) \bmod p - 1 \\
&= -v_E \cdot \text{shift} + v_E \cdot (\text{shift} + v_G) - \langle v_G v_E \rangle_G \bmod p - 1 \\
&= v_G v_E - \langle v_G v_E \rangle_G \bmod p - 1.
\end{align*}
$$

**Security.** Fix *t* pairwise distinct salts *salt*. We argue security through a sequence of game hops:

**Game 0.** This is the experiment $\text{ExpVtO}_0^H(1^\lambda, B, \text{salt})$.

**Game 1.** In this game, we modify the algorithm $\text{VtO}_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt}_i)$:

- On line 1 we additionally compute $\text{psk} := \text{F.Punct}^*(\text{mpk}, \langle \Delta v_E \rangle_E)$.

- On line 4 we instead compute $y_x$ as $y_x := \text{F.PEval}^H(\text{mpk}, \text{psk}, v_E, x, \text{salt}_i)$ for every $x \neq v_E$. For $x = v_E$, $y_x$ is still computed as $\text{F.Eval}^H(\text{msk}, \text{sk}, x, \text{salt}_i)$.

By (perfect) correctness of the PPRF, this game is perfectly indistinguishable from the previous one.

**Game 2.** In this game, we modify again $\text{VtO}_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt}_i)$ for $i = 1$ to $t$: on line 4, we set instead $y_{v_E} \leftarrow \$ Z_{p-1}$. Under the *t*-instance selective security of the PPRF (Definition 12), this game is indistinguishable from the previous one. Note that the value shift output by the modified $\text{VtO}_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt}_i)$ satisfies:

$$ \text{shift} = y_{v_E} + \sum_{x \neq v_E} y_x - v_G \bmod p - 1. $$

Since all $y_{v_E}$ for $i = 1$ to $t$ are sampled uniformly at random (independently of $v_G$ and $(y_x)_{x \neq 0}$), it follows that the marginal distribution of all $t$ shifts *shift* is the uniform distribution over $(Z_{p-1})^t$.

**Game 3.** This is the experiment $\text{ExpVtO}_1^H(1^\lambda, B, \text{salt})$. The difference with the previous game is that *shift* is sampled uniformly from $Z_{p-1}$ for $i = 1$ to $t$. As the marginal distribution of all shifts in Game 2 is already uniform over $(Z_{p-1})^t$, this is a purely syntactic change and this game is perfectly indistinguishable from Game 2. This concludes the proof. ■

## 4.2 Modular reduction of authenticated shares

We observe that the correctness and security analysis above remains identical if the parties replace $y_x$ with $f(y_x)$, for an arbitrary function $f$, in the $\text{VtO}^H$ procedures. Concretely, consider the following “functional” variants where $f: Z_{p-1} \to Z_{p-1}$ is an arbitrary efficient function:

$\text{fVtO}_G^H(\text{msk}, v_G, \langle \Delta v_E \rangle_G, \text{salt}, f)$

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

2: (shift, $\langle v_G v_E \rangle_G$) := $(-v_G, 0)$

3: for $x \in [B]$

4: $y_x := \text{F.Eval}^H(\text{msk}, \text{sk}, x, \text{salt})$

5: shift := shift + $y_x \bmod p - 1$

6: $\langle v_G v_E \rangle_G := \langle v_G v_E \rangle_G + f(x) \cdot y_x \bmod p - 1$

7: return (shift, $\langle v_G \cdot f(v_E) \rangle_G$)

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

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

2: $\langle v_G v_E \rangle_G := -f(v_E) \cdot \text{shift} \bmod p - 1$

3: for $x \in [B] \setminus \{v_E\}$

4: $y_x := \text{F.PEval}^H(\text{mpk}, \text{psk}, v_E, x, \text{salt})$

5: $\langle v_G v_E \rangle_E := \langle v_G v_E \rangle_E + (f(v_E) - f(x)) \cdot y_x \bmod p - 1$

6: return $\langle v_G \cdot f(v_E) \rangle_E$

The same correctness analysis as before shows that with probability 1, it holds that $\langle v_G \cdot f(v_E) \rangle_G + \langle v_G \cdot f(v_E) \rangle_E = v_G \cdot f(v_E) \bmod p - 1$. We use this observation below to define a procedure that lets two parties compute modular reductions inside authenticated shares.
**The MR procedure.** Fix a security parameter $1^{\lambda}$ and two moduli $B = B(\lambda) \in \text{poly}(\lambda)$ and $B' = B'(\lambda) \in \text{poly}(\lambda)$ with $B' > B$. Let $H: \mathbb{G} \times \{0, 1\}^* \to \mathbb{Z}_{p-1}$ be a TCR hash function for exponential correlations over $\mathbb{G}$. Let $(mpk', msk') \leftarrow \$ F.\text{Setup}^*(1^{\lambda}, B')$ and parse $(mpk', \Delta', g_0) := \text{msk}$. Let $\tilde{v}_E \in [B']$ denote a value known to the evaluator E. In this section, we introduce one more procedure to convert, using our PPRF and via a single-message deterministic protocol called MR (for Modular Reduction), $\mathbb{Z}_{p-1}$-shares $(\langle \Delta' \tilde{v}_E \rangle_G, \langle \Delta' \tilde{v}_E \rangle_E)$ of $\Delta' \tilde{v}_E$ to $\mathbb{Z}_{p-1}$-shares $(\langle \Delta'' v_E \rangle_G, \langle \Delta'' v_E \rangle_E)$ of the value $\Delta'' v_E = \Delta'' \cdot [\tilde{v}_E \text{ mod } B]$. That is, $\langle \Delta'' v_E \rangle_G + \langle \Delta'' v_E \rangle_E = \Delta'' \cdot [\tilde{v}_E \text{ mod } B] \text{ mod } p - 1$. Looking ahead, $\Delta''$ will be set in our protocol to be the "$\Delta$ component" of another PPRF secret key $msk''$.

$\text{MR}_{\text{G}}^{\text{H}}(\text{msk}', \Delta'', \langle \Delta' \tilde{v}_E \rangle_{\text{G}}, \text{salt}, B)$

1: parse $(mpk', \Delta', g_0) := \text{msk}'$

2: define $f: x \mapsto [x \text{ mod } B]$

3: (shift, $\langle \Delta'' \cdot v_E \rangle_G) := \text{fVtO}_{\text{G}}^{\text{H}}(\text{msk}', \Delta', \langle \Delta' \tilde{v}_E \rangle_{\text{G}}, \text{salt}, f)$

4: return (shift, $\langle v_G \cdot v_E \rangle_G$)

$\text{MR}_{\text{E}}^{\text{H}}(\text{mpk}', \tilde{v}_E, \langle \Delta' v_E \rangle_{\text{E}}, \text{salt}, \text{shift}, B)$

1: define $f: x \mapsto [x \text{ mod } B]$

2: $\langle v_G \cdot v_E \rangle_E := \text{fVtO}_{\text{E}}^{\text{H}}(\text{mpk}', \tilde{v}_E, \langle \Delta' \tilde{v}_E \rangle_{\text{E}}, \text{salt}, f)$

3: return $\langle \Delta'' \cdot v_E \rangle_E$

The above procedure lets two parties compute, given $(\langle \Delta' \tilde{v}_E \rangle_G, \langle \Delta' \tilde{v}_E \rangle_E)$, shares of $\Delta'' \cdot [\tilde{v}_E \text{ mod } B]$ mod $p-1$ using the functional VOLE-to-OLE procedure, where $\mathbb{G}$ sets its OLE input $v_G$ to $\Delta''$ and the parties use the modular reduction function $f: x \mapsto [x \text{ mod } B]$. Note that we run the setup $(mpk', msk') \leftarrow \$ F.\text{Setup}^*(1^{\lambda}, B')$ using a larger modulus $B' > B$. Looking ahead, we use this procedure to shrink back labels in our garbling scheme to values in $[B]$ after their size has been increased (but remains bounded by $B'$) through computations over the integers.

**Security.** We define security using a slight modification of the ExpVtO to account for the function $f$ and for the fact that we fix $v_G$ to $\Delta$ (hence we don't let the adversary choose it).

$\text{ExpMR}_{0}^{\text{H}}(1^{\lambda}, B', B, \text{salt})$

1: $(mpk', msk') \leftarrow \$ F.\text{Setup}^*(1^{\lambda}, B')$

2: $i := 1$

3: Upon receiving $(\Delta'', \tilde{v}_E, \langle \Delta' \tilde{v}_E \rangle_E)$ from $\mathcal{A}(mpk')$:

4: $i := i + 1$; if $i > t$ return $\perp$

5: $\langle \Delta' \tilde{v}_E \rangle_G := \langle \Delta' \tilde{v}_E \rangle_E - \Delta' \tilde{v}_E \text{ mod } p - 1$

6: $(\text{shift}, \langle \Delta'' v_E \rangle_G) := \text{MR}_{\text{G}}^{\text{H}}(\text{msk}', \Delta'', \langle \Delta' \tilde{v}_E \rangle_{\text{G}}, \text{salt}_i, B)$

7: $\langle \Delta'' v_E \rangle_E := \text{MR}_{\text{E}}^{\text{H}}(\text{mpk}', \tilde{v}_E, \langle \Delta' \tilde{v}_E \rangle_{\text{E}}, \text{shift})$

8: return (shift, $\langle \Delta'' v_E \rangle_E$)

$\text{ExpMR}_{1}^{\text{H}}(1^{\lambda}, B', B, \text{salt})$

1: $(mpk', msk') \leftarrow \$ F.\text{Setup}^*(1^{\lambda}, B')$

2: $i := 1$

3: Upon receiving $(\Delta'', \tilde{v}_E, \langle \Delta' \tilde{v}_E \rangle_E)$ from $\mathcal{A}(mpk')$:

4: $i := i + 1$; if $i > t$ return $\perp$

5: shift $\leftarrow \$ \mathbb{Z}_{p-1}$

6: $\langle \Delta'' v_E \rangle_E := \text{MR}_{\text{E}}^{\text{H}}(\text{mpk}', \tilde{v}_E, \langle \Delta' \tilde{v}_E \rangle_{\text{E}}, \text{salt}_i, \text{shift}, B)$

7: return (shift, $\langle \Delta'' v_E \rangle_E$)

**Definition 14 (Security of MR).** We say that MR is *t*-instance secure *if* for any $B < B'$ and any *t*-tuple of pairwise distinct salts *salt*, the advantage of any stateful polytime adversary $\mathcal{A}$ against the experiment $\text{ExpMR}^{\text{H}}$ defined above is negligible.

The security analysis is an immediate adaptation of the security analysis of ExpVtO and we omit it.

## 4.3 Leaky VOLE to OLE Conversion

We introduce another variant of the VtO procedure, called LVtO, with the following characteristics:

- LVtO is a single-message conversion protocol where the garbler holds an input $v_G \in [B]$. LVtO converts additive shares of $\Delta v_E$ (over $\mathbb{Z}_{p-1}$) into additive shares of $v_G v_E$ over the integers.

- The LVtO procedure produces small integer shares: the output shares $(\langle v_G v_E \rangle_G, \langle v_G v_E \rangle_E)$ are guaranteed to belong to $[\lambda B^3]$.

- This combination of sharing over the integers and achieving a small share size comes at a cost in security: with probability $1/\lambda$, the procedure LVtO leaks information about $v_G$ to the evaluator (in a sense that will be made precise).

Fix a security parameter $1^{\lambda}$ and a modulus $B = B(\lambda) \in \text{poly}(\lambda)$. Let $H': \mathbb{G} \times \{0, 1\}^{\lambda} \to [\lambda \cdot B]$ be a tweakable correlation-robust hash function for exponential correlations over $\mathbb{G}$. Let $(mpk, msk) \leftarrow \$ F.\text{Setup}^*(1^{\lambda}, B)$. Let $v_G, v_E \in [B]$ denote two values known to the garbler $G$ and the evaluator $E$ respectively.
LVtO<sub>G</sub><sup>H'</sup> (msk, v<sub>G</sub>, ⟨Δv<sub>E</sub>⟩<sub>G</sub>, salt)

1: sk := F.KeyGen*(mpk, ⟨Δv<sub>E</sub>⟩<sub>G</sub>)

2: (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub>) := (−v<sub>G</sub>, 0)

3: **for** x ∈ [B]

4: y<sub>x</sub> := F.EvalH'(msk, sk, x, salt)

5: shift := shift + y<sub>x</sub>

6: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> := ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> + x · y<sub>x</sub>

7: **return** (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub>)

LVtO<sub>E</sub><sup>H'</sup> (mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt, shift)

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

2: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> := −v<sub>E</sub> · shift

3: **for** x ∈ [B] \ {v<sub>E</sub>

4: y<sub>x</sub> := F.PEvalH'(mpk, psk, v<sub>E</sub>, x, salt)

5: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> := ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> + (v<sub>E</sub> − x) · y<sub>x</sub>

6: **return** ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>

**Correctness and efficiency.** We define correctness as for VtO. The same analysis as in Section 4.1 shows that ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> + ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> = v<sub>G</sub>v<sub>E</sub> (over the integers) with probability 1. In the procedures above, it holds that y<sub>x</sub> ∈ [λ · B] for every x ∈ [B]. Since ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> = ∑<sub>x∈[B]</sub> x · y<sub>x</sub> and ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> = ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub> − v<sub>G</sub>v<sub>E</sub>, we have |⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub>| ≤ λ · B<sup>2</sup>(B − 1)/2 ≤ λ · B<sup>3</sup>/2, and |⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>| ≤ λB<sup>2</sup>(B − 1)/2 + B<sup>2</sup> ≤ λ · B<sup>3</sup>/2.

**Security.** To define multi-instance security, we introduce below a modified experiment ExpLVtO. Compared to ExpVtO<sub>1</sub>, the simulated experiment ExpLVtO<sub>1</sub> tosses a biased coin σ ←$ Ber(1/λ). With probability 1 − 1 /λ, it samples shift independently of v<sub>G</sub> (no leakage occurred). With probability 1 /λ, it samples shift from a distribution that depends on v<sub>G</sub> (a leakage occurred).

The distribution of the simulated shifts in ExpLVtO<sub>1</sub> are a bit more involved compared to ExpVtO<sub>1</sub> (where shift is simply simulated as shift ←$ Z<sub>p−1</sub>). For convenience, we define two algorithms SimShift and SimLShift that simulate shift in the case where no leakage occurs (σ = 0) and where leakage occurs (σ = 1) respectively:

SimShift<sup>H'</sup> (mpk, psk, v<sub>E</sub>, salt)

1: shift ←$ [(λ − 1) · B]

2: **for** x ∈ [B] \ {v<sub>E</sub>

3: shift := shift + F.PEvalH'(mpk, psk, v<sub>E</sub>, x, salt)

4: **return** shift

SimLShift<sup>H'</sup> (mpk, psk, v<sub>G</sub>, v<sub>E</sub>, salt)

1: shift ←$ [−v<sub>G</sub>, λB − v<sub>G</sub>] \ [(λ − 1) · B]

2: **for** x ∈ [B] \ {v<sub>E</sub>

3: shift := shift + F.PEvalH'(mpk, psk, v<sub>E</sub>, x, salt)

4: **return** shift

**Definition 15 (t-instance security of LVtO<sup>H'</sup>).* For all large enough λ, all v<sub>E</sub> ∈ [B] and pairwise-distinct t-tuple of salts salt = (salt<sub>1</sub>, ..., salt<sub>t</sub>), the advantage of any polynomial-time stateful adversary A against ExpLVtO<sup>H'</sup>(1<sup>λ</sup>, B, salt) is negligible.

ExpLVtO<sub>0</sub><sup>H'</sup> (1<sup>λ</sup>, B, salt)

1: (mpk, msk) ←$ F Gibbition* (1<sup>λ</sup>, B)

2: i := 1

3: Upon receiving ⟨v<sub>G</sub>, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>⟩ from A (mpk):

4: i := i + 1; **if** i > t **return** ⊥

5: ⟨Δv<sub>E</sub>⟩<sub>G</sub> := ⟨Δv<sub>E</sub>⟩<sub>E</sub> − Δv<sub>E</sub> mod p − 1

6: (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>G</sub>) := LVtO<sub>G</sub><sup>H'</sup> (msk, v<sub>G</sub>, ⟨Δv<sub>E</sub>⟩<sub>G</sub>, salt<sub>i</sub>)

7: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> := LVtO<sub>E</sub><sup>H'</sup> (mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt<sub>i</sub>, shift)

8: **return** (shift, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>)

ExpLVtO<sub>1</sub><sup>H'</sup> (1<sup>λ</sup>, B, salt)

1: (mpk, msk) ←$ F Gibbition* (1<sup>λ</sup>, B)

2: i := 1

3: Upon receiving ⟨v<sub>G</sub>, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>⟩ from A (mpk):

4: i := i + 1; **if** i > t **return** ⊥

5: σ<sub>i</sub> ←$ Ber(1 /λ)<sup>t</sup>

6: shift<sub>0</sub> ←$ SimShift<sup>H'</sup> (mpk, psk, v<sub>E</sub>, salt<sub>i</sub>)

7: shift<sub>1</sub> ←$ SimLShift<sup>H'</sup> (mpk, psk, v<sub>G</sub>, v<sub>E</sub>, salt<sub>i</sub>)

8: ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub> := LVtO<sub>E</sub><sup>H'</sup> (mpk, v<sub>E</sub>, ⟨Δv<sub>E</sub>⟩<sub>E</sub>, salt<sub>i</sub>, shift)

9: **return** (shift<sub>σ<sub>i</sub></sub>, ⟨v<sub>G</sub>v<sub>E</sub>⟩<sub>E</sub>)

The proof of correctness is identical to the previous section; we argue security below:

*Proof of Security of LVtO<sup>H'</sup>*, Section 4.3. Fix any t-tuple of salts salt.

**Game 0.** This is the experiment ExpLVtO<sub>0</sub><sup>H</sup>(1<sup>λ</sup>, B, salt).

**Game 1.** In this game, we modify the algorithm LVtO<sub>G</sub><sup>H'</sup> (msk, v<sub>G</sub>, ⟨Δv<sub>E</sub>⟩<sub>G</sub>, salt<sub>i</sub>):

– On line 1 we additionally compute psk := F.Punct*(mpk, ⟨Δv<sub>E</sub>⟩<sub>E</sub>).
- On line 4, for $i = 1$ to $t$, we instead compute $y_x$ as $y_x := \text{F.Eval}^{H'}(\text{mpk}, \text{psk}, v_E, x, \text{salt}_i)$ for every $x \neq v_E$. For $x = v_E$, $y_x$ is still computed as $\text{F.Eval}^{H}(\text{msk}, \text{sk}, x, \text{salt}_i)$.

By (perfect) correctness of the PPRF, this game is perfectly indistinguishable from the previous one.

**Game 2.** In this game, we further modify $\text{LVtO}_G^{H'}(\text{msk}, v_G, \langle\Delta v_E\rangle_G, \text{salt}_i)$ for $i = 1$ to $t$: on line 4, we set instead $y_{v_E} \leftarrow \$[\lambda \cdot B]$. Under the $t$-instance selective security of the PPRF (Definition 12), this game is indistinguishable from the previous one. Note that the value shift output by the modified $\text{LVtO}_G^{H'}(\text{msk}, v_G, \langle\Delta v_E\rangle_G, \text{salt}_i)$ satisfies:

$$ \text{shift} = y_{v_E} - v_G + \sum_{x \neq v_E} y_x. $$

In this equation, $y_{v_E}$ is sampled uniformly at random from $[\lambda \cdot B]$ (independently for all iterations $i = 1$ to $t$). Equivalently, $\text{shift} = z + \sum_{x \neq v_E} y_x$ where $z := y_{v_E} - v_G$ is sampled uniformly at random from $[-v_G, \lambda \cdot B - v_G]$. Before we proceed, we prove a simple claim:

$$ \text{Claim.} \quad \Pr[z \notin [(\lambda - 1) \cdot B]] = 1/\lambda. $$

$$ \text{Proof.} \quad \Pr[z \notin [(\lambda - 1) \cdot B]] = \Pr[z \in [-v_G, 0)] + \Pr[z \in ((\lambda - 1)B, \lambda B - v_G]] = \frac{v_G}{\lambda B} + \frac{B - v_G}{\lambda B} = \frac{1}{\lambda}. \quad \blacksquare $$

**Game 3.** In this experiment, upon receiving each query from $\mathcal{A}$ for $i = 1$ to $t$, we sample $z$ differently: we first pick $\sigma_i \leftarrow \$ \text{Ber}(1/\lambda)$. If $\sigma_i = 0$ (which happens with probability $1 - 1/\lambda$), we sample $z \leftarrow \$ [(\lambda - 1) \cdot B]$. Else, ($\sigma_i = 1$, probability $1/\lambda$) we sample $z \leftarrow \$ [-v_G, \lambda B - v_G] \setminus [(\lambda - 1) \cdot B]$. Note that by the claim above, this induces exactly the same distribution as sampling $z \leftarrow \$ [-v_G, \lambda B - v_G]$ (where a leakage occurs if $z \notin [(\lambda - 1) \cdot B]$), hence this game is perfectly indistinguishable from Game 2. This game corresponds exactly to $\text{ExpLVtO}_0^{H}(1^{\lambda}, B, v_E, \text{salt})$; this concludes the proof.

■

**Remark 16.** Multi-instance security allows running multiple $\text{LVtO}$ instances in parallel using the same pair $(\text{mpk}, \text{msk})$. We note that the same analysis of multi-instance security immediately extends to show that security is preserved when running concurrently both $\text{VtO}$ and $\text{LVtO}$ instances using the same pair $(\text{mpk}, \text{msk})$. We state below the corresponding experiment (denoted $\text{ExpBothVtO}$) for completeness and introduce the corresponding security notion in Definition 17, but omit the proof, which remains essentially identical.

**Definition 17 (t-instance joint security of $\text{VtO}^H$, $\text{LVtO}^{H'}$).** For all large enough $\lambda$, all $v_E \in [B]$ and pairwise-distinct $t$-tuple of salts salt = $(\text{salt}_1, \dots, \text{salt}_t)$, the advantage of any polynomial-time stateful adversary $\mathcal{A}$ against $\text{ExpBothVtO}^{H,H'}(1^{\lambda}, B, \text{salt})$ is negligible.

$\text{ExpBothVtO}_0^{H,H'}(1^{\lambda}, B, \text{salt})$

1: $(\text{mpk}, \text{msk}) \leftarrow \$ \text{F Gibb}(1^{\lambda}, B)$

2: $i := 1$

3: Upon receiving $(\text{VtO}, v_G, v_E, \langle\Delta v_E\rangle_E)$ from $\mathcal{A}(\text{mpk})$:

4: $i := i + 1$; **if** $i > t$ **return** $\perp$

5: $\langle\Delta v_E\rangle_G := \langle\Delta v_E\rangle_E - \Delta v_E \mod p - 1$

6: $(\text{shift}, \langle v_G v_E\rangle_G) := \text{LVtO}_G^{H'}(\text{msk}, v_G, \langle\Delta v_E\rangle_G, \text{salt}_i)$

7: $\langle v_G v_E\rangle_E := \text{LVtO}_E^{H'}(\text{mpk}, v_E, \langle\Delta v_E\rangle_E, \text{salt}_i, \text{shift})$

8: **return** $(\text{shift}, \langle v_G v_E\rangle_E)$

9: Upon receiving $(\text{LVtO}, v_G, v_E, \langle\Delta v_E\rangle_E)$ from $\mathcal{A}(\text{mpk})$:

10: $i := i + 1$; **if** $i > t$ **return** $\perp$

11: $\langle\Delta v_E\rangle_G := \langle\Delta v_E\rangle_E - \Delta v_E \mod p - 1$

12: $(\text{shift}, \langle v_G v_E\rangle_G) := \text{LVtO}_G^{H'}(\text{msk}, v_G, \langle\Delta v_E\rangle_G, \text{salt}_i)$

13: $\langle v_G v_E\rangle_E := \text{LVtO}_E^{H'}(\text{mpk}, v_E, \langle\Delta v_E\rangle_E, \text{salt}_i, \text{shift})$

14: **return** $(\text{shift}, \langle v_G v_E\rangle_E)$

$\text{ExpBothVtO}_1^{H,H'}(1^{\lambda}, B, \text{salt})$

1: $(\text{mpk}, \text{msk}) \leftarrow \$ \text{F Gibb}(1^{\lambda}, B)$

2: $i := 1$

3: Upon receiving $(\text{VtO}, v_G, v_E, \langle\Delta v_E\rangle_E)$ from $\mathcal{A}(\text{mpk})$:

4: $i := i + 1$; **if** $i > t$ **return** $\perp$

5: **shift** $\leftarrow \$ \mathbb{Z}_{p-1}$

6: $\langle v_G v_E\rangle_E := \text{LVtO}_E^{H'}(\text{mpk}, v_E, \langle\Delta v_E\rangle_E, \text{salt}_i, \text{shift})$

7: **return** $(\text{shift}, \langle v_G v_E\rangle_E)$

8: Upon receiving $(\text{LVtO}, v_G, v_E, \langle\Delta v_E\rangle_E)$ from $\mathcal{A}(\text{mpk})$:

9: $i := i + 1$; **if** $i > t$ **return** $\perp$

10: $\sigma_i \leftarrow \$ \text{Ber}(1/\lambda)^t$

11: $\text{shift}_0 \leftarrow \$ \text{SimShift}^{H'}(\text{mpk}, \text{psk}, v_E, \text{salt}_i)$

12: $\text{shift}_1 \leftarrow \$ \text{SimShift}^{H'}(\text{mpk}, \text{psk}, v_G, v_E, \text{salt}_i)$

13: $\langle v_G v_E\rangle_E^i := \text{LVtO}_E^{H'}(\text{mpk}, v_E, \langle\Delta v_E\rangle_E, \text{salt}_i, \text{shift})$

14: **return** $(\text{shift}_{\sigma_i}, \langle v_G v_E\rangle_E)$
## 4.4 The Garbling Scheme

Equipped with the procedures introduced in the previous sections, we are now ready to present our garbling scheme for modular arithmetic circuit. Let $\lambda$ be a security parameter and $B = B(\lambda) \in \text{poly}(\lambda)$ be a polynomial-size modulus. We consider a polynomial-size arithmetic circuit $C$ over $\mathbb{Z}_B$ with $n$ inputs, $m$ outputs, $s$ gates (additions, subtractions, and multiplications), of depth $D$. We let $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$), and $\text{depth}(C)$ to denote its depth (the length of the longest path from an input to an output).

**Theorem 18.** Let $B = B(\lambda) \in \text{poly}(\lambda)$ be a polynomial-size modulus. Let $C = \{C_\lambda\}_{\lambda \in \mathbb{N}}$ denote the class of all polynomial-size arithmetic circuits over the ring $\mathbb{Z}_B$. Let $c = c(\lambda)$ denote a function such that $c = \omega(1)$, and set $B' := B^2 + c \cdot \lambda \cdot B^3$. Assume that the $B'$-power-DDH assumption holds over a group $(\mathbb{G}, p, g) := \text{GrpGen}(1^\lambda)$ of order $p = 2^{O(\lambda)}$ and that $H$ is a tweakable correlation-robust hash function for exponential correlations over $\mathbb{G}$. Then there exists an arithmetic garbling scheme $\text{AGC} = (\text{AGC.Garble}, \text{AGC.Eval})$ for $C$ where, on input $(1^\lambda, C)$ with $C \in C_\lambda$, $\text{AGC.Garble}$ outputs a garbled circuit $\hat{C}$ of size

$$|\hat{C}| = O(\lambda \cdot |C| + \lambda B' \cdot \text{depth}(C)).$$

In particular, the rate of the scheme approaches $O(\log B/\lambda)$ when $\text{depth}(C) \ll |C|$.

More concretely, the garbled circuit $\hat{C}$ contains a “header” of size $(B + B') \cdot \log p \cdot \text{depth}(C)$ and garbled gates $\hat{C}_\gamma$, where $\hat{C}_\gamma = 3 \log p$ for addition/subtraction gates, and $\hat{C}_\gamma \le 3 \log p + 2 \cdot (\log \lambda + 3 \log B + 2 \log p + 2 \log c)$ for multiplication gates. The result of Theorem 18 represents a logarithmic improvement in rate compared with the state of the art: our scheme achieves asymptotic rate $\Omega(\log \lambda)/\lambda$, while the best known arithmetic garbling scheme for modular arithmetic is the scheme of [Hea24], which achieves asymptotic rate $O(1/\lambda)$.

**Remark 19.** The dependency in $\text{depth}(C)$ in Theorem 18 stems from the fact that our construction is leveled: $\text{AGC.Garble}$ samples fresh PPRF master keys $\text{mpk}_d$ at each level $d \le \text{depth}(C)$. This leveled construction allows us to avoid circularity, by ensuring that PPRF evaluations at a given level $d$ are always used to mask values that depend on $\text{msk}_d'$ for $d' > d$. The dependency can be removed at the cost of assuming a non-standard circular variant of tweakable correlation-robustness. Concretely, fix a hash $H$. Let $(g_i)_{i \in [\pm B')] \leftarrow \mathcal{D}_0$, where $\mathcal{D}_0$ is the power-DDH distribution of Definition 3 with bound $B'$, and let $(\alpha, h) \in \mathbb{Z}_p^* \times \mathbb{G}$ be such that $g_i = h^{\alpha^i}$ for all $i \in [\pm B']$. Then the “circular $B'$-power-DDH assumption” states that no PPT adversary $\mathcal{A}$ (who receives the $g_i$ for $i \ne 0$ as input) can, given at most $t$ samples of the form $H(g_0^u, \text{salt}) + \alpha v$, for queries $(u, v, \text{salt})$ of his choice with distinct salts, distinguish the samples from random. In a follow-up work [CHHK25], we showed that this assumption holds unconditionally in the generic group model when $H$ is additionally modeled as a random oracle. Under this assumption, the $2\text{depth}(C)$ different $\Delta$'s in our construction can be replaced with a single global $\Delta$.

**Garbling algorithm** We represent on Algorithm 1 the garbling algorithm $\text{AGC.Garble}(1^\lambda, C)$. The garbling algorithm maintains the following invariant: for every wire $w$ at depth $d$ of $C$, the garbler constructs a wire key $(k_w, K_w) \in \mathbb{Z}_B \times \mathbb{Z}_{p-1}$. $\text{AGC.Garble}$ outputs a global keys $\Delta_1$, a set of wire keys $\hat{K} = (k_w, K_w)_{w \in W(C)}$, and a garbled circuit $\hat{C}$. Given a wire value $x_w \in \mathbb{Z}_B$ at depth $d$, the corresponding wire label is defined as $(\ell_w, L_w) := (x_w - k_w \text{ mod } B, \Delta_d \cdot \ell_w - K_w \text{ mod } p - 1)$.

**Definition 20.** We let InputLabels denote the function which, on input $(1^\lambda, C, \Delta_1, \hat{K}, x)$, outputs $(\ell_i, L_i) := (x_i - k_i \text{ mod } B, \Delta_1 \cdot x_i - K_i \text{ mod } p - 1)_{i \in I(C)}$.

**Algorithm Modular Garbling from Power-DDH: $\text{AGC.Garble}(1^\lambda, C)$**

**Parameters.** Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^\lambda)$. Let $c = c(\lambda)$ denote a function $c = \omega(1)$, and set $B' := B^2 + c \cdot \lambda \cdot B^3$. Let $H: \mathbb{G} \to \mathbb{Z}_{p-1}$ and $H': \mathbb{G} \times \{0, 1\}^* \to [\lambda \cdot B]$ denote TCR hash functions for exponential correlations over $\mathbb{G}$. Let $F = (\text{F Gibb}, \text{F KeyGen}^*, \text{F Eval}, \text{F Punct}^*, \text{F PEval})$ denote the modified PPRF of Section 3.4.
**Initialization.** For $d=1$ to $D$,

- sample $(mpk_d, msk_d) \leftarrow \text{FSetup}(1^{\lambda}, B)$. Parse $msk_d := (mpk_d, \Delta_d, g_{0,d})$.

- Sample $(mpk'_d, msk'_d) \leftarrow \text{FSetup}(1^{\lambda}, B')$. Parse $msk'_d := (mpk'_d, \Delta'_d, g'_{0,d})$.

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

**Addition/Subtraction Gate** $\gamma = (u, v, w)$. Given the incoming wires $u$ and $v$ with keys $(k_u, K_u), (k_v, K_v)$ and depth $d_u, d_v$ respectively, set $d := \max(d_u, d_v) + 1$. Set

For wire $u$. $(\text{shift}_u, \langle \Delta'_d \ell_u \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_u}, \Delta'_d, K_u, \gamma \|u\|)$

For wire $v$. $(\text{shift}_v, \langle \Delta'_d \ell_v \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_v}, \Delta'_d, K_v, \gamma \|v\|)$

For wire $w$.

- $k_w := k_u \pm k_v \bmod B$

- $\tilde{K}_w := \langle \Delta'_d \ell_u \rangle_G \pm \langle \Delta'_d \ell_v \rangle_G \bmod p - 1$

- $(\text{shift}_w, K_w) := \text{MR}_G^H(\text{msk}'_d, \Delta_d, \tilde{K}_w, \gamma, B)$

- Set the keys of the outgoing wire $w$ at depth $d$ to $(k_w, K_w)$ and the garbled gate to

$$ \hat{C}_{\gamma} := (\text{shift}_u, \text{shift}_v, \text{shift}_w). $$

**Multiplication Gate** $\gamma = (u, v, w)$. Given the incoming wires $u$ and $v$ with keys $(k_u, K_u), (k_v, K_v)$ and depth $d_u, d_v$ respectively, set $d := \max(d_u, d_v) + 1$ and sample $c$ uniformly random shares $(k_u^i, k_v^i)_{i \le c}$ of $(k_u, k_v)$ over $\mathbb{Z}_B$.

For wire $u$. For $i=1$ to $c$,

- $(\text{leakyshift}_u^i, \langle k_u^i \ell_v \rangle_G) := \text{LVtO}_G^{H'}(\text{msk}_{d_v}, k_u^i, K_v, \gamma \|u\|)$

- $(\text{shift}_u^i, \langle \Delta'_d k_u^i \ell_v \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_v}, \Delta'_d k_u^i, K_v, \gamma \|u\|)$

- $(\text{shift}_u, K_u') := \text{VtO}_G^H(\text{msk}_{d_u}, \Delta'_d, K_u, \gamma \|u\|)$

- $(\text{shift}_v^i, \langle K_u' \ell_v \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_v}, K_u', K_v, \gamma)$

For wire $v$. For $i=1$ to $c$,

- $(\text{leakyshift}_v^i, \langle k_v^i \ell_u \rangle_G) := \text{LVtO}_G^{H'}(\text{msk}_{d_u}, k_v^i, K_u, \gamma \|v\|)$

- $(\text{shift}_v^i, \langle \Delta'_d k_v^i \ell_u \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_v}, \Delta'_d k_v^i, K_v, \gamma \|v\|)$

For wire $w$. For $i=1$ to $c$,

- $\tilde{k}_w^i := \langle k_u^i \ell_v \rangle_G + \langle k_v^i \ell_u \rangle_G$

- $\tilde{K}_w^i := \langle \Delta'_d k_u^i \ell_v \rangle_G + \langle \Delta'_d k_v^i \ell_u \rangle_G \bmod p - 1$

- $\tilde{k}_w := (\sum_{i=1}^c k_u^i) \cdot (\sum_{i=1}^c k_v^i) + \sum_{i=1}^t \tilde{k}_w^i$

- $\tilde{K}_w := \langle K_u' \ell_v \rangle_G - \Delta'_d \cdot (\sum_{i=1}^c \tilde{k}_w^i) + \sum_{i=1}^c \tilde{K}_w^i \bmod p - 1$

- $k_w := [\tilde{k}_w \bmod B]$

- $(\text{shift}_w, K_w) := \text{MR}_G^H(\text{msk}'_d, \Delta_d, \tilde{K}_w, \gamma, B)$

- Set the keys of the outgoing wire $w$ at depth $d$ to $(k_w, K_w)$ and the garbled gate to

$$ \hat{C}_{\gamma} := \left( \sum_{i=1}^{c} (\text{leakyshift}_u^i, \text{leakyshift}_v^i, \text{shift}_u^i, \text{shift}_v^i), \text{shift}_u, \text{shift}_v, \text{shift}_w \right). $$

**Output.** The garbler outputs the global keys $\Delta_1$, the wire keys $\hat{K}$ and the garbled circuit $\hat{C}$, where

$$ \hat{K} = (k_w, K_w)_{w \in W(C)}, \qquad \hat{C} = ((mpk_d, mpk'_d)_{d \le D}, (\hat{C}_{\gamma})_{\gamma \in \Gamma(C)}, (k_o)_{o \in O(C)}). $$

**Algorithm 1:** Garbling Algorithm of the Modular Arithmetic Garbling Scheme over $\mathbb{Z}_B$ with Rate $\Theta(\log B/\lambda)$ from Power DDH.

**Evaluation algorithm** We represent on Algorithm 2 the evaluation algorithm AGC.Eval$((\ell_i, L_i)_{i \in I(C)}, \hat{C})$. The evaluation algorithm takes as input the input labels $(\ell_i, L_i)$ for every $i \in I(C)$, where we recall that labels are defined for every wire $w$ with value $x_w$ as $(\ell_w, L_w) := (x_w - k_w \bmod B, \Delta_d \cdot \ell_w - K_w \bmod p - 1)$. It also receives the garbled circuit $\hat{C} = ((mpk_d, mpk'_d)_{d \le D}, (\hat{C}_{\gamma})_{\gamma \in \Gamma(C)})$.
**Algorithm** Modular Garbling from Power-DDH: AGC.Eval(((lᵢ, Lᵢ)ᵢ∈I(C), Ĉ)

**Parameters.** Let (G, p, g, G) := GrpGen*(1$^{λ}$). Let c = c(λ) denote an arbitrarily slowly growing functions c = ω(1), and set B' := B² + c · λ · B³. Let H : G → Zₚ₋₁ and H' : G × {0, 1}* → [λ · B] denote TCR hash functions for exponential correlations over G. Let F = (F*, F.KeyGen*, F.Eval, F.Punct*, F.PEval) denote the modified PPRF of Section 3.4. Parse Ĉ = (mpkᵣ, mpk'ᵣ)ᵣ≤D, (Ĉγ)γ∈Γ(C), (k₀)₀∈O(C). The evaluator computes the labels of all outgoing wires of a gate using the labels of the gate's incoming wires, starting with the input wire labels and computing each gate's outgoing wire's label as soon as its incoming wire labels have been computed.

**Addition/Subtraction Gate** $\gamma = (u, v, w)$. Given the incoming wires $u$ and $v$ with labels $(\ell_u, L_u)$, $(\ell_v, L_v)$ and depth $d_u, d_v$ respectively, set $d := \max(d_u, d_v) + 1$. Parse $\hat{C}_\gamma := (\text{shift}_u, \text{shift}_v, \text{shift}_w)$. Set

For wire $u$. $\langle \Delta'_d \ell_u \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| u, \text{shift}_u)$

For wire $v$. $\langle \Delta'_d \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| v, \text{shift}_v)$

For wire $w$.

$$- \tilde{\ell}_w := \ell_u \pm \ell_v$$

$$- \ell_w := [\tilde{\ell}_w \bmod B]$$

$$- \tilde{L}_w := \langle \Delta'_d \ell_u \rangle_E \pm \langle \Delta'_d \ell_v \rangle_E \bmod p - 1$$

$$- L_w := \text{MR}_E^H(\text{mpk}'_d, \tilde{\ell}_w, \tilde{L}_w, \gamma, \text{shift}_w, B)$$

$$- \text{Set the outgoing wire label to } (\ell_w, L_w).$$

**Multiplication Gate** $\gamma = (u, v, w)$. Given the incoming wires $u$ and $v$ with label $(\ell_u, L_u)$, $(\ell_v, L_v)$ and depth $d_u, d_v$ respectively, set $d := \max(d_u, d_v) + 1$ and parse $\hat{C}_\gamma := (\text{leakyshift}_u, \text{leakyshift}_v, \text{shift}_u^0, \text{shift}_v^0, \text{shift}_u, \text{shift}'_u, \text{shift}_w)$. For wire $u$.

$$\bullet \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_E := \text{LVtO}_E^{H'}(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| u, \text{leakyshift}_u)$$

$$\bullet \langle \Delta'_d \sum_{i=1}^{c} k_u^i \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| u, \text{shift}_u^0)$$

$$- L'_u := \text{VtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| u, \text{shift}_u)$$

$$- \langle K'_u \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma, \text{shift}'_u)$$

$$- \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_E := \text{LVtO}_E^{H'}(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| v, \text{leakyshift}_v)$$

$$- \langle \Delta'_d \sum_{i=1}^{c} k_v^i \ell_u \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| v, \text{shift}_v^0)$$

$$- \tilde{\ell}_w := \ell_u \ell_v + \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_E + \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_E$$

$$- \tilde{L}_w := \langle K'_u \ell_v \rangle_E + L'_u \ell_v + \langle \Delta'_d \sum_{i=1}^{c} k_u^i \ell_v \rangle_E + \langle \Delta'_d \sum_{i=1}^{c} k_v^i \ell_u \rangle_E \bmod p - 1$$

$$- \ell_w := [\tilde{\ell}_w \bmod B]$$

$$- L_w := \text{MR}_E^H(\text{mpk}'_d, \tilde{\ell}_w, \tilde{L}_w, \gamma, \text{shift}_w, B)$$

$$- \text{Set the outgoing wire label to } (\ell_w, L_w).$$

**Output.** For all output wire $o \in O(C)$, set $z_o := \ell_o + k_o \bmod B$. Output $z := (z_o)_{o \in O(C)}$.

**Algorithm 2:** Evaluation Algorithm of the Modular Arithmetic Garbling Scheme over Z<sub>B</sub> with Rate Θ(log B/λ) from Power DDH.

## 4.5 Proof of Theorem 18

We provide a complete proof of correctness and security of our modular garbling scheme below.

**Correctness** Fix a circuit $C$ and an input $x$. For every wire $w$ of $C$, let $x_w$ denote the value carried by this wire during the computation of $C(x)$. We prove that the following invariant is maintained for every wire $w$:

$$ (\ell_w, L_w) := (x_w - k_w \bmod B, \Delta_d \cdot \ell_w - K_w \bmod p - 1), $$
where $\ell_w \le B$, and $d$ denote the depth depth($w$) of $w$. Note that in particular, this implies that $z_o = \ell_o+k_o = x_o$ mod $B$ for every output wire $o \in O(C)$, hence correctness is satisfied if the invariant is maintained. Fix the input labels $(\ell_i, L_i)_{i \in I(C)} := \text{InputLabels}(1^\lambda, C, \Delta_1, \tilde{K}, x)$, which satisfy the invariant by definition.

**Addition/Subtraction Gate** $\gamma = (u, v, w)$ with incoming wires at depth $d_u, d_v$ with keys $(k_u, K_u), (k_v, K_v)$ and labels $(\ell_u, L_u), (\ell_v, L_v)$. Assume that the invariant is maintained for $u, v$ and set $d := \max(d_u, d_v) + 1$.

For wire $u$. $\langle \Delta'_d \ell_u \rangle_G + \langle \Delta'_d \ell_u \rangle_E = \Delta'_d \ell_u \mod p - 1 \triangleright$ by correctness of $VtO^H$

For wire $v$. $\langle \Delta'_d \ell_v \rangle_G + \langle \Delta'_d \ell_v \rangle_E = \Delta'_d \ell_v \mod p - 1 \triangleright$ by correctness of $VtO^H$

For wire $w$.

$$- \ell_w = \ell_u \pm \ell_v \mod B$$

$$- \tilde{K}_w + \tilde{L}_w = (\langle \Delta'_d \ell_u \rangle_G + \langle \Delta'_d \ell_u \rangle_E) \pm (\langle \Delta'_d \ell_v \rangle_G + \langle \Delta'_d \ell_v \rangle_E) = \Delta'_d \cdot (\ell_u + \ell_v) \mod p - 1$$

$$- K_w + L_w = \Delta'_d \cdot [\ell_u + \ell_v \mod B] = \Delta'_d \ell_w \mod p - 1 \triangleright \text{by correctness of MR}^H$$

**Multiplication Gate** $\gamma = (u, v, w)$ with incoming wires at depth $d_u, d_v$ with keys $(k_u, K_u), (k_v, K_v)$ and labels $(\ell_u, L_u), (\ell_v, L_v)$. Assume that the invariant is maintained for $u, v$ and set $d := \max(d_u, d_v) + 1$.

For wire $u$.

$$\sum_{i=1}^{c} \langle k_u^i \ell_v \rangle_G + \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_E = \sum_{i=1}^{c} k_u^i \ell_v \quad (\text{over } \mathbb{Z}) \triangleright \text{by correctness of } LVtO^{H'}$$

$$\sum_{i=1}^{c} \langle \Delta'_{d} k_{u}^{i} \ell_{v} \rangle_{\mathbb{G}} + \langle \Delta'_{d} \sum_{i=1}^{c} k_{u}^{i} \ell_{v} \rangle_{\mathbb{E}} = \Delta'_{d} \sum_{i=1}^{c} k_{u}^{i} \ell_{v} \mod p - 1 \triangleright \text{by correctness of } VtO^{H}$$

$$- K'_{u} + L'_{u} = \Delta'_{d} \ell_{u} \mod p - 1 \triangleright \text{by correctness of } VtO^{H}$$

$$- \langle K'_{u} \ell_{v} \rangle_{\mathbb{G}} + \langle K'_{u} \ell_{v} \rangle_{\mathbb{E}} = K'_{u} \ell_{v} \mod p - 1 \triangleright \text{by correctness of } VtO^{H}$$

For wire $v$.

$$- \sum_{i=1}^{c} \langle k_v^i \ell_u \rangle_G + \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_E = \sum_{i=1}^{c} k_v^i \ell_u \quad (\text{over } \mathbb{Z}) \triangleright \text{by correctness of } LVtO^{H'}$$

$$- \sum_{i=1}^{c} \langle \Delta'_{d} k_{v}^{i} \ell_{u} \rangle_{\mathbb{G}} + \langle \Delta'_{d} \sum_{i=1}^{c} k_{v}^{i} \ell_{u} \rangle_{\mathbb{E}} = \Delta'_{d} \sum_{i=1}^{c} k_{v}^{i} \ell_{u} \mod p - 1 \triangleright \text{by correctness of } VtO^{H}$$

For wire $w$.

$$
\begin{align*}
\tilde{k}_w + \tilde{l}_w &= \left(\sum_{i=1}^{c} k_u^i\right) \cdot \left(\sum_{i=1}^{c} k_v^i\right) + \sum_{i=1}^{t} \tilde{k}_w^i + \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_{\mathbb{E}} + \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_{\mathbb{E}} + \ell_u \ell_v \\
&= \left(\sum_{i=1}^{c} k_u^i\right) \cdot \left(\sum_{i=1}^{c} k_v^i\right) + \sum_{i=1}^{t} (k_u^i \ell_v + k_v^i \ell_u) + \ell_u \ell_v \\
&= \left(\sum_{i=1}^{c} k_u^i + \ell_u\right) \cdot \left(\sum_{i=1}^{c} k_v^i + \ell_v\right) \\
\implies k_w + \ell_w &= \left(\sum_{i=1}^{c} k_u^i + \ell_u\right) \cdot \left(\sum_{i=1}^{c} k_v^i + \ell_v\right) \mod B \\
&= (k_u + \ell_u) \cdot (k_v + \ell_v) \mod B \triangleright \text{the } k_u^i, k_v^i \text{ are shares of } k_u, k_v \text{ over } \mathbb{Z}_B \\
&= x_u \cdot x_v \mod B \triangleright \text{by the invariants for } u, v
\end{align*}
$$

$$
\begin{align*}
\tilde{K}_w + \tilde{L}_w &= (\langle K'_u \ell_v \rangle_G + \langle K'_u \ell_v \rangle_E) - \Delta'_d \cdot \sum_{i=1}^{c} \tilde{k}_w^i + L_u \ell_v + \sum_{i=1}^{c} \tilde{K}_w^i \\
&\quad + \langle \Delta'_d \sum_{i=1}^{c} k_u^i \ell_v \rangle_E + \langle \Delta'_d \sum_{i=1}^{c} k_v^i \ell_u \rangle_E \mod p - 1 \\
&= K'_u \ell_v - \Delta'_d \cdot \sum_{i=1}^{c} \tilde{k}_w^i + L'_u \ell_v + \Delta'_d \cdot \left( \sum_{i=1}^{c} \tilde{k}_w^i + \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_E + \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_E \right) \mod p - 1 \\
&= (K'_u + L'_u) \ell_v + \Delta'_d \cdot \left( \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_E + \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_E \right) \mod p - 1 \\
&= \Delta'_d \cdot \ell_u \ell_v + \Delta'_d \cdot \left( \langle \sum_{i=1}^{c} k_u^i \ell_v \rangle_E + \langle \sum_{i=1}^{c} k_v^i \ell_u \rangle_E \right) = \Delta'_d \cdot \tilde{l}_w \mod p - 1 \\
\implies K_w + L_w &= \Delta'_d \cdot [\tilde{l}_w \mod B] \triangleright \text{by correctness of MR}^H
\end{align*}
$$
To conclude the proof of correctness, it remains to verify that, when using the $MR^H$ procedure on shares of $\Delta'_d \cdot (\tilde{\ell}_w)$ over $\mathbb{Z}_{p-1}$, the value $\tilde{\ell}_w$ is bounded by $B' = B^2 + \lambda \cdot c \cdot B^3$ (in absolute value):

- For addition/subtraction gates, $\tilde{\ell}_w = \ell_u + \ell_v \le 2B < B'$

- For multiplication gates, $\tilde{\ell}_w = \ell_u \ell_v + \sum_{i=1}^c \tilde{\ell}_w^i$, where $\tilde{\ell}_w^i = \langle k_u^i \ell_v \rangle_E + \langle k_v^i \ell_u \rangle_E$.

As shown in Section 4.3, the outputs of $LVtO_E^{H'}$ have absolute value at most $\lambda \cdot B^3/2$, hence $|\langle k_u^i \ell_v \rangle_E + \langle k_v^i \ell_u \rangle_E| \le \lambda \cdot B^3$, and therefore $|\tilde{\ell}_w| \le B^2 + c \cdot \lambda \cdot B^3 = B'$. Eventually, the bound $\ell_w \le B$ is trivial as $\ell_w := [\tilde{\ell}_w \bmod B]$. This concludes the proof of correctness.

**Security** We represent on Algorithm 3 a simulator $\text{Sim}(1^{\lambda}, C, z)$, outputs a simulated garbled circuit $\hat{C}$ together with simulated input labels $\hat{L} = (\ell_i, L_i)_{i \in I(C)}$.

**Algorithm Modular Garbling from Power-DDH: $\text{Sim}(1^{\lambda}, C, z)$**

**Parameters.** Let $(\mathbb{G}, p, g, G) := \text{GrpGen}^*(1^{\lambda})$. Let $c = c(\lambda)$ denote an arbitrarily slowly growing functions $c = \omega(1)$, and set $B' := B^2 + c \cdot \lambda \cdot B^3$. Set $t \leftarrow (2c+1) \cdot s$. Let $\text{H} : \mathbb{G} \to \mathbb{Z}_p$ and $\text{H}' : \mathbb{G} \to [\lambda \cdot B]$ denote TCR hash functions for exponential correlations over $\mathbb{G}$. Let $\text{F} = (\text{F}\text{Setup}^*, \text{F}\text{KeyGen}^*, \text{F}\text{Eval}, \text{F}\text{Punct}^*, \text{F}\text{PEval})$ denote the modified PPRF of Section 3.4.

**Initialization.** For $d=1$ to $D$,

- sample $(\text{mpk}_d, \text{msk}_d) \leftarrow \text{F}\text{Setup}(1^{\lambda}, B)$. Parse $\text{msk}_d := (\text{mpk}_d, \Delta_d, g_{0,d})$.

- Sample $(\text{mpk}'_d, \text{msk}'_d) \leftarrow \text{F}\text{Setup}(1^{\lambda}, B')$. Parse $\text{msk}'_d := (\text{mpk}'_d, \Delta'_d, g'_{0,d})$.

**Simulated Input labels.** For each input wire $i$, sample $(\ell_i, L_i) \leftarrow \mathbb{Z}_B \times \mathbb{Z}_{p-1}$.

**Addition/Subtraction Gate** $\gamma = (u, v, w)$. Given the incoming wires $u$ and $v$ with simulated labels $(\ell_u, L_u)$, $(\ell_v, L_v)$ and depth $d_u, d_v$ respectively, set $d := \max(d_u, d_v) + 1$.

For wire $u$. Set $\text{shift}_u \leftarrow \mathbb{Z}_{p-1}$ and $\langle \Delta'_d \ell_u \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| u, \text{shift}_u)$.

For wire $v$. Set $\text{shift}_v \leftarrow \mathbb{Z}_{p-1}$ and $\langle \Delta'_d \ell_v \rangle_G := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| v, \text{shift}_v)$.

For wire $w$.

- $\tilde{\ell}_w := \ell_u \pm \ell_v$

- $\ell_w := [\tilde{\ell}_w \bmod B]$

- $\tilde{L}_w := \langle \Delta'_d \ell_u \rangle_E \pm \langle \Delta'_d \ell_v \rangle_E \bmod p - 1$

- Sample $\text{shift}_w \leftarrow \mathbb{Z}_{p-1}$ and set $L_w := \text{MR}_E^H(\text{mpk}'_d, \tilde{\ell}_w, \tilde{L}_w, \gamma, \text{shift}_w, B)$

- Set the simulated outgoing wire label to $(\ell_w, L_w)$ and the simulated garbled gate to

$$ \hat{C}_{\gamma} := (\text{shift}_u, \text{shift}_v, \text{shift}_w). $$

**Multiplication Gate** $\gamma = (u, v, w)$. Given the incoming wires $u$ and $v$ with simulated label $(\ell_u, L_u)$, $(\ell_v, L_v)$ and depth $d_u, d_v$ respectively, set $d := \max(d_u, d_v) + 1$.

For wire $u$. For $i=1$ to $c$,

- $\text{psk}_u^i := \text{F}\text{Punct}^*(\text{mpk}_{d_v}, L_v)$

- Sample $\sigma_i^u \leftarrow \text{Ber}(1/\lambda)$.

- If $\sigma_i^u = 1$, $k_u^i \leftarrow \mathbb{Z}_B$, leakyshift$_u^i \leftarrow \text{SimLShift}^{H'}(\text{mpk}_{d_v}, \text{psk}_u^i, k_u^i, \ell_v, \gamma \| u \| i)$.

- Else, leakyshift$_u^i \leftarrow \text{SimShift}^{H'}(\text{mpk}_{d_v}, \text{psk}_u^i, \ell_v, \gamma \| u \| i)$

- $\langle k_u^i \ell_v \rangle_E := \text{LVtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| u \| i, \text{leakyshift}_u^i)$

- Sample $\text{shift}_u^i \leftarrow \mathbb{Z}_{p-1}$

- $\langle \Delta'_d k_u^i \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| u \| i, \text{shift}_u^i)$

- Sample $(\text{shift}_u, \text{shift}'_u) \leftarrow \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$

- $L'_u := \text{VtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| u, \text{shift}_u)$.

- $\langle K'_u \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma, \text{shift}'_u)$

For wire $v$. For $i=1$ to $c$,

- $\text{psk}'_v := \text{F}\text{Punct}^*(\text{mpk}_{d_v}, L_v)$

- Sample $\sigma_i^v \leftarrow \text{Ber}(1/\lambda)$.

- If $\sigma_i^v = 1$, set $k_v^i \leftarrow \mathbb{Z}_B$ and leakyshift$_v^i \leftarrow \text{SimLShift}^{H'}(\text{mpk}_{d_v}, \text{psk}_v^i, k_v^i, \ell_v, \gamma \| v \| i)$.

- Else, leakyshift$_v^i \leftarrow \text{SimShift}^{H'}(\text{mpk}_{d_v}, \text{psk}_v^i, \ell_v, \gamma \| v \| i)$

- $\langle k_v^i \ell_u \rangle_E := \text{LVtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| v \| i, \text{leakyshift}_v^i)$
- Sample shift<sub>v</sub><sup>i</sup> ← $ Z_{p-1}

- $\langle \Delta'_d k_v^i \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma ||v||i, \text{shift}_v^i)$

For wire w. For i = 1 to c,

• $\tilde{\ell}_w^i := \langle k_u^i \ell_v \rangle_E + \langle k_v^i \ell_u \rangle_E$

• $\tilde{L}_w^i := \langle \Delta'_d k_u^i \ell_v \rangle_E + \langle \Delta'_d k_v^i \ell_u \rangle_E \mod p - 1$

- $\tilde{\ell}_w := \ell_u \ell_v + \sum_{i=1}^c \tilde{\ell}_w^i$

- Sample shift<sub>w</sub> ← $ Z_{p-1}

- $\tilde{L}_w := \langle K'_u \ell_v \rangle_E + L'_u \ell_v + \sum_{i=1}^c \tilde{L}_w^i \mod p - 1$

- $\ell_w := [\tilde{\ell}_w \mod B]$

- $L_w := \text{MR}_E^H(\text{mpk}'_d, \tilde{\ell}_w, \tilde{L}_w, \gamma, \text{shift}_w, B)$

- Set the simulated outgoing wire label to $(\ell_w, L_w)$ and the simulated garbled gate to

$$ \hat{C}_{\gamma} := \left( \sum_{i=1}^{c} (\text{leakyshift}_{u}^{i}, \text{leakyshift}_{v}^{i}, \text{shift}_{u}^{i}, \text{shift}_{v}^{i}), \text{shift}_{u}, \text{shift}'_{u}, \text{shift}_{w} \right). $$

**Output.** Given the output string $z = (z_o)_{o \in O(C)}$, set $k_o := z_o - \ell_o \mod B$ and output

$$ \hat{L} = (\ell_i, L_i)_{i \in I(C)} $$

$$ \hat{C} = ((\text{mpk}_d, \text{mpk}'_d)_{d \le D}, (\hat{C}_{\gamma})_{\gamma \in \Gamma(C)}, (k_o)_{o \in O(C)}). $$

**Algorithm 3:** Simulator of the Modular Arithmetic Garbling Scheme over $\mathbb{Z}_B$ with Rate $\omega(\log B/\lambda)$ from Power DDH.

**Lemma 21.** For all sequences of polynomial-size $\mathbb{Z}_B$-arithmetic circuits $\{C_\lambda\}_{\lambda \in \mathbb{N}}$, and every sequence of inputs $(x_\lambda)_{\lambda \in \mathbb{N}}$ with $|x_\lambda| = |I(C_\lambda)|$, the following holds:

$$ \{ \text{Sim}(1^{\lambda}, C_{\lambda}, z) : z \leftarrow C_{\lambda}(x) \} \approx_c \left\{ \left( \left( (\ell_i, L_i)_{i \in I(C_{\lambda})}, \hat{C} \right) : (\Delta_1, \hat{K}, \hat{C}) \leftarrow \text{Garble}(1^{\lambda}, C) \atop (\ell_i, L_i)_{i \in I(C_{\lambda})} := \text{InputLabels}(1^{\lambda}, C, \Delta_1, \hat{K}, x) \right) \right\} $$

*Proof.* The proof proceeds through a sequence of game hops. Fix a security parameter $1^{\lambda}$, a circuit $C = C_\lambda$, and an input $x = x_\lambda$. We let **Game**<sub>0</sub> denote the real game:

**Game**<sub>0</sub>: the simulator Sim receives as input $(1^{\lambda}, C, x)$, computes $(\Delta_1, \hat{K}, \hat{C}) \leftarrow \text{Garble}(1^{\lambda}, C)$ and $(\ell_i, L_i)_{i \in I(C)} := \text{InputLabels}(1^{\lambda}, C, \Delta_1, \hat{K}, x)$. Sim outputs $((\ell_i, L_i)_{i \in I(C)}, \hat{C})$.

In the following sequence of games, the simulator initially knows the wire values $(x_w)_{w \in W(C)}$ for all incoming wires of all gates and the corresponding incoming wire keys $(k_w, K_w)_{w \in W(C)}$. The proof proceeds by letting the simulator forget, in a level-by-level fashion, the incoming wire values $x_w$ and corresponding wire keys $(k_w, K_w)$ for gates at a given level, and construct instead simulated labels $(\ell_w, L_w)$.

**Game**<sub>d</sub>: at the start of this game, Sim knows the wire values $x_w$ for all wires $w$ at depth $\text{depth}(w) \ge d$. It performs the following steps:

**Initialization.** For $d=1$ to $D$,

- sample $(\text{mpk}_d, \text{msk}_d) \leftarrow \text{F}\text{Setup}(1^{\lambda}, B)$. Parse $\text{msk}_d := (\text{mpk}_d, \Delta_d, g_{0,d})$.

- Sample $(\text{mpk}'_d, \text{msk}'_d) \leftarrow \text{F}\text{Setup}(1^{\lambda}, B')$. Parse $\text{msk}'_d := (\text{mpk}'_d, \Delta'_d, g'_0, g'_d)$.

**Simulated Input labels.** For each input wire $i$, sample $(\ell_i, L_i) \leftarrow \mathbb{Z}_B \times \mathbb{Z}_{p-1}$.

During the simulation of $\hat{C}$, Sim constructs simulated labels $(\ell_w, L_w)$ for every wire $w$ at depth $\text{depth}(w) < d$, and simulated wire keys $(k_w, K_w)$ for every wire $w$ at depth $\text{depth}(w) \ge d$. We cover each of the two cases below.

**Case 1:** For every gate $\gamma$ with outgoing wire $w$ at depth $\text{depth}(w) \le d$. Given the incoming wires $u$ and $v$ with simulated label $(\ell_u, L_u)$, $(\ell_v, L_v)$ and depth $d_u, d_v < d$ respectively, run the gate garbling algorithm of Algorithm 3 to obtain the simulated outgoing wire label $(\ell_w, L_w)$ and the simulated garbled gate $\hat{C}_\gamma$. If $\text{depth}(w) = d$, set $(k_w, K_w) := (x_w - \ell_w \mod B, \Delta_d \ell_w - L_w \mod p - 1)$.

**Case 2:** For every gate $\gamma$ with outgoing wire $w$ at depth $\text{depth}(w) > d$.
**Case 2.1:** $d_u, d_v \ge d$. Run the gate garbling algorithm of Algorithm 1 with incoming wire keys $(k_u, K_u)$ and $(k_v, K_v)$ to obtain the outgoing wire key $(k_w, K_w)$ and the garbled gate $\hat{C}$.

**Case 2.2:** $d_u < d$, $d_v = d_w - 1 \ge d$. Given the simulated labels $(\ell_u, L_u)$ for the incoming wire $u$ and the wire key $(k_v, K_v)$ for the incoming wire $v$, set $(\ell_v, L_v) := (x_v - k_v \bmod B, \Delta_{d_v} x_v - K_v \bmod p - 1)$.

We provide below the detailed procedure for case 2.2. We use red and blue to denote variants of the procedure that will be used in later games hops. The procedure of case 2.2 corresponds to variant 1, where the parts in blue are ignored.

**Addition/Subtraction Gate** $\gamma = (u, v, w)$.

**For wire u.** Simulated procedure for incoming wires

- Set $\text{shift}_u \leftarrow \mathbb{Z}_{p-1}$ and $\langle \Delta'_d \ell_u \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_u}, \ell_u, L_u, \gamma \| u, \text{shift}_u)$.

**For wire v.** Garbler procedure for incoming wires

- $(\text{shift}_v, \langle \Delta'_d \ell_v \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_v}, \Delta'_d, K_v, \gamma \| v)$

- $\langle \Delta'_d \ell_v \rangle_E := \Delta'_d \ell_v - \langle \Delta'_d \ell_v \rangle_G \bmod p - 1$

**For wire w.** Hybrid procedure for outgoing wires

- $\tilde{\ell}_w := \ell_u \pm \ell_v$

- $\ell_w := [\tilde{\ell}_w \bmod B]$

- $\tilde{L}_w := \langle \Delta'_d \ell_u \rangle_E \pm \langle \Delta'_d \ell_v \rangle_E \bmod p - 1$

- $\tilde{K}_w := \Delta'_d \ell_v \cdot (\ell_u \pm \ell_v) - \tilde{L}_w \bmod p - 1$

- $(\text{shift}_w, K_w) := \text{MR}_G^H(\text{msk}'_{d_w}, \Delta_{d_w}, \tilde{K}_w, \gamma, B)$

- Set the outgoing wire key to $(x_w - \ell_w \bmod B, K_w)$ and the simulated garbled gate to

$$ \hat{C}_{\gamma} := (\text{shift}_u, \text{shift}_v, \text{shift}_w). $$

**Multiplication Gate** $\gamma = (u, v, w)$.

**For wire u.** Simulated procedure for incoming wires (version 1, version 2)

- Sample $c$ uniformly random shares $(k_u^i)_{i \le c}$ of $k_u$ over $\mathbb{Z}_B$.

- For $i=1$ to $c$,

- $\text{psk}_u^i := \text{F.Punct}^*(\text{mpk}_{d_v}, L_v)$

- Sample $\sigma_i^u \leftarrow \text{Ber}(1/\lambda)$.

- If $\sigma_i^u = 1$, set $k_u^i \leftarrow \mathbb{Z}_B$ and leakyshift$_u^i \leftarrow \text{SimLShift}^H(\text{mpk}_{d_v}, \text{psk}_u^i, k_u^i, \ell_v, \gamma \| u \| i)$.

- Else, leakyshift$_u^i \leftarrow \text{SimShift}^H(\text{mpk}_{d_v}, \text{psk}_u^i, \ell_v, \gamma \| u \| i)$

- $\langle k_u^i \ell_v \rangle_E := \text{LVtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| u \| i, \text{leakyshift}_u^i)$

- Sample $\text{shift}_u^i \leftarrow \mathbb{Z}_{p-1}$

- $\langle \Delta'_d k_u^i \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma \| u \| i, \text{shift}_u^i)$

- Sample $(\text{shift}_u, \text{shift}'_u) \leftarrow \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$

- $L'_u := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_u, L_u, \gamma \| u, \text{shift}_u)$

- $\langle K'_u \ell_v \rangle_E := \text{VtO}_E^H(\text{mpk}_{d_v}, \ell_v, L_v, \gamma, \text{shift}'_u)$

**For wire v.** Garbler procedure for incoming wires

For $i=1$ to $c$,

- $(\text{leakyshift}'_v, \langle k_v^i \ell_v \rangle_G) := \text{LVtO}_G^H(\text{msk}_{d_v}, k_v^i, K_v, \gamma \| v \| i)$

- $\langle k_v^i \ell_u \rangle_E := k_v^i \ell_u - \langle k_v^i \ell_u \rangle_G$

- $(\text{shift}'_v, \langle \Delta'_d k_v^i \ell_u \rangle_G) := \text{VtO}_G^H(\text{msk}_{d_v}, \Delta'_d k_v^i, K_v, \gamma \| v \| i)$

- $\langle \Delta'_d k_v^i \ell_u \rangle_E := \Delta'_d k_v^i \ell_u - \langle \Delta'_d k_v^i \ell_u \rangle_G \bmod p - 1$

**For wire w.** Hybrid procedure for outgoing wires

For $i=1$ to $c$,

- $\tilde{\ell}'_w := \langle k_u^i \ell_v \rangle_E + \langle k_v^i \ell_u \rangle_E$

- $\tilde{L}'_w := \langle \Delta'_d k_u^i \ell_v \rangle_E + \langle \Delta'_d k_v^i \ell_u \rangle_E \bmod p - 1$

- $\tilde{\ell}_w := \ell_u \ell_v + \sum_{i=1}^c \tilde{\ell}_w^i$

- $\ell_w := [\tilde{\ell}_w \bmod B]$

- $\langle K_u \ell_v \rangle_E := K_u \ell_v - \langle K_u \ell_v \rangle_G \bmod p - 1$

- $\tilde{L}_w := \langle K'_u \ell_v \rangle_E + L'_u \ell_v + \sum_{i=1}^c \tilde{L}_w^i \bmod p - 1$

- $\tilde{K}_w := \Delta'_d \ell_v \cdot \tilde{\ell}_w - \tilde{L}_w \bmod p - 1$

- $(\text{shift}_w, K_w) := \text{MR}_G^H(\text{msk}'_{d_w}, \Delta'_{d_w}, \tilde{K}_w, \gamma, B)$
- Set the outgoing wire key to $(x_w - \ell_w \mod B, K_w)$ and the simulated garbled gate to

$$ \hat{C}_{\gamma} := \left( \sum_{i=1}^{c} (\text{leakyshift}_{u}^{i}, \text{leakyshift}_{v}^{i}, \text{shift}_{u}^{i}, \text{shift}_{v}^{i}), \text{shift}_{u}, \text{shift}_{u}', \text{shift}_{w}) \right). $$

**Game**$_{d.1}$. In this game, we modify the simulation of the gate garbling procedure. The aim of the sequence of games starting at **Game**$_{d.1}$ is to allow Sim to forget all values $x_w$ on wires at depth $\text{depth}(w) = d$.

For every gate $\gamma$ with outgoing wire $w$ at depth $\text{depth}(w) \le d$. Sim behaves as in **Game**$_d$, except that if $\text{depth}(w) = d$, it does not reconstruct $(k_w, K_w)$ anymore (and instead simply stores $w$'s wire label $(\ell_w, L_w)$.

For every gate $\gamma$ with outgoing wire $w$ at depth $\text{depth}(w) > d$.

Case $d_u \ne d$ and $d_v \ne d$. Sim behaves exactly as in **Game**$_d$.

Case $d_u = d$ or $d_v = d$.

- For $a \in \{u, v\}$, if $d_a \le d$, denoting $b$ the other incoming wire, run the version 2 of the simulated procedure for incoming wires for wire $b$ and gate $\gamma$. Else, run the garbler procedure for incoming wires for wire $b$ and gate $\gamma$. Note that this differs from **Game**$_2$ only when $d_a = d$.

- As in **Game**$_d$, run the hybrid procedure for outgoing wires for the gate $\gamma$.

*Claim.* Under the $t$-instance joint security of $\text{VtO}^H$, $\text{LVtO}^{H'}$ (Definition 17), **Game**$_d$ and **Game**$_{d.1}$ are indistinguishable.

*Proof.* The only difference between **Game**$_d$ and **Game**$_{d.1}$ is that for all wires $w$ at depth $\text{depth}(w) = d$ (incoming to a gate $\gamma$), **Game**$_{d.1}$ uses the simulated procedure for incoming wires to $\gamma$, while **Game**$_d$ uses the garbled procedure for incoming wires to $\gamma$. The reduction to the $t$-instance joint security of $\text{VtO}^H$, $\text{LVtO}^{H'}$ is done by replacing the procedure for a depth-$d$ incoming wire $v$ to a gate $\gamma$ (with other incoming wire $u$ and outgoing wire $w$) with

- One call $(\text{VtO}, \Delta'_{d_w}, \ell_u, L_u)$ to the experiment $\text{ExpBothVtO}^{H,H'}(1^{\lambda}, B, \text{salt})$ (where the salts $\text{salt} := (\gamma, \gamma||a, \gamma||a||i)_{\gamma \in \Gamma(C), a \in W(C), i \le c}$ are all pairwise-distinct by construction) if $\gamma$ is an addition/subtraction gate;

- $c$ calls $(\text{LVtO}, k_u^i, \ell_v, L_v)$, $c$ calls $(\text{VtO}, \Delta'_{d} k_u^i, \ell_v, L_v)$, and one call $(\text{VtO}, K_u, \ell_v, L_v)$ to $\text{ExpBothVtO}^{H,H'}(1^{\lambda}, B, \text{salt})$ if $\gamma$ is a multiplication gate.

The total number of calls is at most $(2c + 1)$ for each wire, and there can be at most $s$ wire at any given level, hence the total number of calls is at most $(2c + 1)s = t$. Answering the queries as in $\text{ExpBothVtO}^{H,H'}(1^{\lambda}, B, \text{salt})$ yields exactly **Game**$_{d.1}$. Answering the queries as in $\text{ExpBothVtO}^{H,H'}(1^{\lambda}, B, \text{salt})$ yields **Game**$_d$, up to one minor difference: the answers $\langle v_G v_E \rangle_E$ of $\text{ExpBothVtO}_0$ are computed as $\langle v_G v_E \rangle_E := \text{LVtO}_E^{H'}(\text{mpk}, v_E, \langle \Delta v_E \rangle_E, \text{salt}_i, \text{shift})$, while they are computed as $v_G v_E - \langle v_G v_E \rangle_G$ (mod $B$ if it is a VtO query, over $\mathbb{Z}$ otherwise) in **Game**$_d$. However, by perfect correctness of VtO and LVtO, this is perfectly equivalent to $\text{ExpBothVtO}_0$. This concludes the proof. ■

**Game**$_{d.2}$. This game is identical to **Game**$_{d.1}$, except that we use version 1 in the simulated procedure for an incoming wire to a multiplication gate.

*Claim.* The advantage of any adversary in distinguishing **Game**$_{d.1}$ from **Game**$_{d.2}$ is at most $s/\lambda^c = \text{negl}(\lambda)$.

*Proof.* The only difference between **Game**$_{d.1}$ and **Game**$_{d.2}$ lies in how the shares $k_u^i$ are sampled: in version 2, the $k_u^i$ are random $(c-1)$-out-of-$c$ shares of $k_u$, while in version 1, the $k_u^i$ are sampled independently. Observe that whenever $\sigma_i^u = 0$, the share $k_u^i$ is not use by the procedure, and therefore, the two versions become perfectly indistinguishable: the view of a distinguisher between both games differs if and only if, for some incoming wire $u$, all the bits $(\sigma_i^u)_{i \le c}$ are equal to 1. As the $\sigma_i^u$ are independent Bernoulli samples equal to 1 with probability $1/\lambda$, this happens with probability $1/\lambda^c$, and we conclude with a union bound over all gates. ■
**Game**$_{d.3}$. In this game, we modify the procedure for all gates where both incoming wires use the simulated procedure, but the outgoing wire uses the hybrid procedure. Instead, we let all such outgoing wires *w* use the simulated procedure for outgoing wires of Algorithm 3.

*Claim*. Under the *t*-instance security of MR<sup>H</sup> (Definition 14), **Game**<sub>d.2</sub> and **Game**<sub>d.3</sub> are indistinguishable.

*Proof*. The claim is proven via a direct reduction to the ExpMR<sup>H</sup>(1<sup>λ</sup>, B', B, salt) security game, with **salt** = (γ)<sub>γ∈Γ(C)</sub>: the procedure for an outgoing wire *w* is replaced by a call (Δ'<sub>*d*<sub>w</sub></sub>, ℓ'<sub>w</sub>, ˜*L*<sub>w</sub>) to ExpMR<sup>H</sup>(1<sup>λ</sup>, B', B, salt). Answering the queries as in ExpMR<sup>H,H'</sup><sub>1</sub>(1<sup>λ</sup>, B', B, salt) yields exactly **Game**<sub>d.3</sub>, and answering as in ExpMR<sup>H,H'</sup><sub>0</sub>(1<sup>λ</sup>, B', B, salt) yields exactly **Game**<sub>d.2</sub> using the perfect correctness of MR.

■

We now finish the proof of Lemma 21. First, observe that $\mathbf{Game}_{d.3}$ is exactly $\mathbf{Game}_{d+1}$. Second, $\mathbf{Game}_D$ is exactly the simulator of Algorithm 3 (and the wire values $x_w$ for all wires $w$ at depth $\text{depth}(w) \ge D$ are the output wire values $z = (z_o)_{O(C)}$, which are passed as input to Sim). This concludes the proof.

■

**Acknowledgements.** We thank the anonymous reviewers for helpful comments and suggestions that improved the presentation and results in the paper, in particular on an optimization that improved the rate of the scheme. Geoffroy Couteau, Aditya Hegde, and Naman Kumar acknowledge the support of the French Agence Nationale de la Recherche (ANR) under grant ANR-20-CE39-0001 (project SCENE) and under the France 2030 ANR Project ANR-22-PECY-003 SecureCompute. This work is supported by ERC grant OBELiSC (101115790). Carmit Hazay acknowledges the support of the United States-Israel Binational Science Foundation (BSF) through Grant No. 2020277. Aditya Hegde was supported by NSF CNS-1814919, NSF CAREER 1942789, and the Johns Hopkins University Catalyst Award.

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<sup>+18</sup>. Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa. Constrained PRFs for NC<sup>1</sup> 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. Springer, Heidelberg, Germany.

BCG<sup>+17</sup>. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù. Homomorphic secret sharing: Optimizations and applications. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, *ACM CCS 2017: 24th Conference on Computer and Communications Security*, pages 2105-2122, Dallas, TX, USA, October 31-November 2, 2017. ACM Press.

BCM<sup>+24</sup>. 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. Springer, Heidelberg, Germany.

BCP03. Emmanuel Bresson, Dario Catalano, and David Pointcheval. A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications. In Chi-Sung Laih, editor, *Advances in Cryptology - ASIACRYPT 2003*, volume 2894 of *Lecture Notes in Computer Science*, pages 37-54, Taipei, Taiwan, November 30 - December 4, 2003. Springer, Heidelberg, Germany.

BGG<sup>+14</sup>. Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Phong Q. Nguyen and Elisabeth Oswald, editors, *Advances in Cryptology - EUROCRYPT 2014*, volume 8441 of *Lecture Notes in Computer Science*, pages 533-556, Copenhagen, Denmark, May 11-15, 2014. Springer, Heidelberg, Germany.
BGI14. Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In *Hugo Krawczyk, editor, PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography*, volume 8383 of *Lecture Notes in Computer Science*, pages 501–519, Buenos Aires, Argentina, March 26–28, 2014. Springer, Heidelberg, Germany.

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. Springer, Heidelberg, Germany.

BGI17. Elette Boyle, Niv Gilboa, and Yuval Ishai. Group-based secure computation: Optimizing rounds, communication, and computation. In *Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017, Part II*, volume 10211 of *Lecture Notes in Computer Science*, pages 163–193, Paris, France, April 30 – May 4, 2017. Springer, Heidelberg, Germany.

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. Springer, Heidelberg, Germany.

BMR90. Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In *22nd Annual ACM Symposium on Theory of Computing*, pages 503–513, Baltimore, MD, USA, May 14–16, 1990. ACM Press.

BMR16. Marshall Ball, Tal Malkin, and Mike Rosulek. Garbling gadgets for Boolean and arithmetic circuits. In *Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security*, pages 565–577, Vienna, Austria, October 24–28, 2016. ACM Press.

BW13. Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In *Kazue Sako and Palash Sarkar, editors, Advances in Cryptology - ASIACRYPT 2013, Part II*, volume 8270 of *Lecture Notes in Computer Science*, pages 280–300, Bangalore, India, December 1–5, 2013. Springer, Heidelberg, Germany.

CHHK25. Geoffroy Couteau, Carmit Hazay, Aditya Hegde, and Naman Kumar. omega(1/lambda)-rate boolean garbling scheme from generic groups. In *Advances in Cryptology - CRYPTO 2025*, 2025.

CM21. Geoffroy Couteau and Pierre Meyer. Breaking the circuit size barrier for secure computation under quasi-polynomial LPN. In *Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021, Part II*, volume 12697 of *Lecture Notes in Computer Science*, pages 842–870, Zagreb, Croatia, October 17–21, 2021. Springer, Heidelberg, Germany.

CMPR23. Geoffroy Couteau, Pierre Meyer, Alain Passelègue, and Mahshid Riahinia. Constrained pseudorandom functions from homomorphic secret sharing. In *Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023, Part III*, volume 14006 of *Lecture Notes in Computer Science*, pages 194–224, Lyon, France, April 23–27, 2023. Springer, Heidelberg, Germany.

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. Springer, Heidelberg, Germany.

CS02. Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In *Lars R. Knudsen, editor, Advances in Cryptology - EUROCRYPT 2002*, volume 2332 of *Lecture Notes in Computer Science*, pages 45–64, Amsterdam, The Netherlands, April 28 – May 2, 2002. Springer, Heidelberg, Germany.

DJN10. Ivan Damgård, Mads Jurik, and Jesper Buus Nielsen. A generalization of paillier's public-key system with applications to electronic voting. *International Journal of Information Security*, 9:371–385, 2010.

Ds17. Jack Doerner and abhi shelat. Scaling ORAM for secure computation. In *Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017: 24th Conference on Computer and Communications Security*, pages 523–535, Dallas, TX, USA, October 31 – November 2, 2017. ACM Press.

FKN94. Uriel Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation (extended abstract). In *26th Annual ACM Symposium on Theory of Computing*, pages 554–563, Montréal, Québec, Canada, May 23–25, 1994. ACM Press.

GGM86. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. *Journal of the ACM*, 33(4):792–807, October 1986.

GJM03. Philippe Golle, Stanislaw Jarecki, and Ilya Mironov. Cryptographic primitives enforcing communication and storage complexity. In *Matt Blaze, editor, FC 2002: 6th International Conference on Financial Cryptography*, volume 2357 of *Lecture Notes in Computer Science*, pages 120–135, Southampton, Bermuda, March 11–14, 2003. Springer, Heidelberg, Germany.

Hea24. David Heath. Efficient arithmetic in garbled circuits. In *Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024, Part V*, volume 14655 of *Lecture Notes in Computer Science*, pages 3–31, Zurich, Switzerland, May 26–30, 2024. Springer, Heidelberg, Germany.
HKN24. David Heath, Vladimir Kolesnikov, and Lucien K. L. Ng. Garbled circuit lookup tables with logarithmic number of ciphertexts. In Marc Joye and Gregor Leander, editors, *Advances in Cryptology - EUROCRYPT 2024, Part V*, volume 14655 of *Lecture Notes in Computer Science*, pages 185-215, Zurich, Switzerland, May 26-30, 2024. Springer, Heidelberg, Germany.

IK00. Yuval Ishai and Eyal Kushlevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In *41st Annual Symposium on Foundations of Computer Science*, pages 294-304, Redondo Beach, CA, USA, November 12-14, 2000. IEEE Computer Society Press.

IKNP03. Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Dan Boneh, editor, *Advances in Cryptology - CRYPTO 2003*, volume 2729 of *Lecture Notes in Computer Science*, pages 145-161, Santa Barbara, CA, USA, August 17-21, 2003. Springer, Heidelberg, Germany.

ILL25. Yuval Ishai, Hanjun Li, and Huijia Lin. A unified framework for succinct garbling from homomorphic secret sharing. In *Advances in Cryptology - CRYPTO 2025*, 2025.

KPTZ13. Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, *ACM CCS 2013: 20th Conference on Computer and Communications Security*, pages 669-684, Berlin, Germany, November 4-8, 2013. ACM Press.

LP09. Yehuda Lindell and Benny Pinkas. A proof of security of Yao's protocol for two-party computation. *Journal of Cryptology*, 22(2):161-188, April 2009.

MORS24. Pierre Meyer, Claudio Orlandi, Lawrence Roy, and Peter Scholl. Rate-1 arithmetic garbling from homomorphic secret-sharing. In *Theory of Cryptography Conference - TCC 2024*, 2024. https://eprint.iacr.org/2024/820.

MORS25. Pierre Meyer, Claudio Orlandi, Lawrence Roy, and Peter Scholl. Silent circuit relinearisation: Sublinear-size (boolean and arithmetic) garbled circuits from DCR. In *Advances in Cryptology - CRYPTO 2025*, 2025.

OSY21. Claudio Orlandi, Peter Scholl, and Sophia Yakoubov. The rise of paillier: Homomorphic secret sharing and public-key silent OT. In Anne Canteaut and François-Xavier Standaert, editors, *Advances in Cryptology - EUROCRYPT 2021, Part I*, volume 12696 of *Lecture Notes in Computer Science*, pages 678-708, Zagreb, Croatia, October 17-21, 2021. Springer, Heidelberg, Germany.

Pai99. Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques Stern, editor, *Advances in Cryptology - EUROCRYPT'99*, volume 1592 of *Lecture Notes in Computer Science*, pages 223-238, Prague, Czech Republic, May 2-6, 1999. Springer, Heidelberg, Germany.

Roy22. Lawrence Roy. SoftSpokenOT: Quieter OT extension from small-field silent VOLE in the minicrypt model. In Yevgeniy Dodis and Thomas Shrimpton, editors, *Advances in Cryptology - CRYPTO 2022, Part I*, volume 13507 of *Lecture Notes in Computer Science*, pages 657-687, Santa Barbara, CA, USA, August 15-18, 2022. Springer, Heidelberg, Germany.

RS21. Lawrence Roy and Jaspal Singh. Large message homomorphic secret sharing from DCR and applications. In Tal Malkin and Chris Peikert, editors, *Advances in Cryptology - CRYPTO 2021, Part III*, volume 12827 of *Lecture Notes in Computer Science*, pages 687-717, Virtual Event, August 16-20, 2021. Springer, Heidelberg, Germany.

Ser24. Sacha Servan-Schreiber. Constrained pseudorandom functions for inner-product predicates from weaker assumptions. In Kai-Min Chung and Yu Sasaki, editors, *Advances in Cryptology - ASI-ACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part II*, volume 15485 of *Lecture Notes in Computer Science*, pages 232-265. Springer, 2024.

Yao86. Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In *27th Annual Symposium on Foundations of Computer Science*, pages 162-167, Toronto, Ontario, Canada, October 27-29, 1986. IEEE Computer Society Press.

ZRE15. Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole - reducing data transfer in garbled circuits using half gates. In Elisabeth Oswald and Marc Fischlin, editors, *Advances in Cryptology - EUROCRYPT 2015, Part II*, volume 9057 of *Lecture Notes in Computer Science*, pages 220-250, Sofia, Bulgaria, April 26-30, 2015. Springer, Heidelberg, Germany.

## A Continued Preliminaries

**Notation.** 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$. 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. Given an integer $x$, we write $[x \bmod B]$ to denote the integer remainder of the euclidean division of $x$ by $B$. 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 a parameter $p \in (0, 1)$, we let $\text{Ber}(p)$ denote the Bernoulli distribution that outputs 0 with probability $1-p$ and 1 with probability $p$.

## A.1 Arithmetic Garbled Circuits

We consider a model of arithmetic circuits consisting of addition, subtraction and multiplication gates with fan-in two. A circuit consists of a series of connected gates that computes some function over its input domain $\mathcal{D}$. We refer to the size of a circuit, denoted by $|C|$, as the number of gates in the circuit.

Our model and definitions are heavily borrowed from [BLLL23] and [MORS24]. In this work we will be considering two models of circuit computation, defined over different domains. We refer to a valid input as *admissible*; the output value of the circuit is defined only over admissible inputs.

**Modular Arithmetic Computation.** In this model, the domain of the circuit is defined to be the ring $\mathbb{Z}_N$. All input and intermediate computations are carried out over $\mathbb{Z}_N$. If $C$ has $n$ input wires, every input vector $\mathbf{x} \in \mathbb{Z}_N^n$ is considered admissible.

**Bounded Integer Computation.** In this model, the domain of the circuit is defined to be $\mathbb{Z}$ and there exists a bound $B = B(\lambda) \in \mathbb{N}$ that bounds the magnitude of circuit wire values. If $C$ has $n$ input wires, then an input vector $\mathbf{x} \in \mathbb{Z}^n$ is considered admissible with respect to bound $B$ if the inputs, outputs, and every intermediate wire value obtained during the evaluation of $C$ are in the range $[-B, B]$.

## Arithmetic Garbling

**Definition 22 (Arithmetic Garbled Circuit, adapted from [MORS24]).** Let $\mathbb{Z}_N$-modular arithmetic computation (resp. B-bounded integer computation) be the model of computation. A garbling scheme for a family of circuit classes $C = \{C_\lambda\}_{\lambda \in \mathbb{N}^*}$ for modular arithmetic computation (resp. B-bounded integer computation) with label space $\mathcal{L} = \mathcal{L}(\lambda)$ is a pair of PPT algorithms $\text{AGC} = (\text{AGC.Garble}, \text{AGC.Eval})$ with the following syntax and properties:

- **Garble(1^λ, C):** On input a security parameter $1^λ$ and a circuit $C \in C_\lambda$ with $n$ inputs, Garble outputs $n$ key pairs $(k_0^i, k_1^i)_{i \in [n]} \in \mathcal{L}$ and a garbled circuit $\hat{C}$.

- **Eval((L_i)_{i \in [n]}, \hat{C}):** On input $n$ input labels $(L_i)_{i \in [n]} \in \mathcal{L}^n$ and a garbled circuit $\hat{C}$, Eval outputs a value $y \in \mathbb{Z}_N$ (resp. $y \in [B]$).

- **Correctness.** A garbling scheme is correct if there exists a negligible function $\text{negl}(\lambda)$ such that for all $\lambda \in \mathbb{N}$, every circuit $C \in C_\lambda$ with $n$ inputs, and every $x_1, \dots, x_n \in \mathcal{X}^n$ where $\mathcal{X}$ is the set of admissible inputs of $C$, the following holds:

$$ \Pr \left[ \text{Eval}((L_i)_{i \in [n]}, \hat{C}) = \mathbb{Z} \ C(x_1, \dots, x_n) : \left( \begin{array}{l} ((k_0^i, k_1^i)_{i \in [n]}, \hat{C}) \leftarrow \text{Garble}(1^\lambda, C) \\ L_i \leftarrow k_0^i \cdot x_i + k_1^i \end{array} \right) \le \text{negl}(\lambda) \right] $$

- **Privacy.** A garbling scheme is secure if there exists a PPT simulator $\text{Sim}$ such that for all sequences of circuits $\{C_\lambda\}_{\lambda \in \mathbb{N}}$, where $C_\lambda \in C_\lambda$ with $n = n(\lambda)$ inputs, and every admissible sequence of inputs $\{(x_{1,\lambda}, \dots, x_{n,\lambda})\}_{\lambda \in \mathbb{N}}$, the following holds:

$$ \{\text{Sim}(1^{\lambda}, C_{\lambda}, y) : y \leftarrow C_{\lambda}(x)\} \approx_c \left\{ \left( (L_i)_{i \in [n]}, \hat{C} : \left( \begin{array}{l} ((k_0^i, k_1^i)_{i \in [n]}, \hat{C}) \leftarrow \text{Garble}(1^{\lambda}, C) \\ L_i \leftarrow k_0^i \cdot x_i + k_1^i \end{array} \right) \right\} \right\} $$

**Definition 23 (Rate of Arithmetic Garbled Circuit, adapted from [MORS24]).** Let $C$ be a class of arithmetic circuits, let $\text{AGC}$ be an arithmetic garbling scheme for $C$ with $\mathbb{Z}_N$-modular arithmetic computation (resp. B-bounded computation), and let $\ell = \log(N)$ (resp. $\ell = \log(2B+1)$). The rate of $\text{AGC}$ for $C$ is the quantity

$$ \text{rate} = \liminf_{C \in \mathcal{C}} \min_x \frac{(|C| + n)\ell}{|\hat{C}| + \sum_i \text{size}(k_0^i \cdot x_i + k_1^i)} $$

where the minimum is taken over admissible inputs to the circuit $C$, and the limit infimum is taken over all circuits in $C$.
## B Homomorphic Secret Sharing

We start by recalling the standard definition of homomorphic secret sharing, as well as of Restricted Multiplication Straight-line (RMS) programs which is the common model of computation in the context of HSS. Our definitions have been taken from [CMPR23].

**Definition 24 (Homomorphic Secret Sharing).** Let $\lambda$ be a security parameter. A Homomorphic Secret Sharing (HSS) scheme for a class of programs $\mathcal{P}$ which is defined over a ring $\mathcal{R}$ and has input space $\mathcal{I} \subseteq \mathcal{R}$ consists of three PPT algorithms (Setup, Input, Eval) such that:

* Setup($1^{\lambda}$) → (pk, (ek$_{0}$, ek$_{1}$)): On input the security parameter $\lambda$, the setup algorithm outputs a public key pk and a pair of evaluation keys (ek$_{0}$, ek$_{1}$).

* Input(pk, x) → (l$_{0}$, l$_{1}$): On input the public key pk and an input $x \in \mathcal{I}$, the input algorithm outputs a pair of input information (l$_{0}$, l$_{1}$).

* Eval($\sigma$, ek$_{\sigma}$, l$_{\sigma}$ = (l$_{\sigma}^{(1)}$, ..., l$_{\sigma}^{(\rho)}$), P) → y$_{\sigma}$: On input a party index $\sigma \in \{0, 1\}$, an evaluation key ek$_{\sigma}$, a vector of $\rho$ input values (l$_{\sigma}^{(1)}$, ..., l$_{\sigma}^{(\rho)}$), and a program $P \in \mathcal{P}$, the evaluation algorithm outputs the party $\sigma$'s corresponding share of the output y$_{\sigma}$.

We require scheme to satisfy the following two properties:

* **Correctness.** For any security parameter $\lambda \in \mathbb{N}$, and any program $P \in \mathcal{P}$ with input space $\mathcal{I} \subseteq \mathcal{R}$, we have:

$$ \Pr[y_0 - y_1 = P(x^{(1)}, \dots, x^{(\rho)})] \geq 1 - \text{negl}(\lambda), $$

where the probability is taken over (pk, (ek$_{0}$, ek$_{1}$)) ← Setup($1^{\lambda}$), (l$_{0}^{(i)}$, l$_{1}^{(i)}$) ← Input(pk, x$^{(i)}$) for $i \in [\rho]$, and y$_{\sigma}$ ← Eval($\sigma$, ek$_{\sigma}$, (l$_{\sigma}^{(1)}$, ..., l$_{\sigma}^{(\rho)}$), P), for $\sigma \in \{0, 1\}$.

* **Security.** For any PPT adversaries $\mathcal{A}, \mathcal{A}'$, and any bit $\sigma \in \{0, 1\}$ the following value should be negligible in $\lambda$:

$$ \Pr \left[ \begin{array}{l} (x_0, x_1, \text{state}) \leftarrow \mathcal{A}(1^{\lambda}) \\ (\text{pk}, (\text{ek}_0, \text{ek}_1)) \leftarrow \text{Setup}(1^{\lambda}) \\ b \stackrel{\$}{\leftarrow} \{0, 1\} \\ (l_0, l_1) \leftarrow \text{Input}(x_b) \\ b' \leftarrow \mathcal{A}'(\text{state}, \text{pk}, \text{ek}_{\sigma}, l_{\sigma}) \end{array} \right] - \frac{1}{2} . $$

We now remind the definition of Restricted Multiplication Straight-line (RMS) programs. RMS programs form a class of programs which encompasses polynomial-size branching programs and therefore NC¹ circuits. In an RMS program, the multiplication is restricted to happen between an input value and an intermediate value of the computation (so-called “memory” value).

**Definition 25 (RMS Programs).** An RMS program with magnitude bound $B$ is defined as a sequence of the instructions as follows:

- ConvertInput($l^x$) → $M^x$: Loads an input $x$ into memory.

- Add($M^x, M^y$) → $M^{x+y}$: Adds two memory values.

- Mul($l^x, M^y$) → $M^{x \cdot y}$: Multiplies an input value and a memory value to produce a memory value of their product.

- Output($M^x, n$) → $x \bmod n$: Outputs a memory value with respect to a modulus $n < B$.

### B.1 Template for RMS Programs

We now outline a template construction for HSS in the context of RMS programs, adapted from Section 4 of [CMPR23].

**Definition 26 (HSS Following the RMS Template).** A homomorphic secret sharing scheme HSS = (Setup, Input, MemGen, Eval) following the RMS template is scheme as defined in Definition 24 with an additional algorithm MemGen which serves to produce memory values as follows:

* MemGen($\sigma$, ek$_{\sigma}$, x) → $M_{\sigma}$: On input a party index $\sigma \in \{0, 1\}$, an evaluation key ek$_{\sigma}$, and an input $x \in \mathcal{I}$, the memory generator algorithm outputs a memory value $M_{\sigma}$.
Moreover, the Eval algorithm proceeds with sub-routines following the RMS operations ConvertInput, Add, Mul, Output as follows:

* Eval($\sigma$, ek$_\sigma$, $l_\sigma^{(1)}$, ..., $l_\sigma^{(\rho)}$), P) → y$_\sigma$: On input a party index $\sigma \in \{0, 1\}$, an evaluation key ek$_\sigma$, a vector of $\rho$ input values ($l_\sigma^{(1)}$, ..., $l_\sigma^{(\rho)}$), and an RMS program P, this algorithm follows the instructions of P and processes them as follows:

* ConvertInput($\sigma$, ek$_\sigma$, $l_\sigma^x$) → $M_\sigma^x$: This algorithm simply uses the MemGen and Mult algorithms as follows:

- Run MemGen($\sigma$, ek$_\sigma$, 1) → $M_\sigma^1$.

- Run Mult($\sigma$, ek$_\sigma$, $l_\sigma^x$, $M_\sigma^1$) → $M_\sigma^x$.

* Add($\sigma$, ek$_\sigma$, $M_\sigma^x$, $M_\sigma^y$) → $M_\sigma^{x+y}$: This algorithm directly adds the given memory values of $x$ and $y$. Namely, $M_\sigma^{x+y} = M_\sigma^x + M_\sigma^y$.

* Mul($\sigma$, ek$_\sigma$, $l_\sigma^x$, $M_\sigma^y$) → $M_\sigma^{x \cdot y}$: It multiplies an input value $l_\sigma^x$ and a memory value $M_\sigma^y$ and outputs a memory value of $x \cdot y$. The template does not impose any non-black box requirement on this algorithm.

* Output($\sigma$, $M_\sigma^x$, $n$) → $x \bmod n$: It uses $M_\sigma^x$ to output $x_\sigma \bmod n$.

Correctness and security properties are defined as in Definition 24.

Any HSS following the RMS template as defined above satisfies the following lemma, which states that one can evaluate share of $z \cdot P(x^{(1)}, \dots, x^{(\rho)})$ using only a memory value of $z$ (instead of an input value) together with the input values of the rest of variables ($x^{(1)}, \dots, x^{(\rho)}$). This property is key to our garbling scheme, as it allows non-interactive evaluations of pseudorandomly generated shares.

**Lemma 27.** Let HSS = (Setup, Input, MemGen, Eval) be scheme following the RMS template. There exists an extended evaluation algorithm ExtEval:

* ExtEval($\sigma$, ek$_\sigma$, $M_\sigma$, ($l_\sigma^{(1)}$, ..., $l_\sigma^{(\rho)}$), P) → y$_\sigma$: On input a party index $\sigma \in \{0, 1\}$, an evaluation key ek$_\sigma$, a single memory value $M_\sigma$, a vector of $\rho$ input values ($l_\sigma^{(1)}$, ..., $l_\sigma^{(\rho)}$), and an RMS program P, return a value $y_\sigma$ such that the following holds.

For any security parameter $\lambda \in \mathbb{N}$ and any RMS program P, we have:

$$ \Pr[y_0 - y_1 = z \cdot P(x^{(1)}, \dots, x^{(\rho)})] \geq 1 - \text{negl}(\lambda), \quad (3) $$

where the probability over (pk, (ek$_0$, ek$_1$)) ← Setup(1$^\lambda$), ($l_0^{(i)}$, $l_1^{(i)}$) ← Input(pk, $x^{(i)}$), $M_\sigma$ ← MemGen($\sigma$, ek$_\sigma$, z), and $y_\sigma$ ← ExtEval($\sigma$, ek$_\sigma$, $M_\sigma$, ($l_\sigma^{(1)}$, ..., $l_\sigma^{(\rho)}$), P), for $\sigma \in \{0, 1\}$, $i \in [\rho]$.

The proof of the above lemma is detailed in the supplementary material in Section B of [CMPR23]. In the HSS scheme from Paillier-ElGamal, the Input(pk, $x^{(i)}$) is a ciphertext of $x^{(i)}$.

## B.2 HSS based on Paillier-ElGamal

In this work, we will be working heavily with the Paillier-ElGamal Cryptosystem ([CS02], [BCP03]), which is essentially the ElGamal cryptosystem over the group $(\mathbb{Z}/N^2\mathbb{Z})^{\times}$. We borrow the description of Paillier-ElGamal from Appendix B of [OSY21]. We will be working with a mild variant of Paillier-ElGamal (2) with the only semantic difference that the secret key is sampled from $[2^{2\lambda}]$ instead of $[N^2]$; the rest of the description is identical to that of [OSY21]. The security of this cryptosystem can be easily proven based on the DCR and SEI assumptions.

**Definition 28 (S-bounded Short Exponent Indistinguishability Assumption).** Let $p$ and $q$ be primes of fixed length $n(\lambda)$ where $n$ is some polynomial function of $\lambda$ and let $N = pq$ be a Blum Integer. Consider a group $\mathbb{G}$ of unknown order $N\phi(N)$ with generator $g$. Let $S < N^2$ be an integer. The S-bounded Short Exponent Indistinguishability (SEI) assumption holds if for all PPT $\mathcal{A}$,

$$ \left| \Pr[z \stackrel{\$}{\leftarrow} [0, S-1] : \mathcal{A}(g^z) = 1] - \Pr[z \stackrel{\$}{\leftarrow} [N^2] : \mathcal{A}(g^z) = 1] \right| \leq \text{negl}(\lambda). $$

In this work, we set $S = 2^{2\lambda}$.
**Lemma 29 (Paillier-ElGamal Cryptosystem).** The Paillier-ElGamal cryptosystem is a CPA-secure encryption scheme iff the DCR assumption holds.

**Lemma 30 (Paillier-ElGamal Cryptosystem with Short Exponent).** The construction of 2 is a CPA-secure encryption scheme iff the DCR and the SEI assumptions hold.

*Proof.* Consider an adversary $\mathcal{A}$ which can distinguish between short-exponent Paillier-ElGamal ciphertexts with noticeable probability. We will show that, assuming the security of 'regular' Paillier-ElGamal, we can construct a distinguisher that can distinguish between elements of $N\phi(N)$ with small and large exponent. Our distinguisher works as follows. Given the challenge $(g, g^x)$ (where $x$ is sampled from either $[0, S-1]$ or $[N^2]$), the distinguisher $D$ publishes $pk = g^d$ and sends it to $\mathcal{A}$. In return, $\mathcal{A}$ responds with $(m_0, m_1)$, and $D$ chooses $r \stackrel{\$}{\leftarrow} [N^2]$ and responds with $(g^r, pk^r(1+N)^{m_1})$ as the challenge ciphertext. If $\mathcal{A}$ responds with 0 then $D$ outputs 1, otherwise $D$ outputs 0. Since the ciphertext always corresponds to a correct 'left'-encryption of the adversary's challenge, $\mathcal{A}$ outputs 0 with noticeable probability if $x \stackrel{\$}{\leftarrow} [0, S-1]$ and 1 otherwise. Thus, $D$ breaks the small exponent indistinguishability game, but this contradicts the SEI assumption. ■

## Paillier-ElGamal Cryptosystem with Short Exponent

PaillierEG.Gen(1^λ)

1: Sample $(N, p, q) \leftarrow \text{GenPQ}(1^\lambda)$.

2: Sample a random $g' \leftarrow [N^2]$.

3: Let $g = (g')^{2N} \bmod N^2$.

4: Sample $d \stackrel{\$}{\leftarrow} [2^{2\lambda}]$.

5: **return** $(N, g, pk = g^d \bmod N^2, sk = d)$

PaillierEG.Enc(pk, x)

1: Sample $r \stackrel{\$}{\leftarrow} [N^2]$.

2: **return** $ct = (g^r, pk^r(1+N)^x)$

PaillierEG.Dec(sk, ct = (ct₀, ct₁))

1: Let $ct' = ct_1(ct_0)^{-sk} \bmod N^2$.

2: **return** $x = (ct' - 1)/N$.

<caption>Fig. 2: The Paillier-ElGamal Cryptosystem with Short Exponent.</caption>

# C Constant-Rate Arithmetic Garbling over Small Integers

## C.1 Technical Overview: Constant-Rate Arithmetic Garbling over Small Integers

The starting point of our scheme is the recent work of [MORS24], which constructs constant-rate garbling for circuits with B-bounded integer arithmetic from the Decisional Composite Residuosity Assumption (DCR) using techniques derived from Homomorphic Secret Sharing (HSS). We begin by recalling the construction of [MORS24].

**Homomorphic Secret Sharing** Our techniques make heavy use of Homomorphic Secret Sharing (HSS). Informally, 2-party HSS allows parties to share an input into shares $x = (x_0, x_1)$ such that any party $P_i$ can evaluate any arbitrary function $f$ from a class $\mathcal{F}$ of admissible functions and obtain $y_i = \text{Eval}(i, f, x_i)$. The correctness requirement states that $y_0 + y_1 = f(x)$, and security requires each share to computationally hide $x$. HSS is implied by a number of different standard assumptions in the literature ([BGI16], [OSY21], [CM21]), and a plethora of different constructions are known
for a variety of circuit classes. In this work, we will be interested in HSS schemes where the Share algorithm supports a public-key style setup, ie. each party publishes a public key, and consequently, shared public and evaluation keys can be derived non-interactively. We (very informally) term such cryptosystems ‘HSS-compatible’.

**Arithmetic Garbling from HSS** At a high level, the garbling scheme of [MORS24] follows the template introduced in Section 2.2, where the scheme utilizes HSS to allow the parties to non-interactively compute shares of cross terms. In particular, the garbler begins by generating an HSS-compatible key pair (sk, pk). Then by setting $\Delta = \text{sk}$, the garbler can provide $\text{Enc}_{\text{pk}}(\text{sk}^{-1})$ as one-time garbling cost, along with $\text{Enc}_{\text{pk}}(\langle x \rangle_{\text{G}})$, $\text{Enc}_{\text{pk}}(\langle y \rangle_{\text{G}})$ and $\text{Enc}_{\text{pk}}(\langle \text{sk} \cdot x \rangle_{\text{G}})$ for each gate as garbling material. Recall that the distributed discrete log algorithm (DDlog) allows parties to non-interactively compute, using as input an HSS-compatible encryption of $A$ and a subtractive share of $\text{sk} \cdot B$, sharings of $\text{sk} \cdot AB$; full details can be found in Section 3.4 of [MORS24]. With this in place, the parties can now do the following:

1. Run $\text{DDlog}(\text{Enc}_{\text{pk}}(\langle y \rangle_{\text{G}}), \langle \text{sk} \cdot x \rangle)$ → $\langle \text{sk} \cdot x \cdot \langle y \rangle_{\text{G}} \rangle$, $\text{DDlog}(\text{Enc}_{\text{pk}}(\langle x \rangle_{\text{G}}), \langle y \rangle)$ → $\langle \text{sk} \cdot y \cdot \langle x \rangle_{\text{G}} \rangle$, and $\text{DDlog}(\text{Enc}_{\text{pk}}(\langle \text{sk} \cdot x \rangle_{\text{G}}), \langle y \rangle)$ → $\langle \text{sk} \cdot y \cdot \langle \text{sk} \cdot x \rangle_{\text{G}} \rangle$.

2. Remove the sk factor in the sharings by running $\text{DDlog}(\text{Enc}_{\text{pk}}(\text{sk}^{-1}), \langle \text{sk} \cdot x \cdot \langle y \rangle_{\text{G}} \rangle) \rightarrow \langle x \cdot \langle y \rangle_{\text{G}} \rangle$, $\text{DDlog}(\text{Enc}_{\text{pk}}(\text{sk}^{-1}), \langle \text{sk} \cdot y \cdot \langle x \rangle_{\text{G}} \rangle) \rightarrow \langle y \cdot \langle x \rangle_{\text{G}} \rangle$, and $\text{DDlog}(\text{Enc}_{\text{pk}}(\text{sk}^{-1}), \langle \text{sk} \cdot y \cdot \langle \text{sk} \cdot x \rangle_{\text{G}} \rangle) \rightarrow \langle y \cdot \langle \text{sk} \cdot x \rangle_{\text{G}} \rangle$.

The garbler can then set his share of $z$ to be $\langle x \rangle_{\text{G}} \cdot \langle y \rangle_{\text{G}} - \langle x \cdot \langle y \rangle_{\text{G}} \rangle_{\text{G}} - \langle y \cdot \langle x \rangle_{\text{G}} \rangle_{\text{G}}$ and vice-versa. Similarly, the parties can compute shares of $\text{sk} \cdot z$, maintaining the invariant. The procedure is continued till the global output gates have been reached, at which point the garbler can send its (precomputed) shares of output wires to reconstruct.

The above scheme works assuming the KDM-security of any HSS-compatible encryption scheme. When instantiated using Damgard-Jurik ([RS21] shows that this scheme is HSS-compatible), the asymptotic rate of the scheme comes out to be approximately 1/3. [MORS24] also carries a number of optimizations to obtain a scheme with a rate arbitrarily close to 1, but the bare template remains the same. We stop and make a note of two observations here, motivated by [MORS24]'s use of the Damgard-Jurik cryptosystem.

- First, note that the Damgard-Jurik cryptosystem is parametrized by two numbers: a constant $\zeta > 2$ and an RSA modulus $N$, setting the plaintext space to be $\mathbb{Z}/N^{\zeta}\mathbb{Z}$ and the ciphertext space to be $\mathbb{Z}/N^{\zeta+1}\mathbb{Z}$. In particular, to preserve security, the scheme requires the share sizes to scale as $\text{poly}(N)$.

- Secondly, the DDlog algorithm of [RS21] has a probability of failure with large plaintexts, restricting garbling to $B$-bounded integers where $B \approx N^{\zeta-1}/2^{\kappa}$ with a statistical security parameter $\kappa$.

**Small-Integer Garbling with Paillier-ElGamal** Our first contribution is a constant-rate, $B$-bounded arithmetic garbling scheme based on the circular security of the Paillier-ElGamal cryptosystem with a short exponent that supports small integers (of size $B \approx 2^{O(\lambda)}$). Our motivation is simple: an immediate way to overcome the problems inherent to the Damgard-Jurik garbling implementation is to instantiate HSS-based garbling from a different HSS-compatible encryption scheme. [OSY21] shows a promising construction of HSS from the Paillier-ElGamal Cryptosystem (Figure 2). However, simply instantiating the above HSS template using Paillier-ElGamal does not lead to any improvement in domain size.

- The plaintext space of Paillier-ElGamal is $\mathbb{Z}/N\mathbb{Z}$, which is still proportional to the size of the RSA modulus. Furthermore, this space also needs to be able to contain authenticated shares of wire values, i.e., $\langle \text{sk} \cdot x \rangle$ for a wire $x$, where sk is chosen from $[N^2]$.

- The ciphertext space is $\mathbb{Z}/N^2\mathbb{Z}$, which is too large – simply instantiating the scheme above leads to a far worse rate of 1/6.

With this in mind, we outline a series of techniques that lead to an arithmetic garbling scheme for integers of size $2^{O(\lambda)}$ with rate (close to) 1/2.

**Reducing the size of the plaintext space.** We can alleviate the first issue by additionally relying on a well-known variant of the Paillier-ElGamal cryptosystem with short exponent. Informally
speaking, the S-bounded Small Exponent Indistinguishability Assumption (SEI, Definition 28) states that given a group $\mathbb{G}$ and generator $g$, a PPT adversary cannot distinguish between random $g^a$ and $g^b$ where $a \stackrel{\$}{\leftarrow} [0, S - 1]$ and $b \stackrel{\$}{\leftarrow} \bar{\mathbb{G}}$. Applying this to the Paillier-ElGamal group of unknown order $N\phi(N)$, we can ensure that the encryption scheme remains secure even if $sk$ is bounded above by a small constant, say $2^{2\lambda}$.

While the previous discussion allows us to reduce the size of $sk$, letting the authenticated share $\langle sk \cdot x \rangle$ fit into the plaintext space, the underlying problem with the size of the plaintext space being too large remains. However, we can, at this point, rely on an observation made in previous works (including [OSY21]) to reduce the bit-length of both shares to size $O(\lambda)$. The core idea is this: a single invocation of DDlog returns substractive shares of the output over $\mathbb{Z}/N\mathbb{Z}$. If we want to convert these to shares over the integers, however, then assuming that the output $\langle x \rangle$ of DDlog is randomly distributed$^8$, restricting $x$ to be small immediately implies that the shares are already over $\mathbb{Z}$ with high probability. In particular, if $x$ is bounded by $N/2^\kappa$ for some statistical parameter $\kappa$, the formed shares will be over $\mathbb{Z}$ with probability except $2^\kappa$; if we restrict $B$ to, say, $2^{2\lambda}$, this probability is negligible. Our key observation is that with this in place, both the garbler and the evaluator can perform a round of modular reduction over $2^{O(\lambda)}$ on their shares and still obtain valid (substractive) shares of $x$ with negligible correctness error. Concretely, if the reduction is performed modulo $2^{3\lambda}$, then the probability of shares being malformed is negligible. Thus, the bitlength of the reduced shares is $\approx 3\lambda$. Setting this to be $B$, we obtain $B = 2^{3\lambda}$, as wished.

Combining the two approaches, our scheme achieves a quantitative reduction of share size (and hence, $B$). In practice, this allows us to set $B$ as low as 256 bits, an improvement from the previously known best value of $\approx 4000$ bits.

**Choosing garbler shares pseudorandomly.** The second problem is harder to solve. It is clear that in order to achieve a competitive rate, the garbling material cannot consist of ciphertexts. We make two key observations here: first, HSS allows parties to evaluate more than just a single DDlog instance; it allows a non-interactive share conversion for any $\text{NC}^1$ function of an encrypted input, and second the garbler's shares contain no information about the secret (by definition, since they must be formed before the evaluator receives the garbled circuit) and hence can be defined to be pseudorandom.

We construct our scheme as follows. Let $\text{id}_x$ be the label referring to the identity of the wire carrying the value $x$; this value is completely independent of $x$. The garbler can sample a key $k$ for a low-depth PRF$^9$ and set for any wire $\text{id}_x$ (which we can colloquially refer to as $x$) its shares $(\langle x \rangle_{\mathbb{G}}, \langle sk \cdot x \rangle_{\mathbb{G}}) := \text{PRF}_k(\text{id}_x)$. For convenience, we can view $\text{PRF}_k(w) = (\text{PRF}_k^1(w), \text{PRF}_k^2(w))$. As before, parties maintain the invariant $(\langle x \rangle, \langle sk \cdot x \rangle)$ for every wire $x$. However, note now that addition gates are no longer free since the garbler's share of the output of an addition gate $z = x \pm y$ is defined to be $\text{PRF}_k(\text{id}_z) \neq \text{PRF}_k(\text{id}_x) + \text{PRF}_k(\text{id}_y)$ except with negligible probability. Thus, the garbler sends a fresh shift

$$ (\langle x \rangle_{\mathbb{G}}, \langle sk \cdot x \rangle_{\mathbb{G}}) \pm (\langle y \rangle_{\mathbb{G}}, \langle sk \cdot y \rangle_{\mathbb{G}}) - \text{PRF}_k(\text{id}_z) $$

for each $z$, which the evaluator adds to its share to maintain the invariant.

Now assume the parties encounter a multiplication gate with input wires $x$ and $y$ and output wire $z$. The garbler can then provide the evaluator with global ciphertexts $\text{Enc}_{\text{pk}}(k)$ and $\text{Enc}_{\text{pk}}(sk \cdot k)$. Assume that the chosen PRF has depth $O(\log(\lambda))$. The key ingredient of our construction is a procedure introduced in [CMPR23] that lets two parties, given ciphertexts $\text{Enc}_{\text{pk}}(A)$, $\text{Enc}_{\text{pk}}(sk \cdot A)$ for a PRF key $A$ and a substractive input sharing $(\langle B \rangle, \langle sk \cdot B \rangle)$ over $\mathbb{Z}$, use a special form of HSS (called HSS with simulatable memory shares in [CMPR23]) to compute substractive shares of $(\langle B \cdot \text{PRF}_A(c) \rangle, \langle sk \cdot B \cdot \text{PRF}_A(c) \rangle)$ over $\mathbb{Z}$ for any $c$ of their choice. We refer the reader to Appendix B.1 for an outline of the method of [CMPR23].

In particular, the parties can use the ciphertexts of $k$ to compute $\langle y \cdot \text{PRF}_k^1(\text{id}_x) \rangle, \langle sk \cdot y \cdot \text{PRF}_k^2(\text{id}_x) \rangle$ and $\langle x \cdot \text{PRF}_k^1(\text{id}_y) \rangle$, which are the required cross-terms in Equation (1) and Equation (2), and hence can set their shares appropriately. However, note that with this in place, there is also another invariant: the garbler's share of $(z, sk \cdot z) = (x \cdot y, sk \cdot x \cdot y)$ is necessarily defined to be $\text{PRF}_k(\text{id}_z)$. Let $(\langle z \rangle'_{\mathbb{G}}, \langle sk \cdot z \rangle'_{\mathbb{G}})$

<footnote>$^8$ In general, this is non-trivial; however the parties can ensure it to be so by adding, say, a PRG output with range $[N]$ to their obtained shares.</footnote>

<footnote>$^9$ The construction of such a PRF is known from several standard assumptions, including DDH and DCR.</footnote>
be the computed share of the garbler immediately after the HSS evaluation, defined as

$$ \langle z \rangle'_{\mathcal{G}} := \mathrm{PRF}_{k}^{1}(\mathrm{id}_{x}) \cdot \mathrm{PRF}_{k}^{1}(\mathrm{id}_{y}) - \langle x \cdot \mathrm{PRF}_{k}^{1}(\mathrm{id}_{y}) \rangle_{\mathcal{G}} - \langle y \cdot \mathrm{PRF}_{k}^{1}(\mathrm{id}_{x}) \rangle_{\mathcal{G}} \quad (4) $$

$$ \langle \mathrm{sk} \cdot z \rangle'_{\mathcal{G}} := \mathrm{PRF}_{k}^{2}(\mathrm{id}_{x}) \cdot \mathrm{PRF}_{k}^{2}(\mathrm{id}_{y}) - \langle \mathrm{sk} \cdot x \cdot \mathrm{PRF}_{k}^{1}(\mathrm{id}_{y}) \rangle_{\mathcal{G}} - \langle y \cdot \mathrm{PRF}_{k}^{2}(\mathrm{id}_{x}) \rangle_{\mathcal{G}} \quad (5) $$

Contrast this with the invariant, which sets the actual share $(\langle z \rangle_{\mathcal{G}}, \langle \mathrm{sk} \cdot z \rangle_{\mathcal{G}}) := \mathrm{PRF}_{k}(\mathrm{id}_{z})$. To maintain this, the garbler sends two (plaintext) shifts $\langle z \rangle_{\mathcal{G}} - \langle z \rangle'_{\mathcal{G}}$ and $\langle \mathrm{sk} \cdot z \rangle_{\mathcal{G}} - \langle \mathrm{sk} \cdot z \rangle'_{\mathcal{G}}$ as garbling material which the evaluator can add to its own shares to adjust them appropriately. The resulting invariant is shares of $(z, \mathrm{sk} \cdot z)$ where the garbler's share is defined to be $\mathrm{PRF}_{k}(\mathrm{id}_{z})$, and the evaluation can continue.

The per-gate garbling material is the size of two plaintexts, setting the scheme's rate close to 1/2. When instantiated with Paillier-ElGamal and the small exponent assumption, the scheme also supports small integers of size $2^{O(\lambda)}$.

We briefly mention the security of the above sketch requires a variant of circular security for the underlying Paillier-ElGamal cryptosystem, owing to the fact that the evaluator can see an encryption of the PRF key, which is used to pseudorandomly mask (the garbler's computed share of) $\mathrm{sk} \cdot z$. A more involved technical discussion can be found in Appendix C.2.

## C.2 Small-Integer Garbling from Circular Security of Paillier-ElGamal with Constant Rate

**HSS Share Reduction with Paillier-ElGamal** The starting point of our construction for small-integer garbling with constant rate is a share reduction mechanism that allows parties to non-interactively perform homomorphic secret sharing from DCR that supports smaller share sizes. Recall from the discussion in Appendix C.1 that our techniques heavily rely on homomorphic secret sharing instantiated with the Paillier-ElGamal Cryptosystem with Small Exponent (henceforth referred to as simply Paillier-ElGamal). Natively, this form of HSS follows the HSS template for RMS programs described in Definition 26. In this setting, both parties maintain Memory Shares $M^x$ of any intermediate value $x$ required in the computation; these memory shares are of the form $M^x := (\langle x \rangle, \langle \mathrm{sk} \cdot x \rangle)$ where the shares are interpreted as subtractive shares over the integers modulo $N$, where $N$ is the RSA modulus associated with the Paillier-ElGamal instantiation. A full description of how HSS is constructed from Paillier-ElGamal can be found in Appendix B of [OSY21].

The key to our construction involves a technique that allows parties to reduce the size of intermediate memory shares from a subtractive sharing over $N$ to a subtractive sharing over the integers modulo $2^{O(\lambda)}$. In this section, we introduce our (slightly modified) DDlog algorithm over reduced shares for Paillier-ElGamal.

Let $(N, g, k_{\mathrm{DDlogRS}})$ be a CRS where $(N, p, q) \stackrel{\$}{\leftarrow} \mathrm{GenPQ}(1^{\lambda})$, $g = (g')^{2N} \bmod N^2$ where $g' \stackrel{\$}{\leftarrow} [N^2]$, and $k_{\mathrm{DDlogRS}}$ is a randomly sampled (public) PRF key for a pseudorandom function $\mathrm{PRF}_{\mathrm{DDlogRS}}$: $\{0, 1\}^{\lambda} \times \{0, 1\}^{\mathrm{id}(\lambda)} \to [N]$. Let $x, y \in \{0, 1\}^{k\lambda}$ be integers such that arithmetic is $2^{(k-1)\lambda}$-bounded, ie. $xy$ does not exceed $2^{(k-1)\lambda}$ where $k > 1$. Assume that $(\mathrm{pk}, \mathrm{sk})$ is an honestly generated Paillier-ElGamal key pair. The DDlogRS algorithm then takes as input a Paillier-ElGamal ciphertext pair $c = \mathrm{Enc}_{\mathrm{pk}}(x), c' = \mathrm{Enc}_{\mathrm{pk}}(\mathrm{sk} \cdot x)$ and subtractive memory shares $(\langle y \rangle, \langle \mathrm{sk} \cdot y \rangle)$ over the integers and outputs correct subtractive shares $(\langle xy \rangle, \langle \mathrm{sk} \cdot xy \rangle)$ over $[2^{k\lambda}] \times [2^{(k+2)\lambda}]$ with overwhelming probability. Here, we use $\sigma \in \{0, 1\}$ to denote the party ID.

$$ \mathrm{DDlogRS}(N, k, \sigma, c = (c_0, c_1), c' = (c'_0, c'_1), (\langle y \rangle_{\sigma}, \langle \mathrm{sk} \cdot y \rangle_{\sigma})) $$

1. Define $(g_{\sigma}, g'_{\sigma}) := (c_1^{\langle y \rangle_{\sigma}} \cdot c_0^{-\langle \mathrm{sk} \cdot y \rangle_{\sigma}}, c_1^{\langle y \rangle_{\sigma}} \cdot c_0^{-\langle \mathrm{sk} \cdot y \rangle_{\sigma}})$

2. Compute $a_{\sigma}, a'_{\sigma} < N$ such that $g_{\sigma} = a_{\sigma} + a'_{\sigma} N$

3. Compute $b_{\sigma}, b'_{\sigma} < N$ such that $g'_{\sigma} = b_{\sigma} + b'_{\sigma} N$

4. Set $z_{\sigma} := (a'_{\sigma} a_{\sigma}^{-1} \bmod N) + \mathrm{PRF}_{\mathrm{DDlogRS}}(\mathrm{id}) \bmod 2^{k\lambda}$

5. Set $z'_{\sigma} := (b'_{\sigma} b_{\sigma}^{-1} \bmod N) + \mathrm{PRF}_{\mathrm{DDlogRS}}(\mathrm{id}') \bmod 2^{(k+2)\lambda}$

6. return $(z_{\sigma}, z'_{\sigma})$

**Lemma 31.** The outputs $(z_{\sigma}, z'_{\sigma})$ of DDlogRS are correctly obtained subtractive shares of $(xy, \mathrm{sk} \cdot xy)$.
**Proof.** We note that the only difference between our algorithm DDlogRS and the multiplication procedure outlined in Section B.1 of [OSY21] is that we perform a second reduction modulo $2^{k\lambda}$ and $2^{(k+2)\lambda}$ in Steps 4 and 5. Hence, the shares $A_\sigma := (a'_\sigma a_\sigma^{-1} \bmod N) + \text{PRF}_{\text{DDlogRS}}(\text{id})$ and $B_\sigma := (b'_\sigma b_\sigma^{-1} \bmod N) + \text{PRF}_{\text{DDlogRS}}(\text{id}')$ are correctly computed subtractive shares over $[N]$. Furthermore, by the security of $\text{PRF}_{\text{DDlogRS}}$, the shares are also indistinguishable from uniform in $\mathbb{Z}_N$. We thus only need to show that $z_\sigma$ and $z'_\sigma$ are subtractive shares over $[2^{k\lambda}]$ and $[2^{(k+2)\lambda}]$ respectively. To do this, note that $z_1 - z_0 \ge xy$ so long as $z_1 \ge xy$. However, this is only possible for $xy \le 2^{(k-1)\lambda}$ possible values of $z_1$, and since $z_1$ is uniform, it happens with probability $2^{-\lambda} = \text{negl}(\lambda)$. Thus, the shares are well-formed with overwhelming probability in $\lambda$. ■

By replacing every instance of input multiplication in the HSS scheme from Paillier-ElGamal in Section B.1 of [OSY21] with DDlogRS, we immediately obtain an HSS scheme with small shares from Paillier-ElGamal with small exponent. Since this scheme follows the HSS template for RMS programs in Definition 26, it can be equipped with the ExtEval algorithm that allows for computation of small shares of $(y \cdot P(x))$ for any input share $x$ if $(y \cdot P(x))$ is $2^{k\lambda}$-bounded.

**Remark 32.** For our purposes, we will require a slightly modified version of the algorithm that outputs complete memory shares $M^{y \cdot P(x)}$ of $(y \cdot P(x))$. Henceforth, we assume the output of ExtEval as defined in Lemma 27 to output a memory value $M_g^y$, where $M_0^y - M_1^y = (z \cdot P(x^{(1)}, \dots, x^{(\rho)}), \text{sk} \cdot z \cdot P(x^{(1)}, \dots, x^{(\rho)}))$ with all but negligible probability. When equipped with DDlogRS, this scheme outputs reduced memory shares over the integers. Our algorithm ExtEval as used in Appendix C.2 uses this modified ExtEval procedure as an intermediary.

**Rate-1/2 Garbling with Pseudorandom Garbler Shares** We provide a formal specification along with proofs of correctness and security of our rate-1/2 garbling scheme below; a high-level description was covered in Appendix C.1. Our scheme requires a circular-secure variant of Paillier-ElGamal, which (as far as we know) is not equivalent to any known circular-security assumptions. Recall from Appendix C.1 that our scheme requires the garbler's share to be defined pseudorandomly as $\text{PRF}(k_{\text{PRF}}, \text{id}_w)$ for some each wire $w$. In order to be able to compute shares of the cross terms defined in Equation (1) and Equation (2) the parties employ the ExtEval procedure to compute shares of the form $(x \cdot \text{PRF}(k_{\text{PRF}}, \text{id}_y))$ for each multiplication gate with input wires $x$ and $y$; these correspond to the required cross terms since the garbler's share of $y$ is defined as $\text{PRF}(k_{\text{PRF}}, \text{id}_y)$. However, the garbler's calculated cross terms, which define its calculated share of $xy$ are different from $\text{PRF}(k_{\text{PRF}}, \text{id}_{xy})$. In order to maintain this invariant, the garbler must send a shift $((xy)_G, (\text{sk} \cdot xy)_G) - \text{PRF}(k_{\text{PRF}}, \text{id}_{xy})$ which the evaluator adds to its own share, setting it to be $(xy, \text{sk} \cdot xy) - \text{PRF}(k_{\text{PRF}}, \text{id}_{xy})$. In order to calculate this value using HSS, the evaluator receives an input share $l^{k_{\text{PRF}}}$ corresponding to the input key. Hence, the evaluator's view includes two separate ciphertexts: a public-key encryption of a symmetric key $k_{\text{PRF}}$, and a symmetric key encryption of the secret key $\text{sk}$. This is similar to the setting of *hybrid encryption* in the real world, in which parties first use a PKI to establish a symmetric key and then use that symmetric key for efficient encryption and decryption. While the security of hybrid encryption can be proved secure in the standard model, the view of the evaluator in our construction consists of ciphertexts that are *key-dependent*, which is not covered by standard security definitions of hybrid encryption. We thus introduce a natural variant of circular security for the hybrid setting that formally captures the relevant security notion. We term this assumption as *circular security of the hybrid* and provide a full specification below.
In the following definition, $F$ and $F'$ are function classes corresponding to the functions of the secret key that are being encrypted by the public-key and symmetric-key encryption scheme respectively.

**Definition 33 (F, F'-Circular Security of ($\mathcal{E}, \mathcal{E'}$)-Hybrid).** Let $\mathcal{E} = (\text{Gen}, \text{Enc}, \text{Dec})$ be a public-key encryption scheme with plaintext space $\mathcal{M}$, ciphertext space $\mathcal{C}$ and key spaces $\mathcal{SK}$ and $\mathcal{PK}$, and let $\mathcal{E}' = (\text{Gen}', \text{Enc}', \text{Dec}')$ be a symmetric-key encryption scheme with key space $\mathcal{K}$, plaintext space $\mathcal{M}'$, and ciphertext space $\mathcal{C}'$. Furthermore, let $F \subseteq \mathcal{K} \times \mathcal{SK} \to \mathcal{M}'$ and $F' \subseteq \mathcal{K} \times \mathcal{SK} \to \mathcal{M}$ be function classes. We say that the $(\mathcal{E}, \mathcal{E}')$-hybrid is $F, F'$-circular secure if for every polynomial time algorithm $A$,