2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.