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
0
$\begingroup$

The encryption algorithm for constructing Garbled Circuits should have indistinguishable encryption for multiple messages and elusive and efficiently verifiable range. Elusive range means that encryption with one key falls with negligible probability under the range of an encryption with another key. Efficiently verifiable range means that given a key $k$, it is possible to efficiently (polynomial time) verify if a given ciphertext is in the range of $k$.

The latter two properties are required for the correct computation of the garbled circuit. The evaluator has 2 keys for evaluating a gate and he can know the intended decryption only if encryptions in one key won't be valid encryptions under another key and if this can be verified easily. Do note that these requirements are needed only for standard Yao's protocol and are not required in case of Point and Permute.

The encryption scheme should also be secure under chosen double-encryption. We encrypt the output label with two keys and we require that it is not possible to obtain the plaintext with only one of the keys. This requirement ensures that the evaluator cannot get the labels for other gates without both the corresponding keys.

It can be shown that any scheme that is CPA-secure can be used to satisfy these security constraints.

This paper formally states the security constraints and provides a proof for Yao's garbled circuit protocol.

|improve this answer
$\endgroup$

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.