36
$\begingroup$

There are plenty of questions here about the details and how-to's of "garbled circuits", but I have not seen anything that defines what garbled circuits are.

What exactly is a garbled circuit? What are they intended to be used for? What are their limitations?

The tag for garbled circuits just says that they are used in secure multiparty computation. However, this answer states that they're only appropriate for two-party computation?

This question seeks the definition of a "circuit". What is the difference between a circuit and a garbled circuit?

$\endgroup$
2
  • $\begingroup$ You wil find a good exposition of Yao's garbled circuits protocol for secure two-party computations in this book. It's expensive, but your local university library may have it. $\endgroup$
    – fkraiem
    Commented Jul 27, 2016 at 19:35
  • $\begingroup$ I suggest this video, and slides $\endgroup$
    – mikeazo
    Commented Jul 27, 2016 at 19:43

1 Answer 1

40
$\begingroup$

A circuit is just a way to represent a computation. There is nothing specifically cryptographic about a circuit. It just means a straight-line computation (no looping or flow-control constructs) consisting of just operations on bits, like AND, OR, NOT.

A garbled circuit is a way to "encrypt a computation" that reveals only the output of the computation, but reveals nothing about the inputs or any intermediate values. We use the term "circuit" because garbled circuits work by taking the computation you care about, expressed as a circuit, and then doing some cryptographic stuff for each operation (AND, OR, NOT) in the circuit.

If we want to be a little more precise, a "garbling scheme" consists of:

  • (Garble) A way to convert a (plain) circuit $C$ into a garbled circuit $\widehat C$.

  • (Encode) A way to convert any (plain) input $x$ for the circuit into a garbled input $\widehat x$. You need the secret randomness that was used to garble the circuit to encode $x$ into $\widehat x$.

  • (Evaluate) A way to take a garbled circuit $\widehat C$ and garbled input $\widehat x$ and compute the circuit output $C(x)$. Anyone can do this, you don't have to know $x$ or the secret randomness inside $\widehat C$ to evaluate and learn $C(x)$.

I'm simplifying a little bit here. But the main idea of security is that $\widehat C$ and $\widehat x$ together leak no more information than $C(x)$. In particular, they reveal nothing about $x$, yet they allow the computation $C(x)$ to be done (obliviously). This is what I mean by "encrypting a computation".

The main application for garbled circuits is secure two-party computation. Imagine that Alice has private input $x$ and Bob has private input $y$. They agree on some function $f$ and agree that they both want to learn $f(x,y)$, but don't want their opponent to learn anything more than $f(x,y)$. To achieve this, they can do the following (this is Yao's classical protocol):

  1. The parties agree on a way to express $f$ as a (plain) circuit. Alice garbles the circuit $f \mapsto \widehat f$. She sends $\widehat f$ to Bob as well as her own "garbled input" $\widehat x$.

  2. Alice knows how to encode any input for $f$ into a "garbled" input, but only Bob knows his private input $y$. So the parties arrange for Bob to pick up a garbled version $\widehat y$ without Alice learning what $y$ was. This can be done with a primitive called oblivious transfer.

  3. Now Bob has the garbled circuit $\widehat f$, and a garbled input $\widehat x, \widehat y$ for that circuit. He can then run the evaluation procedure and learn $f(x,y)$. He can reveal $f(x,y)$ to Alice.

We can argue that the protocol reveals no more than $f(x,y)$ in the following way:

  • Alice doesn't see anything other than the final answer $f(x,y)$ in this protocol (the security of oblivious transfer ensures that she learns nothing in step 2).

  • Even though Bob sees $\widehat f$, $\widehat x$ and $\widehat y$, the security of garbled circuits ensures that these values don't reveal anything beyond $f(x,y)$.

This approach works when Alice & Bob are semi-honest (i.e., they follow the protocol as instructed). But when Alice is malicious she can garble some other function $f'$ instead of the $f$ that they agreed upon. So other things need to be added to the protocol to prevent this from happening, when we want security against malicious adversaries.

Reference material:

$\endgroup$
3
  • 1
    $\begingroup$ How does Bob garble y without knowing the secret randomness that Alice chose when she came up with the garbling scheme? $\endgroup$
    – Jason C
    Commented Jul 28, 2016 at 2:27
  • 7
    $\begingroup$ The garbled encoding works bit-by-bit. Take Bob's first bit. Alice can think to herself: "if Bob has input bit 0 then his garbled encoding should be $G_0$. If he has input bit 1 then his garbled encoding should be $G_1$." Oblivious transfer is a primitive where Alice provides two strings $G_0, G_1$ as input. Bob provides a bit $b$ as input and learns $G_b$ (but not the other one $G_{1-b}$). Alice doesn't learn $b$. The parties can perform an oblivious transfer for each bit of Bob's input. As for how oblivious transfer really works, that is another question ;) $\endgroup$
    – Mikero
    Commented Jul 28, 2016 at 2:47
  • $\begingroup$ Beside Yao's garbled circuit can't be reused. Can you please resolve my confustion that "Is it allow to assign different keys each time when garbled circuit is executed or keys are fixed for input bit 0 and 1" $\endgroup$
    – Infinity
    Commented Feb 4, 2017 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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