Why is garbled circuit a randomized encoding?

Question

In Garbled Circuit, a circuit C is encoded to C' and input x is encoded to x' such that only C(x) can be computed given C' and x'.

Randomized encoding of a function f is another randomized function f' such that output distribution of f' encodes f.

I heard that garbled circuit is a randomized encoding but couldn't figure out how. Can anyone please explain it?

Answer 1

First of all, having a precise definition of garbled circuit is a bit cumbersome - if you want to see a clear and nice (formal) definition, I suggest looking at page 2 of this article.

The purpose of a randomized encoding is to create, from a function $f$ and an input $x$, an encoding $\phantom{i}\hat{f}(x;r)$ such that:

• Correctness: there is an algorithm $D$ such that, for any input $x$ and any random coin $r$, $D(\hat{f}(x;r)) = f(x)$

• Security: $\phantom{i}\hat{f}(x;r)$ reveals nothing about $x$ except $f(x)$. Formally, there is a simulator that, given only $f(x)$, can sample from a distribution indistinguishable from $$\{\phantom{i}\hat{f}(x;r) | r \text{ random}\}$$

The level of indistinguishability (perfect, statistical, or computational) gives the corresponding flavor of the randomized encoding.

For a randomized encoding to be be useful, computing $\phantom{i}\hat{f}(x;r)$ must be simpler than directly computing $f(x)$ for a definition of "simpler" that depends on the application in mind. An example: suppose you want someone to learn $xy$ and nothing more, but you cannot directly compute $xy$ because all you know are, say, additively homomorphic encryptions of $x$ and $y$ - so you can compute any function of the form $ax+by+c$, but not $xy$. Here, you can pick two random coins $(r_x,r_y)$ and send (encryptions of) $(u,v,w) = (x+r_x,y+r_y, xr_y+yr_x+r_xr_y)$: your opponent (who has the secret key of the scheme) can compute $xy = uv-w$, and one can easily prove that he can only learn $xy$.

So, why are garbled circuits randomized encodings? Well, given a function $f$ represented by a circuit $C$, the randomized encoding of $C(x)$ is just Garble$(x;r) = (C',K)$ ($K$ is the list of keys for every input bit, $r$ is a random coin) together with Encode$(K,x) = E$: given $(E,C')$, one can recover $C(x)$ by evaluating the garbling $C'$ with the keys $E$ associated to $x$ (this is the correctness of the encoding), and it reveals nothing more than $C(x)$ (this is the security of the randomized encoding). Therefore, this does indeed correspond to a computational randomized encoding of a function.

But why is it useful? Because with known constructions of garbled circuits, computing $(C',E)$ is simpler than computing $C(x)$ in the following sense:

• Garble$(C;r)$ can be computed by a constant depth circuit, independently of the depth of the function computed by $C$. Indeed, one can garble all the gates in parallel. This has many applications in cryptography and led to a fruitful line of work that started with the article Cryptography in $NC_0$.
• Garbling the circuit and encoding the input are two separated algorithm, and Encode$(x,K)$ is usually a very simple algorithm (a table lookup).