Paper 2012/255
How to Garble Arithmetic Circuits
Benny Applebaum and 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 $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors (LWE) problem.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Published elsewhere. An extended abstract of this work appears in FOCS 2011.
- Keywords
- secure computationrandomized rencoding
- Contact author(s)
- benny applebaum @ gmail com
- History
- 2013-07-04: revised
- 2012-05-09: received
- See all versions
- Short URL
- https://ia.cr/2012/255
- License
-
CC BY