$$
\left| \Pr \left[ \mathcal{A}^{\mathcal{O}_{F,k,sk,0}, \mathcal{O}_{F',k,sk,0}}(1^{\lambda}) = 1 : \begin{array}{l} k \stackrel{\$}{\leftarrow} \mathcal{K} \\ (\mathit{sk}, \mathit{pk}) \stackrel{\$}{\leftarrow} \mathrm{Gen}(1^{\lambda}) \end{array} \right] - \Pr \left[ \mathcal{A}^{\mathcal{O}_{F,k,sk,1}, \mathcal{O}_{F',k,sk,1}}(1^{\lambda}) = 1 : \begin{array}{l} k \stackrel{\$}{\leftarrow} \mathcal{K} \\ (\mathit{sk}, \mathit{pk}) \stackrel{\$}{\leftarrow} \mathrm{Gen}(1^{\lambda}) \end{array} \right] \right| \le \mathrm{negl}(\lambda)
$$

where $\mathcal{O}_{F,k,sk,0}$, $\mathcal{O}_{F,k,sk,1}$, $\mathcal{O}_{F',k,sk,0}$ and $\mathcal{O}_{F',k,sk,1}$ are as defined below.

$$
\begin{array}{l@{\quad}l}
\begin{array}{@{}c@{\,}c@{}}
  \mathcal{O}_{F,k,sk,0}(f) &
  \begin{array}{@{}c@{}}
    \text{if } f \notin F, \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}(\mathit{pk}, f(k, \mathit{sk}))
  \end{array}
\end{array}
&
\begin{array}{@{}c@{}}
  \mathcal{O}_{F,k,sk,1}(f) \\
  \begin{array}{@{}c@{}}
    \text{if } f \notin F, \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}(\mathit{pk}, 0^{|f(k,sk)|})
  \end{array}
\end{array}
\end{array}
$$

$$
\begin{array}{l@{\quad}l}
\begin{array}{@{}c@{\,}c@{}}
  \mathcal{O}_{F,k,sk,1}(f) &
  \begin{array}{@{}c@{}}
    \text{if } f \notin F, \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}(\mathit{pk}, 0^{|f(k,sk)|})
  \end{array}
\end{array}
&
\begin{array}{@{}c@{}}
  \mathcal{O}_{F',k,sk,1}(f) \\
  \begin{array}{@{}c@{}}
    \text{if } f \notin F', \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}'(k, f(k, \mathit{sk}))
  \end{array}
\end{array}
\end{array}
$$

$$
\begin{array}{l@{\quad}l}
\begin{array}{@{}c@{\,}c@{}}
  \mathcal{O}_{F',k,sk,0}(f) &
  \begin{array}{@{}c@{}}
    \text{if } f \notin F', \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}'(k, f(k, \mathit{sk}))
  \end{array}
\end{array}
&
\begin{array}{@{}c@{}}
  \mathcal{O}_{F',k,sk,1}(f) \\
  \begin{array}{@{}c@{}}
    \text{if } f \notin F', \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}'(k, 0^{|f(k,sk)|})
  \end{array}
\end{array}
\end{array}
$$

$$
\begin{array}{l@{\quad}l}
\begin{array}{@{}c@{\,}c@{}}
  \mathcal{O}_{F',k,sk,1}(f) &
  \begin{array}{@{}c@{}}
    \text{if } f \notin F', \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}'(k, 0^{|f(k,sk)|})
  \end{array}
\end{array}
&
\begin{array}{@{}c@{}}
  \mathcal{O}_{F',k,sk,1}(f) \\
  \begin{array}{@{}c@{}}
    \text{if } f \notin F', \text{ return } \perp \\
    \text{else } c \stackrel{\$}{\leftarrow} \text{Enc}'(k, 0^{|f(k,sk)|})
  \end{array}
\end{array}
\end{array}
$$

Remark 34. Our security proof will require a relatively strong variant of the above assumption. In particular, let $\mathcal{E}$ be the Paillier-ElGamal Encryption Scheme with Short Exponent, and let $\mathcal{E}'$ be a one-time pseudorandom mask for a fixed number of messages defined as $\{\text{PRF}_{\lambda}(k_{\text{PRF}}, \mathit{id}_i) \oplus m_i\}_{i \in \text{poly}(\lambda)}$ where $\mathit{id}_i$ is public, $m \in \{0, 1\}^{(2k+2)^\lambda}$ and $k_{\text{PRF}}$ is a uniform secret key; with our parameters, the above scheme is equivalent to a computational one-time pad encryption of a message of length $(n+|C|)(2k+2)$. Furthermore, we require $F$ to support only the *identity* and *product* functions $|\mathcal{K}: (k, \mathit{sk}) \mapsto k$ and $\times: (k, \mathit{sk}) \mapsto k \cdot \mathit{sk}$. The function class we require $F'$ to support is stronger and is defined recursively in Figure 3. Note here that our function class $F'$ is *circuit-dependent*, ie. the exact function depends on the topology of the circuit. In our reduction, we will consider an adversary that is allowed to make exactly one call to $\mathcal{O}_{F',k,sk,b}(F_{\text{prf-mask},C}(\cdot, \cdot, \mathit{id}_i))$ for each gate $i$ (by the security of our one-time pseudorandom mask encryption scheme, which breaks if multiple messages are allowed to be encrypted under the same mask). We note that the function is computable in time $\text{poly}(\lambda)$.

Remark 35. Implicit in our construction below is the fact that each gate of the circuit can have arbitrary fan-out. Note that our required garbling material per gate is a single plaintext shift<sub>z</sub>, which the evaluator uses to output a memory share $M_E^z$ of the output wire of the gate. By the security of HSS, this share computationally hides the value of z, and can thus be reused as an input share to the next ExtEval. The evaluator does not get any additional information about z by reusing the input share.

Remark 36. While the scheme as described in Protocol 2 does not allow the evaluation of additive/subtractive gates for free, there is a simple modification that enables this change. Note that polynomially-many linear combinations of PRF evaluations can be evaluated in parallel and reconstructed in logarithmic depth, and are hence representable in $NC^1$. Thus, the garbler and the evaluator can simply perform addition/subtraction on their shares when encountering an additive/subtractive gate, and the garbler can set the obtained linear combination of PRF values as its share of an input wire of a multiplicative gate. The evaluator (who knows the topology of the circuit, and thus can determine the precise combination) simply performs an ExtEval with the adjusted program description accordingly.

With this in mind, we can now give a full description of our scheme.
### The Function $F_{\text{prf-mask},C}$

**Parameters:** Let $C$ be a circuit and $k, \mathbf{s}, \mathbf{k}$ be the symmetric and secret key used in Definition 33 respectively. The inputs to $\text{ExtEval}$ are exactly as defined in Protocol 2.

1. For input wires, $F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z) = 0^{(2k+2)\lambda}$.

2. For an additive/subtractive gate $z = x \pm y$, $F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z) = -F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|x) \mp F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|y)$.

3. For a multiplicative gate $z = x \cdot y$,

$$F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z) = (F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z)_1, F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z)_2),$$

where

$$F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z)_1 = F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z)_1 \cdot F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|y)_1 \\ - \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_G\}, M_G^x, I^k, \text{PRF}_\lambda^1(\cdot, \mathbf{k}|y))_1 \\ - \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_G\}, M_G^y, I^k, \text{PRF}_\lambda^1(\cdot, \mathbf{k}|x))_1$$

$$F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z)_2 = F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|z)_2 \cdot F_{\text{prf-mask},C}(k, \mathbf{s}, \mathbf{k}|y)_1 \\ - \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_G\}, M_G^x, I^k, \text{PRF}_\lambda^1(\cdot, \mathbf{k}|y))_2 \\ - \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_G\}, M_G^y, I^k, \text{PRF}_\lambda^2(\cdot, \mathbf{k}|x))_1$$

<caption>Fig. 3: Function supported by the circular security assumption.</caption>

### Protocol Small Integer Garbling from Paillier-ElGamal with Small Exponent $AGC_{\text{PaillierEG}}$

**Parameters.** Let $\lambda$ be a security parameter and $k > 1$ be a global parameter. We consider $B$-bounded arithmetic circuits where $B \le 2^{(k-1)\lambda}$. We consider a circuit $C$ of size at most $\text{poly}(\lambda)$ with $n$ inputs, $m$ outputs and $s_\times$ multiplication gates; we represent the $i$th output wire by $\text{out}_i$. Let $\text{PaillierEG} = (\text{PaillierEG.Gen}, \text{PaillierEG.Enc}, \text{PaillierEG.Dec})$ be the Paillier-ElGamal cryptosystem with short exponent defined in Figure 2. Further define $\text{PRF}_\lambda : \{0, 1\}^\lambda \times (n+|C|) \to \{0, 1\}^{2k+2}$ to be a family of PRFs of depth at most $O(\log \lambda)$. For convenience, we define $\text{PRF}_\lambda^1 : \{0, 1\}^\lambda \times (n+|C|) \to \{0, 1\}^k$ and $\text{PRF}_\lambda^2 : \{0, 1\}^\lambda \times (n+|C|) \to \{0, 1\}^{k+2}$ as partial outputs of the PRF, ie. $\text{PRF}_\lambda = (\text{PRF}_\lambda^1, \text{PRF}_\lambda^2)$. Furthermore, note that $\text{PRF}_\lambda(\cdot, \mathbf{k}|x)$ for fixed $x$ is expressible as an RMS program, since $\text{PRF} \in \text{NC}^1$.

$AGC_{\text{PaillierEG}}.\text{Garble}(1^\lambda, C)$:

1. The garbler samples $k_{\text{PRF}}, k_{\text{DDlogRS}} \stackrel{\$}{\leftarrow} \{0, 1\}^\lambda$ and $(N, g, \text{pk}, \mathbf{s}) \stackrel{\$}{\leftarrow} \text{PaillierEG.Gen}(1^\lambda)$.

2. The garbler sets $I^{k_{\text{PRF}}} \leftarrow (\text{PaillierEG.Enc}(\text{pk}, k_{\text{PRF}}), \text{PaillierEG.Enc}(\text{pk}, \mathbf{s} \cdot k_{\text{PRF}}))$ and adds it to $\hat{C}$.

3. The garbler chooses a subtractive sharing of $1 ((\langle 1 \rangle_i, \langle \mathbf{s} \rangle_i)_{i \in \{E, G\}}$ and adds one share $M_E := (\langle 1 \rangle_E, \langle \mathbf{s} \rangle_E)$ to $\hat{C}$. Here $M_E$ is the evaluator's memory share of 1 that it uses to perform an HSS evaluation. The garbler initiates its own HSS with the share $M_G := (\langle 1 \rangle_G, \langle \mathbf{s} \rangle_G)$.

4. For each input wire $i$ and admissible value $x$, the garbler sets its share as $\text{PRF}_\lambda(k_{\text{PRF}}, \mathbf{k}|i)$. The label associated with $x$ is $L_x^i \leftarrow (x, \mathbf{s} \cdot x) + \text{PRF}_\lambda(k_{\text{PRF}}, \mathbf{k}|i)$.

5. For each internal wire $w$, the garbler maintains the sharing $(\langle w \rangle_G, \langle \mathbf{s} \cdot w \rangle_G)$. For each gate in parallel, the garbler can compute:

**Addition/Subtraction Gate** $z = x \pm y$. The garbler sets its label of wire $z$ to be $\text{PRF}_\lambda(k_{\text{PRF}}, \mathbf{k}|z)$ and adds $\text{shift}_z := -(\langle x \rangle_G, \langle (\mathbf{s} \cdot x) \rangle_G) \mp (\langle y \rangle_G, \langle (\mathbf{s} \cdot y) \rangle_G) - \text{PRF}_\lambda(k_{\text{PRF}}, \mathbf{k}|z)$ to $\hat{C}$.
**Multiplication Gate** $z = x \cdot y$. The garbler sets its label of wire $z$ to be $\text{PRF}_{\lambda}(k_{\text{PRF}}, \text{id}_y)$. It then computes

$$ \begin{align*} & (\langle x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{G}}, \langle \text{sk} \cdot x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{G}}) \\ & \leftarrow \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_{\text{G}}\}, M_{\text{G}}^{x}, l^{k_{\text{PRF}}}, \text{PRF}_{\lambda}^{1}(\cdot, \text{id}_y)) \\ & (\langle y \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{G}}, \langle \text{sk} \cdot y \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{G}}) \\ & \leftarrow \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_{\text{G}}\}, M_{\text{G}}^{y}, l^{k_{\text{PRF}}}, \text{PRF}_{\lambda}^{1}(\cdot, \text{id}_x)) \\ & (\langle y \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{G}}, \langle \text{sk} \cdot y \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{G}}) \\ & \leftarrow \text{ExtEval}(1, \{k_{\text{DDlogRS}}, M_{\text{G}}\}, M_{\text{G}}^{y}, l^{k_{\text{PRF}}}, \text{PRF}_{\lambda}^{2}(\cdot, \text{id}_x)) \end{align*} $$

and sets

$$ \text{shift}_z := (\text{shift}_z^1, \text{shift}_z^2), $$

where

$$ \begin{align*} \text{shift}_z^1 &= \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) - \langle x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{G}} \\ & \quad - \langle y \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{G}} - \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_z) \\ \text{shift}_z^2 &= \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_y) - \langle \text{sk} \cdot x \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{G}} \\ & \quad - \langle y \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{G}} - \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_z) \end{align*} $$

and adds $\text{shift}_z$ to $\hat{C}$.

6. The garbler outputs $((L_x^i)_{i \in [n]}, \hat{C} = (N, g, k_{\text{DDlogRS}}, l^{k_{\text{PRF}}}, M_E, (\text{shift}_i)_{i \in C}, \{\langle \text{out}_i \rangle_{\text{G}}\}_{i \in m}))$ where $x$ is over the set of admissible inputs.

$\text{AGC}_{\text{PaillierEG}}.\text{Eval}((L_i)_{i \in [n]}, \hat{C})$:

1. The evaluator sets its sharing of input wire $w_i$ as $((w_i)_{\text{E}}, (\langle \text{sk} \cdot w_i \rangle_{\text{E}})) := L_i$. It interprets $\hat{C}$ as $(N, g, k_{\text{DDlogRS}}, l^{k_{\text{PRF}}}, M_E, (\text{shift}_i)_{i \in C}, \{\langle \text{out}_i \rangle_{\text{G}}\}_{i \in m})$.

2. For each internal wire $w$, the evaluator maintains the sharing $((\langle w \rangle_{\text{E}}, (\langle \text{sk} \cdot w \rangle_{\text{E}})))$. It then proceeds gate-by-gate in topological order:

**Addition/Subtraction Gate** $z = x \pm y$. The evaluator sets its share of wire $z$ as $((x)_{\text{E}}, (\langle \text{sk} \cdot x \rangle_{\text{E}})) \pm ((y)_{\text{E}}, (\langle \text{sk} \cdot y \rangle_{\text{E}})) + \text{shift}_z$.

**Multiplication Gate** $z = x \cdot y$. The evaluator computes

$$ \begin{align*} & (\langle x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{E}}, \langle \text{sk} \cdot x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{E}}) \\ & \quad \leftarrow \text{ExtEval}(0, \{k_{\text{DDlogRS}}, M_{\text{E}}\}, M_{\text{E}}^{x}, l^{k_{\text{PRF}}}, \text{PRF}_{\lambda}^{1}(\cdot, \text{id}_y)) \\ & (\langle y \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{E}}, \langle \text{sk} \cdot y \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{E}}) \\ & \quad \leftarrow \text{ExtEval}(0, \{k_{\text{DDlogRS}}, M_{\text{E}}\}, M_{\text{E}}^{y}, l^{k_{\text{PRF}}}, \text{PRF}_{\lambda}^{1}(\cdot, \text{id}_x)) \\ & (\langle y \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{E}}, \langle \text{sk} \cdot y \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{E}}) \\ & \quad \leftarrow \text{ExtEval}(0, \{k_{\text{DDlogRS}}, M_{\text{E}}\}, M_{\text{E}}^{y}, l^{k_{\text{PRF}}}, \text{PRF}_{\lambda}^{2}(\cdot, \text{id}_x)) \end{align*} $$

and sets its shares to be

$$ \begin{align*} \langle z \rangle_{\text{E}} &:= \langle x \rangle_{\text{E}} \cdot \langle y \rangle_{\text{E}} + \langle x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{E}} \\ & \quad + \langle y \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{E}} + \text{shift}_z^1 \\ \langle \text{sk} \cdot z \rangle_{\text{E}} &:= \langle \text{sk} \cdot x \rangle_{\text{E}} \cdot \langle y \rangle_{\text{E}} + \langle \text{sk} \cdot x \cdot \text{PRF}_{\lambda}^{1}(k_{\text{PRF}}, \text{id}_y) \rangle_{\text{E}} \\ & \quad + \langle y \cdot \text{PRF}_{\lambda}^{2}(k_{\text{PRF}}, \text{id}_x) \rangle_{\text{E}} + \text{shift}_z^2 \end{align*} $$

3. The evaluator outputs $\{\langle \text{out}_i \rangle_{\text{E}} - \langle \text{out}_i \rangle_{\text{G}}\}_{i \in m}$.
### Protocol 2: Small Integer Garbling Scheme from Paillier-ElGamal.

**Theorem 37 (Small Integer Garbling from the Circular-Security of Paillier-ElGamal with Small Exponent).** Let $\lambda$ be a security parameter and $\ell(\lambda)$ be the bitlength of a corresponding RSA modulus. We consider a circuit C consisting of n input wires and m output wires. Assume the ({\times}, l_K), {$F_{\text{prf-mask,C}}$}C\in C)-circular security of the (Paillier-ElGamal with Small Exponent, Pseudorandom Mask)-Hybrid (Definition 33, Remark 34) and the existence of a pseudorandom function in NC¹. Then for every integer $k > 1$, the construction AGC<sub>PaillierEG</sub> (Protocol 2) is an arithmetic garbling scheme for B-bounded integer computation where B is any integer less than $2^{(k-1)\lambda}$. Moreover, the garbled circuit has bit-size

$$6\ell(\lambda) + (n + |C| + 1)(2k + 2)\lambda + (km + 1)\lambda$$

where the size of each input label is $k\lambda$ bits.

*Proof.* We show correctness and Privacy.

**Correctness.** We will show that for any wire w carrying the secret x, the following invariant holds: $\langle w \rangle_E - \langle w \rangle_G = (x, sk \cdot x)$.

- **Input Labels:** For the input labels, the invariant holds by Step 4 of the scheme.

- **Addition/Subtraction Gates:** Consider the output wires of addition/subtraction gates and assume WLOG that the gate is an addition gate. The garbler sets its share to be $PRF_{\lambda}(k_{\text{PRF}}, \text{id}_z)$. Assuming that the invariant holds for input gates, the evaluator calculates its share as $(\langle x \rangle_E, \langle (sk \cdot x) \rangle_E) + (\langle y \rangle_E, \langle (sk \cdot y) \rangle_E) + \text{shift}_z = (\langle x \rangle_E, \langle (sk \cdot x) \rangle_E) + (\langle y \rangle_E, \langle (sk \cdot y) \rangle_E) - (\langle x \rangle_G, \langle (sk \cdot x) \rangle_G) - (\langle y \rangle_G, \langle (sk \cdot y) \rangle_G) - PRF_{\lambda}(k_{\text{PRF}}, \text{id}_z) = (x + y, sk \cdot (x + y)) - PRF_{\lambda}(k_{\text{PRF}}, \text{id}_z)$, which maintains the invariant.

- **Multiplication Gates:** Consider the output wire of a multiplication gate. We use here the correctness of the ExtEval algorithm. First, note that we require the PRF to be in NC¹ since ExtEval requires the program P to be defined as a polynomial-size RMS program; this class encapsulates NC¹ circuits. As stated in Lemma 27, the outputs of ExtEval in Step 5 of the protocol form subtractive shares over [N]. Along with the correctness of Lemma 31, these are shares over $2^{k\lambda}$ and $2^{(k+2)\lambda}$ with all but negligible probability. Hence, note that

$$ \begin{aligned} \Pr[\langle z \rangle_E - \langle z \rangle_G \neq z] &\leq \Pr[\langle x \cdot \text{PRF}_{\lambda}^1(k_{\text{PRF}}, \text{id}_y) \rangle_E - \langle x \cdot \text{PRF}_{\lambda}^1(k_{\text{PRF}}, \text{id}_y) \rangle_G \neq x \cdot \text{PRF}_{\lambda}^1(k_{\text{PRF}}, \text{id}_y)] \\ &\quad + \Pr[\langle y \cdot \text{PRF}_{\lambda}^1(k_{\text{PRF}}, \text{id}_x) \rangle_E - \langle y \cdot \text{PRF}_{\lambda}^1(k_{\text{PRF}}, \text{id}_x) \rangle_G \neq y \cdot \text{PRF}_{\lambda}^1(k_{\text{PRF}}, \text{id}_x)] \\ &\leq 2\text{negl}(\lambda) \\ &= \text{negl}(\lambda) \end{aligned} $$

Thus, the output wire satisfies the above invariant with all but negligible probability. Note that the depth of the circuit is polynomially bounded, and hence the label values of each output wire go through at most polynomially many iterations of ExtEval. It follows that that each such wire then maintains the above invariant with all but negligible probability.

- **Output Wires:** From the previous discussion, the above invariant is also maintained for each output wire of the circuit. Hence, the output wires reconstruct, and the scheme is correct.

**Privacy.** We describe our simulator in Algorithm 4. We will argue indistinguishability via a series of hybrids.

**Algorithm** Small Integer Garbling from Paillier-ElGamal with Small Exponent: $\text{Sim}(1^{\lambda}, C, z)$

**Parameters.** Let $\lambda$ be a security parameter and $k > 1$ be a global parameter. We consider a circuit C of size at most poly($\lambda$) with n inputs, m outputs and $s_\times$ multiplication gates; we represent the ith output wire by out_i. Let PaillierEG = (PaillierEG.Gen, PaillierEG.Enc, PaillierEG.Dec) be the Paillier-ElGamal cryptosystem with short exponent defined in Figure 2.

$\text{Sim}(1^{\lambda}, C, z)$:

1. The simulator samples $k_{\text{DDlogRS}} \stackrel{\$}{\leftarrow} \{0, 1\}^{\lambda}$ and $(N, g, pk, sk) \stackrel{\$}{\leftarrow}$ PaillierEG.Gen(1$^{\lambda}$).
2. The simulator sets $l^{k_{\text{PRF}}} \leftarrow (\text{PaillierEG.Enc}(\text{pk}, 0), \text{PaillierEG.Enc}(\text{pk}, 0))$ and adds it to $\hat{C}$.

3. The simulator chooses a subtractive sharing of 1 and adds one share $M_E := (\langle 1 \rangle_E, \langle \text{sk} \rangle_E)$ to $\hat{C}$.

4. The simulator chooses $L_x^i \stackrel{\$}{\leftarrow} \{0, 1\}^{(2k+2)\lambda}$.

5. For output wire $i$ of any gate, the simulator chooses $\text{shift}_i \stackrel{\$}{\leftarrow} \{0, 1\}^{(2k+2)\lambda}$.

6. The simulator runs $\text{AGCPaillierEG.Eval}$ to find the outputs $\{\langle \text{out}_i \rangle_E\}_{i \in N}$ and chooses $\langle \text{out}_i \rangle_G := \langle \text{out}_i \rangle_E - z_i$. Then it outputs $((L_x^i)_{i \in [n]}, \hat{C} = (N, g, k_{\text{DDlogRS}}, l^{k_{\text{PRF}}}, M_E, (\text{shift}_i)_{i \in C}, \{\langle \text{out}_i \rangle_G\}_{i \in m}))$.

**Algorithm 4: Simulator for Small Integer Garbling Scheme from Paillier-ElGamal.**

- **Hybrid 0:** The real-world protocol.

- **Hybrid 1:** The garbler runs Step 6 of the simulator instead of the garbling scheme. The only difference between this hybrid and the previous one is how the simulator programs its output shares. The garbler's output shares, however, are statistically hidden by the correctness of the protocol; thus the hybrids are statistically indistinguishable.

- **Hybrid 2:** In this hybrid, the garbler replaces $l^{k_{\text{PRF}}}$ with encryptions of 0 instead of $k$ and $\text{sk} \cdot x$, and replaces the shifts $\text{shift}_z$ with PRF outputs $\text{PRF}_{\lambda}(k_{\text{PRF}}, \text{id}_z)$. The indistinguishability of this hybrid from the previous one follows via a direct application of the circular security of the (Paillier-ElGamal, Pseudorandom Mask)-Hybrid parametrized with Remark 34.

Suppose that there is a PPT distinguisher $\text{Dist}(1^{\lambda})$ that can distinguish between Hybrid 1 and Hybrid 2 with greater than negligible probability. We will show an adversary $\mathcal{A}$ that, given access to this distinguisher and the oracles $\mathcal{O}_{F,k,\text{sk},b}$ and $\mathcal{O}_{F',k,\text{sk},b}$, can break the circular security of the (Paillier-ElGamal, Pseudorandom Mask)-Hybrid. The adversary $\mathcal{A}(1^{\lambda}, N, g)$ works as follows. It runs $\text{AGCPaillierEG.Garble}(1^{\lambda}, C)$ for some $B$-bounded circuit $C$, with the following changes:

• In step 1, it does not sample $k_{\text{PRF}}$ or PaillierEG.Gen(1$^{\lambda}$).

• In step 2, it makes the oracle queries $\mathcal{O}_{F,k,\text{sk},b}(l_{\mathcal{K}})$ and $\mathcal{O}_{F,k,\text{sk},b}(\times)$ where $l_{\mathcal{K}}$ and $\times$ are the functions as defined in Remark 34.

• In step 4, the adversary sets its share by querying $\mathcal{O}_{F',k,\text{sk},b}(F_{\text{prf-mask},C}(\cdot, \cdot, \text{id}_{\text{in}_i}))$ for each input wire $\text{in}_i$.

• In step 5, the adversary sets $\text{shift}_z \leftarrow \mathcal{O}_{F',k,\text{sk},b}(F_{\text{prf-mask},C}(\cdot, \cdot, \text{id}_z))$.

Note that since the pseudorandom mask is a one-time encryption scheme, the adversary is only allowed to make a single call to the oracle per gate. Nevertheless, the adversary sends the output $((L_x^i)_{i \in [n]}, \hat{C} = (N, g, k_{\text{DDlogRS}}, l^{k_{\text{PRF}}}, M_E, (\text{shift}_i)_{i \in C}, \{\langle \text{out}_i \rangle_G\}_{i \in m}))$ to $\text{Dist}$. If $b=0$, then the above procedure corresponds to Hybrid 1, while if $b=1$ then the above procedure corresponds to Hybrid 2. The adversary outputs whatever $\text{Dist}$ outputs, however since $\text{Dist}$ is able to distinguish between the two hybrids with more than negligible probability, the adversary can differentiate between $b=0$ and $b=1$ with more than negligible probability as well, breaking the $(\{\times, l_{\mathcal{K}}\}, \{F_{\text{prf-mask},C}\}_{C \in C_{\lambda}})$-circular security of the (Paillier-ElGamal, Pseudorandom Mask)-Hybrid.

- **Hybrid 3:** In this hybrid, the garbler replaces both the labels $L_i$ and the shifts $\text{shift}_z$ with truly random values. Note that there is no information about $k_{\text{PRF}}$ remaining in the view. The indistinguishability of this hybrid follows from the security of the PRF. Our reduction works briefly as follows: assume that there is a distinguisher $\text{Dist}(1^{\lambda})$ which can distinguish between Hybrids 2 and 3 with noticeable probability. Then consider a PPT adversary $\mathcal{A}^{\mathcal{O}(\cdot)}$, where $\mathcal{O}(\cdot)$ either $\text{PRF}(k_{\text{PRF}}, \cdot)$ or $\text{R}(\cdot)$ where $\text{R}$ is a truly random function. $\mathcal{A}$ can run the algorithm of Hybrid 2, making calls to either $\text{PRF}_{\lambda}(k_{\text{PRF}}, \text{id}_z)$ or $\text{R}(\text{id}_z)$ as given. It sends the output of the garbled circuit to $\text{Dist}$, then outputs as the distinguisher does accordingly. Since only a polynomial number of calls to the oracle have been made, the adversary then can output whether $\mathcal{O}(\cdot)$ is the PRF or a truly random function with noticeable probability, breaking the underlying security of the PRF.

- **Hybrid 4:** The simulator's algorithm of Algorithm 4. The hybrids are identical.

With this we complete the proof of privacy.

**Size.** Finally, we compute the size of the garbling output. Note that $N$ is of size $\ell(\lambda)$, $g$ is an element of $N$ and is hence also of size $\ell(\lambda)$. $k_{\text{DDlogRS}}$ is of length $\lambda$ and $M_1$, being a share, is of length $(2k+2)\lambda$,
which is also the length of each one of the shifts (there are $n + |C|$) of them. Furthermore, $|k_{PRF}|$ is two ciphertexts and is hence of size $4\ell(\lambda)$, and the output wires are of length $k\lambda$ each. Together, this adds up to

$$6\ell(\lambda) + (n + |C| + 1)(2k + 2)\lambda + (km + 1)\lambda.$$

It is easy to see that the rate of the scheme goes rapidly to $1/2$ as $k \to \infty$.

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