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.
Category / Keywords: foundations / secure computation, randomized rencoding Publication Info: An extended abstract of this work appears in FOCS 2011. Date: received 5 May 2012, last revised 4 Jul 2013 Contact author: benny applebaum at gmail com Available format(s): PDF | BibTeX Citation Version: 20130704:065254 (All versions of this report) Short URL: ia.cr/2012/255 Discussion forum: Show discussion | Start new discussion