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.

## No comments:

## Post a Comment