2
$\begingroup$

In Garbled Circuits party $P_1$ garbles the original truth table by arbitrary choosing or by some other method values. Table (b) represents the garbled values corresponding to each entry in the original truth table.

My question is: What does the last column in garbled table represents? In the original table we have three columns but in garbled table we have a fourth column of the form $H(k^{a}_{0}\left | \right | k^{b}_{1}\left | \right | g_{1})\oplus k^{a\vee b}_{2}$.

Note: There is a mismatch between the notation in the circuit diagram and the table in the figures below. Subscribt and superscript has been switched.

Garbled Circuit

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The first three columns in Table (b) are the random keys that $P_1$ has chosen to associate with the bit values on the two input wires and the output wire, respectively. The fourth column is the actual garbled gate information. I.e., the garbled values that $P_1$ sends to $P_2$, and $P_2$ uses to evaluate the garbled gate. Note, that if $P_2$ is given keys $k^a_0$ and $k^b_1$ he can use the garbled column to compute $k^{a \vee b}_2$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doesn't $P_2$ need to have also $k_2^*$ values to compute the garbled circuits? ( In the table $k_2^*$ is also taking part in the computation..) $\endgroup$
    – user1387682
    Apr 29, 2017 at 19:37
  • 1
    $\begingroup$ @user1387682 No, $P_2$ does not compute the garbled circuit himself. It is computed by $P_1$ and sent to $P_2$. As described in the answer $P_2$ can then use keys coresponding to inputs to the gate to compute a key corresponding to the output. I.e., some key $k^{a \vee b}_2$ $\endgroup$
    – Guut Boy
    Apr 29, 2017 at 20:04
0
$\begingroup$

The fourth column is garbled gate values that $P_1$ sends to $P_2$ and is calculated by taking $Hash$ of keys that $P_1$ assigned to inputs $w_0$ and $w_1$

Improve this answer
$\endgroup$

Your Answer

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

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