Paper 2023/501
New Ways to Garble Arithmetic Circuits
Abstract
The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting $C$ into a Boolean circuit and applying Yao's garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not "arithmetic". In this work, we present new ways to garble arithmetic circuits, which improve the stateoftheart on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bitlength of the garbled circuit $\widehat C$ and that of the computation tableau $C\ell$ in the clear, where $\ell$ is the bit length of wire values (e.g., Yao's garbled circuit has rate $O(\lambda)$). $\bullet$ We present the first constantrate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz. $\bullet$ We construct an arithmetic garbling scheme for modular computation over $\mathcal{R} = \mathbb{Z}_p$ for any integer modulus $p$, based on either DCR or LWE. The DCRbased instantiation achieves rate $O(\lambda)$ for large $p$. Furthermore, our construction is modular and makes blackbox use of the underlying ring and a simple key extension gadget. $\bullet$ We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part. To the best of our knowledge, constantrate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2023
 Keywords
 garbled circuitssecure computationarithmetic circuits
 Contact author(s)

marshall @ cs nyu edu
hanjul @ cs washington edu
rachel @ cs washington edu
trl @ pku edu cn  History
 20230407: approved
 20230406: received
 See all versions
 Short URL
 https://ia.cr/2023/501
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/501, author = {Marshall Ball and Hanjun Li and Huijia Lin and Tianren Liu}, title = {New Ways to Garble Arithmetic Circuits}, howpublished = {Cryptology ePrint Archive, Paper 2023/501}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/501}}, url = {https://eprint.iacr.org/2023/501} }