How to Garble Arithmetic Circuits
Speaker: Yuval Ishai , Technion
Date: April 1 2011
Time: 10:30AM to 12:00PM
Location: 32-G449
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
> 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
See other events that are part of CIS Seminars 2010/2011
See other events happening in April 2011
