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 $\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)
PDF
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/255,
      author = {Benny Applebaum and Yuval Ishai and Eyal Kushilevitz},
      title = {How to Garble Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2012/255},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/255}},
      url = {https://eprint.iacr.org/2012/255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.