ECCC-Report TR12-058https://eccc.weizmann.ac.il/report/2012/058Comments and Revisions published for TR12-058en-usThu, 04 Jul 2013 08:59:15 +0300
Revision 1
| How to Garble Arithmetic Circuits |
Benny Applebaum,
Yuval Ishai,
Eyal Kushilevitz
https://eccc.weizmann.ac.il/report/2012/058#revision1Yao'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.Thu, 04 Jul 2013 08:59:15 +0300https://eccc.weizmann.ac.il/report/2012/058#revision1
Paper TR12-058
| How to Garble Arithmetic Circuits |
Benny Applebaum,
Yuval Ishai,
Eyal Kushilevitz
https://eccc.weizmann.ac.il/report/2012/058Yao'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.Mon, 07 May 2012 18:03:47 +0300https://eccc.weizmann.ac.il/report/2012/058