Abstract:
Yao's garbled circuit construction transforms a boolean circuit C : {0,1}^n --> {0,1}^m into a "garbled circuit" C' along with n pairs of k-bit keys, one for each input bit, such that 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 present the first arithmetic analogue of Yao's construction. Our construction transforms an arithmetic circuit C : Z^n --> Z^m over integers from a bounded (but possibly exponential) range into a garbled circuit C' along with n affine functions L_i : Z --> Z^k such that 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 decisional variant of the learning with errors (LWE) problem.
Joint work with Benny Applebaum and Eyal Kushilevitz