How to Garble Arithmetic Circuits

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.

Authors

• Benny Applebaum
• Yuval Ishai
• Eyal Kushilevitz

Keywords

• Encoding
• Wires
• Encryption
• Vectors
• Polynomials
• Arithmetic Circuits
• Public Key
• Affine Function
• Original Construct
• Multi-party Computation
• Input Bits
• Positive Integer
• Functional Identification
• Constant Factor
• Transformation Efficiency
• Random Matrix
• Output Format
• Complex Communication
• Final Construct
• Main Constructs
• Efficient Type
• Random Input
• Key Size
• Security Parameter
• Arithmetic Calculation
• One-way Function
• Random Bits
• Ring Elements
• Circuit Size
• Classical Circuit
• Decoding
• Privacy
• Cryptography
• Garbled Circuit
• Randomizing Polynomials