*on Financial Cryptography*, volume 2357 of *Lecture Notes in Computer Science*, pages 120–135, Southampton, Bermuda, March 11–14, 2003.

[GKWY20] Chun Guo, Jonathan Katz, Xiao Wang, and Yu Yu. Efficient and secure multiparty computation from fixed-key block ciphers. In *2020 IEEE Symposium on Security and Privacy*, pages 825–841, San Francisco, CA, USA, May 18–21, 2020. IEEE Computer Society Press.

[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.

[HIMV19] Carmit Hazay, Yuval Ishai, Antonio Marcedone, and Muthuramakrishnan Venkitasubramaniam. LevioSA: Lightweight secure arithmetic computation. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, *ACM CCS 2019: 26th Conference on Computer and Communications Security*, pages 327–344, London, UK, November 11–15, 2019. ACM Press.

[HLL23] Yao-Ching Hsieh, Huijia Lin, and Ji Luo. Attribute-based encryption for circuits of unbounded depth from lattices. In *64th Annual Symposium on Foundations of Computer Science*, pages 415–434. IEEE Computer Society Press, October 2023.

[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.

[IKSS22] Yuval Ishai, Dakshita Khurana, Amit Sahai, and Akshayaram Srinivasan. Round-optimal black-box protocol compilers. In Orr Dunkelman and Stefan Dziembowski, editors, *Advances in Cryptology – EUROCRYPT 2022, Part I*, volume 13275 of *Lecture Notes in Computer Science*, pages 210–240, Trondheim, Norway, May 30 – June 3, 2022.

[KMR14] Vladimir Kolesnikov, Payman Mohassel, and Mike Rosulek. FleXOR: Flexible garbling for XOR gates that beats free-XOR. In Juan A. Garay and Rosario Gennaro, editors, *Advances in Cryptology – CRYPTO 2014, Part II*, volume 8617 of *Lecture Notes in Computer Science*, pages 440–457, Santa Barbara, CA, USA, August 17–21, 2014.

[KS08] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, *ICALP 2008: 35th International Colloquium on Automata, Languages and Programming, Part II*, volume 5126 of *Lecture Notes in Computer Science*, pages 486–498, Reykjavik, Iceland, July 7–11, 2008. Springer, Heidelberg, Germany.

[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.

[LWYY24] Hanlin Liu, Xiao Wang, Kang Yang, and Yu Yu. Garbled circuits with 1 bit per gate. Cryptology ePrint Archive, Report 2024/712, 2024.

[MORS24] Pierre Meyer, Claudio Orlandi, Lawrence Roy, and Peter Scholl. Rate-1 arithmetic garbling from homomorphic secret sharing. *Lecture Notes in Computer Science*, pages 71–97, November 2024.
[PS21] Antigoni Polychroniadou and Yifan Song. Constant-overhead unconditionally secure multi-party computation over binary fields. 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 812–841, Zagreb, Croatia, October 17–21, 2021.

[PSSW09] Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure two-party computation is practical. In Mitsuru Matsui, editor, *Advances in Cryptology – ASIACRYPT 2009*, volume 5912 of *Lecture Notes in Computer Science*, pages 250–267, Tokyo, Japan, December 6–10, 2009.

[PW09] Rafael Pass and Hoeteck Wee. Black-box constructions of two-party protocols from one-way functions. In Omer Reingold, editor, *TCC 2009: 6th Theory of Cryptography Conference*, volume 5444 of *Lecture Notes in Computer Science*, pages 403–418, March 15–17, 2009.

[QWW18] Willy Quach, Hoeteck Wee, and Daniel Wichs. Laconic function evaluation and applications. In Mikkel Thorup, editor, *59th Annual Symposium on Foundations of Computer Science*, pages 859–870, Paris, France, October 7–9, 2018. IEEE Computer Society Press.

[RR21] Mike Rosulek and Lawrence Roy. Three halves make a whole? Beating the half-gates lower bound for garbled circuits. In Tal Malkin and Chris Peikert, editors, *Advances in Cryptology – CRYPTO 2021, Part I*, volume 12825 of *Lecture Notes in Computer Science*, pages 94–124, Virtual Event, August 16–20, 2021.

[Sho97] Victor Shoup. Lower bounds for discrete logarithms and related problems. In Walter Fumy, editor, *Advances in Cryptology – EUROCRYPT’97*, volume 1233 of *Lecture Notes in Computer Science*, pages 256–266, Konstanz, Germany, May 11–15, 1997.

[SS24] Sacha Servan-Schreiber. Constrained pseudorandom functions for inner-product predicates from weaker assumptions. *Cryptology ePrint Archive*, Report 2024/058, 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.
# A Security Proofs for the Building Blocks

## A.1 Proof of Lemma 8

*Proof.* We first consider the case of constant polynomials, that is, when $m = 0$, and then generalize to an arbitrary $m \in \mathbb{N}$. It is easy to see that the support of $\text{Pert}_c(a)$ and $\text{RandSum}_{0,c}$ is contained in $[c]$ and consequently, the support of $\mathcal{D}_{0,c}^{(a)}$ and $\mathcal{D}_{0,c}$ is contained in $[2c]$. Moreover, the output of $\text{RandSum}_{0,c}$ is the binomial distribution Binomial(c, 1/2). Next, observe that the output of $\text{Pert}_c(a)$ is distributed identically to that of $\text{RandSum}_{0,c}$ conditioned on the latter outputting a value congruent to $a \bmod 2$ i.e., for any $u \in [c]$,

$$ \mathrm{Pr}_{a' \leftarrow \mathrm{Pert}_c(a)}[a' = u] = \mathrm{Pr}_{a' \leftarrow \mathrm{RandSum}_{0,c}}[a' = u \mid a' \equiv a \bmod 2]. $$

Therefore, for any $u \in [2c]$, we have

$$ \begin{aligned} & \left| \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}^{(a)}}[a' + r = u] - \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}}[a' + r = u] \right| \\ &= \left| \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}}[a' + r = u \mid a' \equiv a \bmod 2] - \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}}[a' + r = u] \right| \tag{1} \\ &= \frac{1}{2} \left| \mathrm{Pr}[a' + r = u \mid a' \equiv a \bmod 2] - \mathrm{Pr}[a' + r = u \mid a' \not\equiv a \bmod 2] \right| \end{aligned} $$

where the second equality follows from the fact that $\mathrm{Pr}[a' \equiv a \bmod 2] = 1/2$ when $a' \leftarrow \mathrm{RandSum}_{0,c}$. When $u$ is odd, we have

$$ \begin{aligned} & \mathrm{Pr}[a' + r = u \mid a' \equiv a \bmod 2] - \mathrm{Pr}[a' + r = u \mid a' \not\equiv a \bmod 2] \\ &= \sum_{\substack{v \in [u] \\ v \equiv a \bmod 2}} \frac{1}{2^{2c}} \cdot \binom{c}{v} \cdot \binom{c}{u-v} - \sum_{\substack{v \in [u] \\ v \not\equiv a \bmod 2}} \frac{1}{2^{2c}} \cdot \binom{c}{v} \cdot \binom{c}{u-v} \\ &= 0, \end{aligned} $$

where the first equality follows from the fact that $a'$ and $r$ are distributed as Binomial(c, 1/2) and the second equality follows from recognizing that the summation is the co-efficient of $X^u$ in $(1-X)^c \cdot (1+X)^c = (1-X^2)^c$.

Similarly, when $u$ is even, we have

$$ \left| \mathrm{Pr}[a' + r = u \mid a' \equiv a \bmod 2] - \mathrm{Pr}[a' + r = u \mid a' \not\equiv a \bmod 2] \right| = \frac{1}{2^{2c}} \cdot \binom{c}{u/2}. $$

In summary, Equation (1) simplifies to

$$ \left| \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}^{(a)}}[a' + r = u] - \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}}[a' + r = u] \right| = \begin{cases} 0 & \text{if } u \text{ is odd,} \\ \frac{1}{2^{2c}} \cdot \binom{c}{u/2} & \text{otherwise.} \end{cases} $$

Consequently,

$$ \begin{aligned} \mathrm{SD}(\mathcal{D}_{0,c}^{(a)}, \mathcal{D}_{0,c}) &= \frac{1}{2} \cdot \sum_{u=0}^{2c} \left| \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}^{(a)}}[a' + r = u] - \mathrm{Pr}_{a'+r \sim \mathcal{D}_{0,c}}[a' + r = u] \right| \\ &= \frac{1}{2} \sum_{u=0}^{c} \frac{1}{2^{2c}} \cdot \binom{c}{u/2} \\ &= \frac{1}{2^{c+1}} \end{aligned} $$
To conclude the proof, observe that for all $m \in \mathbb{N}$, every coefficient in the output of $\mathcal{D}_{m,c}^{(a)}$ and $\mathcal{D}_{m,c}$ is independently and identically distributed to $\mathcal{D}_{0,c}^{(a)}$ and $\mathcal{D}_{0,c}$ respectively. It follows that

$$ \mathrm{SD} \left( \mathcal{D}_{m,c}^{(a)}, \mathcal{D}_{m,c} \right) = 1 - \left( 1 - \frac{1}{2^{c+1}} \right)^m \le \frac{m}{2^c}. $$

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

## A.2 Proof of Lemma 9

*Proof.* Intuitively, the proof follows from the fact that when $N > T \cdot c \cdot m$, the sum used to compute $\tilde{v}$ does not produce any carries when viewed as a base-$N$ integer.

More formally, let $u = \sum_{i=1}^{T} a_i \cdot b_i'$ where the sum is computed by interpreting each $a_i$ and $b_i'$ as elements of $\mathbb{N}[X]$. Observe that for every $i \in [2m]$, the co-efficient $u[i]$ of $X^i$ in $u$, is of the form

$$ u[i] = \sum_{\ell=1}^{T} \sum_{j=\max(0, i-m)}^{\min(i, m)} a_{\ell}[j] \cdot b'_{\ell}[i-j], $$

where $a_{\ell}[j]$ and $b'_{\ell}[i-j]$ denote the co-efficients of $X^j$ and $X^{i-j}$ in $a_{\ell}$ and $b'_{\ell}$ respectively. Since each $a_{\ell}[j]$ and $b'_{\ell}[i-j]$ are non-negative integers such that $a_{\ell}[j] \le 1$ and $b'_{\ell}[i-j] \le c$, it follows that $u[i]$ is a non-negative integer with $u[i] \le T \cdot c \cdot m < N$. In particular, this means that $(u[i])_{i \in [2m]}$ represents the unique $N$-ary decomposition of $u(N)$. It then immediately follows that $v = \mathrm{toPoly}_N(\mathrm{Mod}_N(\tilde{v}, 2))$ since, by definition, $u \equiv v \bmod 2$ and $u(N) = \tilde{v}$. ■

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