Garbled 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.
[2] The first written document about this technique was by Goldreich, Micali, and Wigderson in STOC'87.
[3] The term "garbled circuit" was first used by Beaver, Micali, and Rogaway in STOC'90.
In the garbled circuit protocol, we make use of oblivious transfer.
with the oblivious transfer protocol such that Note that while the receiver doesn't know the
The oblivious transfer can be built using asymmetric cryptography like the RSA cryptosystem.
The protocol consists of 6 steps as follows: The Boolean circuit for small functions can be generated by hand.
It is important that the generated circuit has the minimum number of AND gates (see Free XOR optimization).
There are methods that generate the optimized circuit in term of number of AND gates using logic synthesis technique.
This means the total number of AND gates for the circuit of the Millionaires' Problem is equal to the bit-width of the inputs.
Alice assigns two randomly generated strings called labels to each wire in the circuit: one for Boolean semantic 0 and one for 1.
(The label is k-bit long where k the security parameter and is usually set to 128.)
is the secret key and X is the value to be encrypted (see Fixed-Key Blockcipher).
After this, Alice randomly permutes the table such that the output value cannot be determined from the row.
Alice sends the computed garbled tables for all gates in the circuit to Bob.
He receives his labels through oblivious transfers for each bit of his input.
After the data transfer, Bob has the garbled tables and the input labels.
He is able to open one row for each table and retrieve the corresponding output label:
She then, instead of randomly permuting, sorts the garbled table according to the inputs select bits.
This way, Bob does not need to test all four rows of the table to find the correct one, since he receives the pointer bits with each wire label and can find the correct row and decrypt it with one attempt.
It also does not reveal anything about the output value because the select bits are randomly generated.
She generates the output labels such that the first entry of the garbled table becomes all 0 and no longer needs to be sent:[7]
In this optimization, Alice generates a global random (k-1)-bit value
The proof of security in the Random Oracle Model for this optimization is given in the Free-XOR paper.
[8] Free XOR optimization implies an important point that the amount of data transfer (communication) and number of encryption and decryption (computation) of the garbled circuit protocol relies only on the number of AND gates in the Boolean circuit not the XOR gates.
Thus, between two Boolean circuits representing the same function, the one with the smaller number of AND gates is preferred.
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
is a unique-per-gate number (e.g., gate identifier) called tweak.
[12] Another approach is using several GC for a circuit and verifying the correctness of a subset of them and then using the rest for the computation with the hope that if the garbler was malicious, it would be detected during the verification phase.
