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


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$.

  • $\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 '17 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 '17 at 20:04

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$


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.