2
$\begingroup$

I'm learning about garbled circuits, and I'm using the following tutorial: Yao's Protocol.

I have a questions regarding to construction (encryption) of truth table in garbled circuits.

Slide 14 says:

For each wire x, y, z, specify two random values, corresponding to 0 and 1.

So I picked:

(k_x0, k_x1) = 1, 0
(k_y0, k_y1) = 0, 1
(k_z0, k_z1) = 1, 0

Then,

We need to “associate” (k_z0, k_z1) with (k_x0, k_x1, k_y0, k_y1).

Here's my table according to the values in slide 16.

x | y | z | GCT
----------------
1 | 0 | 1 |  ?
1 | 1 | 1 |  ?
0 | 0 | 1 |  ?
0 | 1 | 0 |  ?

However, I can't figure out what should GCT values be? How should those values be calculated?

| improve this question | |
$\endgroup$
  • $\begingroup$ Your table is empty but, int the slides, it is full $\endgroup$ – kelalaka Oct 7 '18 at 14:50
0
$\begingroup$

The slides you are looking date from 2014, but some optimizations have been realized since ! By the fact that all fonctions can be written as a combination of AND and XOR gates, you just need to be able to encrypt AND and XOR gates. Obviously, both can be done with double encryption but look at those two optimizations : FreeXOR and HalfGates. A list of all optimizations can be found here

On the page 13 of the HalfGates optimization, you have the algorithm using both (FreeXOR and HalfGates) of this optimizations.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Yao, encodes AND curcuit as;

  • the $x$ values as $k_x^0,k_x^1$,
  • the $y$ values as $k_y^0,k_y^1$,
  • the $z$ values as $z_k^0,z_k^1$.

Here the upper script represents 0 or 1.

\begin{array}{|c|} \hline GCT \\\hline E_{k_x^0}(E_{k_y^0}(k_z^0)) & \\\hline E_{k_x^0}(E_{k_y^1}(k_z^0)) & \\\hline E_{k_x^1}(E_{k_y^0}(k_z^0)) & \\\hline E_{k_x^1}(E_{k_y^1}(k_z^1)) & \\\hline \end{array}

Where $E$ is Symmetric Encryption Scheme, and in these schemes Block Ciphers can be utilized. One can use Asymmetric Encryption schemes but that will be slow, and non-standard.

so, given to keys, only one of the rows can be decrypted correctly.

| improve this answer | |
$\endgroup$
  • $\begingroup$ my question was how to calculate values in GCT column, i.e. what is E? i found this question crypto.stackexchange.com/questions/48081/…, the answer says that E is some symmetric encryption scheme, so can that scheme be an algorithm that computes the values of GCT columns by ANDing, ORing etc. the k_z0, k_y0, k_x0? $\endgroup$ – bb8 Oct 7 '18 at 16:06
  • $\begingroup$ your document already says that "use $k_i^j$'s as encryption keys. You can construct any truth table. $\endgroup$ – kelalaka Oct 7 '18 at 16:19
  • $\begingroup$ i mean how is the encryption algorithm chosen? $\endgroup$ – bb8 Oct 7 '18 at 16:33
  • $\begingroup$ see the update. $\endgroup$ – kelalaka Oct 7 '18 at 16:42
  • 2
    $\begingroup$ Simply letting $E_k(m)$ be a block cipher won't work if there are many gates in the circuit (see Tate-Xu 2003). You either need to incorporate a unique identifier of each gate, for example $F_{k_x}(id) \oplus F_{k_y}(id) \oplus k_z$. And then if you're really using standard Yao (evaluator does trial decryption) instead of point-permute then you have to add extra redundancy to the ciphertexts so you can tell when you've got the right ciphertext. $\endgroup$ – Mikero Oct 7 '18 at 21:45

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.