Paper 2012/255

How to Garble Arithmetic Circuits

Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz

Abstract

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1{\}}^n\to \{0,1{\}}^m$ into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C:{\mathbb{Z}}^n\to {\mathbb{Z}}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $$ along with $$ affine functions $$ such that $$ together with the $$ integer vectors $$ reveal $$ and no additional information about $$. The security of our construction relies on the intractability of the learning with errors (LWE) problem.