How to Garble Arithmetic Circuits
Authors:
- Benny ApplebaumBABenny Applebaum
- Yuval IshaiYIYuval Ishai
- Eyal KushilevitzEKEyal Kushilevitz
- 1 October 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 120-129
Abstract
Yao's garbled circuit construction transforms a boolean circuit C : {0, 1} n → {0, 1} m into a "garbled circuit" Ĉ along with n pairs of k-bit keys, one for each input bit, such that Ĉ 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 : ℤ n → ℤ m over integers from a bounded (but possibly exponential) range into a garbled circuit Ĉ along with n affine functions L i : ℤ → ℤ k such that Ĉ 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.Keywords
This publication has 29 references indexed in Scilit:
- Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits2011
- Worry-free encryption2010
- The Learning with Errors Problem (Invited Survey)2010
- Public-key cryptosystems from the worst-case shortest vector problem2009
- Fully homomorphic encryption using ideal lattices2009
- Delegating computation2008
- On lattices, learning with errors, random linear codes, and cryptography2005
- Public-Key Cryptosystems Based on Composite Degree Residuosity Classes1999
- How to play ANY mental game1987
- Completeness classes in algebra1979