International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 09 May 2012

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.