4
$\begingroup$

I have been recently working on garbled circuits for a course and I think I don't have the the proper background for understanding them. I don't know how to approach such problems.

Here is an example of what I'm looking for. Other examples include the function for maximum of two entries each having 2 bits, the function that checks if the two entries have equal Hamming weights, etc.

How does one go about solving the question that I linked?

$\endgroup$
14
$\begingroup$

In order to answer this, you need to be sure to understand how garbled circuits actually work. I'll try to explain this from top to bottom:

The protocol

Let Alice and Bob be willing to compute securely a function $f(x,y)$ (in your example, it would be $f(x,y)=\min(x,y)$) while keeping their respective inputs $x$ and $y$ secret.

In order to do so, they will first model the function $f$ as a Boolean circuit, which is possible since there exists a Boolean circuit $C$ that calculates the output of $f$ for any function $f$ with fixed size inputs [1]. However, the way such a modeling is performed can depend on the function and will not be further discussed here.

Then Alice will garble the Boolean circuit: for each wire $W_i$ of the circuit $C$, she randomly chooses two secret values $w^0_i, w^1_i$, where $w^j_i$ is the garbled value of the value $j\in \{0,1\}$ of the wire $W_i$. Note that $w_i^j$ cannot reveal $j$ in itself, so Alice has to keep track of $i$ and $j$. This has to be done for each and every input and output wires of every logical gates in the circuit, excepted for the circuit output gates which can be left ungarbled.

Then Alice also has to construct a garbled truth table (GTT) $T_i$ for each of the gates $G_i$ in $C$. Those tables have to be so that given garbled values along its set of input wires, $T_i$ will allow to recover the garbled output of this $G_i$ and no other information. This is achieved through encryption of the output values. I will detail further the garbling of gates below.

A logical AND gate, its labels and its truth table

Afterwards, Alice can translate each bit of her input into its corresponding garbled values on the circuit's input wires. And then she can send the—now garbled—circuit where each gate is replaced by its GTT to Bob with her encrypted input.

After Bob received the garbled circuit, since all input wires are encrypted and only Alice knows the mapping of the encrypted values and the real bits, Bob need to perform an oblivious transfer (I let you google that one, since it's not useful to answer your question) with Alice for each of his input bits, so that Alice can inform him of what encrypted values correspond to his inputs bits with knowing what are his actual input bits.

So it means that for each input wire, Bob will choose one amongst the two random strings $w_i^0, w_i^1$ which correspond respectively to $0$ and $1$, but without knowing the content of the string he does not choose. And thanks to the properties of the oblivious transfer Alice cannot learn Bob's input.

Then Bob has all the needed values to compute the output of the circuit as I will discuss it below. Once he has done so, he can tell the output values to Alice. So Bob was able to obtain the output of $f$ without revealing his input, nor knowing Alice's input, this means that Alice and Bob successfully simulated a trusted third party and performed thus secure MPC!

Garbling Logical Gates

The notion of garbling logical gates and their truth table is crucial. Without loss of generality, I will only consider logical gates with two input wires and one output wire. As I quickly explained above, for a given gate $G\in C$ and its input wires $W_0,W_1$ and its output wire $W$, Alice had to choose six different random strings, $w_0^0, w_0^1,w_1^0,w_1^1,w^0,w^1$ she assigned to each values of the wires in a one-to-one mapping, where $w_i^j$ represents the random string assigned to the value $j$ of the wire $W_i$.

Then in order to garble the truth table of $G$ in a way which would not reveal any information given two input values $w_0,w_1$ excepted for its output value $w$, not even the type of the gate, Alice can encrypt the output values $w^0,w^1$ using the garbled input values as keys, using a given symmetric encryption scheme $\mathbb{E}$. I use the notation $\mathbb{E}_{k_0,k_1}(x)=\mathbb{E}_{k_0}(\mathbb{E}_{k_1}(x))$ to denote encrypting twice with two given keys $k_0,k_1$. As an example, let us encrypt the truth table of the AND gate from Figure 1: $$\begin{array}{c|c|c||c} W_0 & W_1 & W & \text{Garbled value} \\ \hline w_0^0 & w_1^0 & w^0 & \mathbb{E}_{w_0^0,w_1^0}(w^0) \\ w_0^0 & w_1^1 & w^0 & \mathbb{E}_{w_0^0,w_1^1}(w^0) \\ w_0^1 & w_1^0 & w^0 & \mathbb{E}_{w_0^1,w_1^0}(w^0)\\ w_0^1 & w_1^1 & w^1 & \mathbb{E}_{w_0^1,w_1^1}(w^1) \\ \end{array}$$

The GTT $T$ of the gate $G$ is then simply the set $\left\lbrace\mathbb{E}_{w_0^j,w_1^k}(w^{G(j,k)}) \mid j,k \in \left\lbrace0,1\right\rbrace \right\rbrace$ of the garbled values, where $G(j,k)$ corresponds to the output of the gate $G$ under inputs $(j,k)$.

Evaluation of a garbled circuit

Once Bob has received the garbled circuit $C$ from Alice and obtained the garbled values of his input through multiple oblivious transfers, he can evaluate the circuit.

It is important to realize that a garbled circuit differs from a regular Boolean circuit. In a Boolean circuit, semantic and syntax are basically the same: we are assigning to each wire two possible semantic values, namely True or False, which we will syntactically denote as a signal with 1 or 0 values respectively.

Those signals were public and the same signals were associated with every wire and anybody could tell from the signal what semantic value it held. This changes in a garbled circuit, since the semantic values of each signal—excepted for the circuit's output ones—are now secret and the signals are now varying from one wire to another wire.

Thus, in order to evaluate the circuit, for each gates $G_i$ of the circuit, Bob can try and decrypt the values in the associated truth table $T_i$ using the gate's input values as keys. One of the entries in $T_i$ will then decrypt into the output of the gate. Hence it seems necessary to have an oracle to confirm successful decryption of the entries of $T_i$, however a trick I'll detail right now called permute-and-point first used in [2] and then clearly explained in Phillip Rogoway's dissertation [3], allows to decide which entry of the GTT is to be decrypted given the garbled inputs, enabling faster computations and still preventing the evaluator to deduce anything from the order of the truth table's entries.

Permute-and-point

This trick works as follows: for each input and output wires $W_i$, Alice will concatenate a random bit $a\in \{0,1\}$ at the end of its garbled value $w_i^0$ and concatenate its inverse $b=\overline{a}=1-a$ at the end of $w_i^1$. So it allows to associate each of the 4 permutations of 2 bits to one of the entry of the GTT, without having any correlation between the bits and the values of the ungarbled truth table. So Alice can simply order the GTT according to the natural ordering and give it to Bob which will then be able to deduce which entry he should decrypt on a given input. To obtain a nice representation of this trick, those bits can be seen as a pair of colors, as I depict them in Figure 2, in which we see how the truth table is modified to take into account this method.

The permute-and-point trick

Those modifications allow Bob to simply decrypt the entry whose index corresponds with the colors associated to its input wires and thus to obtain the output wire's value and its color, allowing him to further evaluate the circuit.


Example evaluation

A circuit made of one AND gate and one OR gate and one XOR gate with their respective GTT and their labeled wires randomly colored. The bold values are the values used to compute the example below.

Let us see how one could evaluate the garbled circuit represented in Figure 3 using the permute-and-point method we discussed above. Let us assume that the semantic input values of $(W_1,W_2,W_3,W_4)$ are $(0,0,1,0)$, which means that the actual garbled input is $({\color{green}\bullet}{}w_1^0,{\color{red}\bullet}{}w_2^0,{\color{red}\bullet}{}w_3^1,{\color{green}\bullet}{}w_4^0)$ where the $w_j^i$ are the random values that Alice chose when she garbled the circuit, as seen above. Let us also assume that Alice already provided her garbled input, say $(W_1,W_3)$, and that Bob already obtained his garbled input $(W_2,W_4)$ from Alice through two applications of oblivious transfer as described in the protocol part.

So Bob will begin by evaluating first the AND gate using the input $({\color{green}\bullet}{}w_1^0,{\color{red}\bullet}{}w_2^0)$, since it has the colors $ \color{green}\bullet\color{red}\bullet$ he will try and decrypt the third entry of the GGT of the AND gate, which works and thus provide him with the garbled value ${\color{green}\bullet}{}w_5^0$.

Then he can continue his evaluation with the second gate, which is the OR gate. He looks at its input $({\color{red}\bullet}{}w_3^1,{\color{green}\bullet}{}w_4^0)$ and try to decrypt the entry corresponding to $ \color{red}\bullet\color{green}\bullet$ with the keys $(w_3^1,w_4^0)$, it decrypt into the garbled value ${\color{green}\bullet}{}w_6^1$.

He can now decrypt the final XOR gate using the computed input $({\color{green}\bullet}{}w_5^0,{\color{green}\bullet}{}w_6^1)$, thus decrypting the $\color{green}\bullet\color{green}\bullet$ entry which provide him with the final result: "1".

And Bob does not know what was Alice's input, he just knows the final output "1" and the randomly generated strings $w_1^0,w_2^0,w_3^1,w_4^0,w_5^0,w_6^1$. He can still for example deduce from the circuit that the semantic values of $w_5^0$ and $w_6^1$ are opposed, however it does not allow him to reverse the garbled circuit up to Alice's input values. There are circuits where no privacy is assured, like for example a circuit computing the sum of the inputs, however in this example case, Bob—knowing his semantic input values—can simply restrict Alice's inputs to a subset of the possible inputs but cannot uniquely determine the actual Alice's input values.


Now, answering your question

  1. You must model the function as a boolean circuit using fairly basic gates.
  2. You must garble that boolean circuit.
  3. You can then do the drawings.

Now, in the linked question the trickiest part is to "show that the simulated circuits are indistinguishable from the actual one", but since it is a really small circuit you can simply show it behaves correctly on all inputs. If you want to do it more formally, you can see the proof the the Yao protocol by Lindell & Pinkas, more specifically their claim 6.

Hopefully this should address all the problems you may have with garbled circuits... (Except if you want to dig into how to get better performance, since there are many more tricks to speed things up.)


Modeling the min function

The fastest way to model a boolean function is to draw its truth table, so in your case, you have 4 bits inputs, with the numbers $a$ and $b$ being 2-bits numbers $a_1a_2$ and $b_1b_2$ respectively, and you want as output the minimum $c$ of $a$ and $b$, where $c$ is constituted of two bits: $c_1c_2$.

So you can draw the truth table:

$$\begin{array}{c|c||c|c||c|c} a_1 & a_2 & b_1 & b_2 & c_1 & c_2 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array}$$ And you can model your boolean circuit by taking the true values in the results and represent them as being a boolean expression:

For $c_1$: $$ \begin{array}{c|c||c|c||c|c} a_1 & a_2 & b_1 & b_2 & c_1 & {bool. expr.} \\ \hline 1 & 0 & 1 & 0 & 1 & a_1 \land \overline{a_2}\land b_1 \land \overline{b_2} \\ 1 & 0 & 1 & 1 & 1 & a_1 \land \overline{a_2}\land b_1 \land {b_2} \\ 1 & 1 & 1 & 0 & 1 & a_1 \land {a_2}\land b_1 \land \overline{b_2} \\ 1 & 1 & 1 & 1 & 1 & a_1 \land {a_2}\land b_1 \land {b_2} \\ \end{array} $$ And for $c_2$: $$ \begin{array}{c|c||c|c||c|c} a_1 & a_2 & b_1 & b_2 & c_2 & {bool. expr.} \\ \hline 0 & 1 & 0 & 1 & 1 & \overline{a_1} \land {a_2}\land \overline{b_1} \land {b_2}\\ 0 & 1 & 1 & 0 & 1 & \overline{a_1} \land {a_2}\land b_1 \land \overline{b_2}\\ 0 & 1 & 1 & 1 & 1 & \overline{a_1} \land {a_2}\land b_1 \land {b_2}\\ 1 & 0 & 0 & 1 & 1 & a_1 \land \overline{a_2}\land \overline{b_1} \land {b_2}\\ 1 & 1 & 0 & 1 & 1 & a_1 \land {a_2}\land \overline{b_1} \land {b_2}\\ 1 & 1 & 1 & 1 & 1 & a_1 \land {a_2}\land b_1 \land {b_2}\\ \end{array} $$

Now, you can express $c_1$ and $c_2$ as the OR of all their respective boolean expression, this method is called the boolean Sum-of-Product: $$ \begin{aligned} c_1= (a_1\land \overline{a_2}\land b_1 \land \overline{b_2}) \lor(a_1\land \overline{a_2}\land b_1 \land {b_2}) \\ \lor(a_1\land {a_2}\land b_1 \land \overline{b_2}) \lor(a_1\land {a_2}\land b_1 \land {b_2}) \end{aligned} $$

And for $c_2$: $$ \begin{aligned} c_2 = (\overline{a_1} \land {a_2}\land \overline{b_1} \land {b_2}) \lor(\overline{a_1} \land {a_2}\land b_1 \land \overline{b_2})\\ \lor(\overline{a_1} \land {a_2}\land b_1 \land {b_2}) \lor(a_1 \land \overline{a_2}\land \overline{b_1} \land {b_2})\\ \lor(a_1 \land {a_2}\land \overline{b_1} \land {b_2}) \lor(a_1 \land {a_2}\land b_1 \land {b_2})\\ \end{aligned} $$

And you have a possible circuit for your function.

Now those expression are really ugly and you may want to simplify them, it is possible to convert them into nicer forms, like DNF (this is where Karnaugh maps can help). But I won't cover this topic.

For instance, $c_1$ can be rewritten as: $c_1=a_1 \land b_1$ and $c_2$ can be rewritten as: $c_2 = (a_1 \land \overline{b_1} \land b_2) \lor (\overline{a_1} \land a_2 \land b_1) \lor (a_2 \land b_2)$

I haven't much resources to refer you to there, but a quick search led me to this page and that one, which even has a graphical representation of the circuits.


References

[1] Goldwasser, S., Micali, S., & Wigderson, A. (1987). How to play any mental game, or a completeness theorem for protocols with an honest majority. In Proc. of the Nienteenth Annual ACM STOC (Vol. 87, pp. 218-229). [PDF]

[2] Beaver, D., Micali, S., & Rogaway, P. (1990, April). The round complexity of secure protocols. In Proceedings of the twenty-second annual ACM symposium on Theory of computing (pp. 503-513). ACM. [PDF]

[3] Rogaway, P., & Micali, S. (1991). The round complexity of secure protocols (Doctoral dissertation, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science). [PDF]

$\endgroup$
  • $\begingroup$ Thanks for your response. However, I was specifically looking for the drawing of the circuit not the explanation of how the garbled circuit principle works. Do you know any references on how to construct the circuit for the function? $\endgroup$ – Spock Jun 8 '17 at 20:50
  • 1
    $\begingroup$ You can construct a boolean circuit from the truth table using k-maps, I'll expand my answer tomorrow to include this. $\endgroup$ – Lery Jun 8 '17 at 22:34
  • $\begingroup$ Constructing circuits based on what? Pseudocode? Mathematical formulas? Binary Operations (well, those are easy)? Anyway, that is very, very far out of scope of cryptography - my guess would be that's just basic computer science. $\endgroup$ – tylo Jun 9 '17 at 11:38
  • $\begingroup$ I agree with you @tylo, but nonetheless I've completed my answer. The link Spock gave was asking for a circuit for the $\min$ function for 2 2-bits numbers. I misunderstood what he actually asked at first (which is more related to the Electrical Engineering Stack Exchange, maybe), so I ended up describing the whole process. $\endgroup$ – Lery Jun 9 '17 at 11:42
  • $\begingroup$ @Lery, Thanks a lot. That's what exactly what I was looking for. $\endgroup$ – Spock Jun 9 '17 at 19:41

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.