Garbled circuit

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

History

The history of garbled circuits is complicated. The invention of garbled circuit was credited to Andrew Yao, as Yao introduced the idea in the oral presentation of a paper in FOCS'86. This was documented by Oded Goldreich in 2003.

The first written document about this technique was by Goldreich, Micali, and Wigderson in STOC'87. The term "garbled circuit" was first used by Beaver, Micali, and Rogaway in STOC'90. Yao's protocol solving Yao's Millionaires' Problem was the beginning example of secure computation, yet it is not directly related to garbled circuits.

Note that while the receiver doesn't know the S_{0}, S_{1} values, in practice the receiver knows some information about what S_{b} encodes so that the receiver is not blindly choosing b . That is, if S_{0} encodes a false value, S_{1} encodes a true value and the receiver wants to get the encoded true value, the receiver chooses b=1 . The oblivious transfer can be built using asymmetric cryptography like the RSA cryptosystem.

Alice sends the computed garbled tables for all gates in the circuit to Bob. Bob needs input labels to open the garbled tables. Thus, Alice chooses the labels corresponding to her input a and sends them to Bob.

For example, if Alice's input is \mathbf{a} = a_4a_3a_2a_1a_0 = 01101 , then she sends X_0^{a_4} , X_1^{a_3} , X_1^{a_2} , X_0^{a_1} , and X_1^{a_0} to Bob. Bob will not learn anything about Alice's input, \mathbf{a} , since the labels are randomly generated by Alice and they look like random strings to Bob. Bob needs the labels corresponding to his input as well.

He receives his labels through oblivious transfers for each bit of his input. For example, if Bob's input is \mathbf{b} = b_4b_3b_2b_1b_0 = 10100 , Bob first asks for b_0=0 between Alice's labels X_0^{b_0} and X_1^{b_0} . Through a 1-out-of-2 oblivious transfer, he receives X_0^{b_0} and so on.

After the oblivious transfers, Alice will not learn anything about Bob's input and Bob will not learn anything about the other labels. After the data transfer, Bob has the garbled tables and the input labels. He goes through all gates one by one and tries to decrypt the rows in their garbled tables.

He is able to open one row for each table and retrieve the corresponding output label: X^c = Dec_{X^a, X^b}(garbled\_table[i]) , where 0\le i \le 3 . He continues the evaluation until he reaches to the output labels. &Enc_{X_0^a, X_0^b}(X_0^c) = 0 \\ &X_0^c = Dec_{X_0^a, X_0^b}(0). \end{align} In this optimization, Alice generates a global random (k-1)-bit value R which is kept secret.

During the garbling of the input gates w^a and w^b , she only generates the labels (X_0^a,X_0^b) and computes the other labels as X_1^a = X_0^a \oplus (R \parallel 1) and X_1^b = X_0^b \oplus (R \parallel 1) . Using these values, the label of an XOR gate's output wire w^c with input wires w^a , w^b is set to X^c = X^a \oplus X^b . The proof of security in the Random Oracle Model for this optimization is given in the Free-XOR paper.

This method allows to efficiently garble and evaluate AND gates using fixed-key AES, instead of costly cryptographic hash function like SHA-2. In this garbling scheme which is compatible with the Free XOR and Row Reduction techniques, the output key X^c is encrypted with the input token X^a and X^b using the encryption function Enc(X^a, X^b, T, X^c) = \pi(K) \oplus K \oplus X^c , where K = 2X^a \oplus 4X^b \oplus T , \pi is a fixed-key block cipher (e.g., instantiated with AES), and T is a unique-per-gate number (e.g., gate identifier) called tweak.

See also

Cryptography RSA Secure multi-party computation Yao's Millionaires' Problem

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378944480 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.