Garbled Circuits

The first talk on Wednesday was given by Phillip Rogaway on Garbled Circuits. GC find  motivation in the Two Millionaire Problem, and it is generalized to the case of (secure) evaluation of any given boolean circuit between two players. GC have been around on the literature for long time, since Yao in 1986 published his six-pages paper. Surprisingly, the protocol is not described in this paper but is based in Yao's oral presentations of his work. Foundations were not worked out back then: GC have been seen as a tool or technique instead of an object of study itself. In the talk, Rogaway first gave a brief overview of several proposed constructions along the last twenty years. The first instantiations grabbed some information within the circuit's gates and made use of the XOR operation to go through the garbled gates and eventually compute an encoding of the circuit's output. The legitimate user can then resolve the real output value from this encoding. The problem with this approach is that for certain configurations of the circuit (concretely, when several garbled gates share a common input wire) hidden values on the garbled gate can be recovered (see this paper).
The first attempt to establish its security appears in 2009 by Lindell and Pinkas. It is based in the latest protocol described in the paper How to play a mental game. This protocol uses double encryptions to garble the gates. The symmetric encryption used in the garbling has the followings three properties: 1) IND-CPA secure, 2) It has elusive range. That is, the range of the encryption function under two different keys (gate's input wires values) are likely to be disjoint with high probability. 3) Efficient verification range (to efficiently move along the garbled gates).

On the other hand, many implementations have been proposed, (e.g. Kolesnikov, Schneider 2008, Pinkas Schneider Smart Williams, 2009) but none of them are within Lindell-Pinkas paradigm, since they use hash functions and therefore belongs to the ROM world.

The goal that Rogaway wanted to achieve was to define a Garbling scheme in a way that it is suitable for most applications, and it is representation-independent (boolean or arithmetic circuits, lookup tables etc). Here is how it goes this formalization: we have a function f and want to securely evaluate it.  We split f into a triple (e,F,d), where e (d) is an encoding (decoding) of the input (output) and F is the garbled circuit f. We see f as a string. Then, a Garbled scheme consists of a 5-tuple G=(Gb,En,De,Ev,ev). Gb generates (e,F,d) and Ev evaluates F on the encoded input X given by En, and outputs Y , from which y=f(x) is derived using De. It can be the case that G leaks information from f. He defined a function L, which on input f measures the leakage of the scheme (sometimes f itself is known, others only its topology or structure). L is suppose to be poly-time computable. Using this notion he defines several properties (better said, formalizes concepts used in the literature). For example, input privacy holds if from (F,X,d) we learn nothing but L(f). Similarly, obliviousness holds if we learn nothing but L(f) from (F,d).

He also talked about game-based security. He gave two different notions: indistinguishability, and simulation. In the IND game an attacker A has access to a garbling oracle which on queries (f,x,f',x') of A, returns an random garbled instance (F,X,d) either of (f,x) or of (f',x'). The goal of the attacker is to guess the right function/input. Here we must assume that L(f)=L(f'). The simulation scenario is similar. Just note that the simulator make up his instance (F,X,d) using only L(f). He noticed that SIM implies IND, but the converse is only true when (L,ev) is efficiently invertible (that is, given the pair (s=L(f*),y=ev(f*,ev*)), find (f,x) such that s=L(f) and y=ev(f,x)).

Last, he stressed that Garbling schemes meet applications on the Verifiable Computation area (introduced by Gennaro Gentry and Parno in 2010), since a garbled circuit can be seen as a one-time verifiable scheme.