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. Andrew Yao of Stanford University first proposed the protocol in 1986 to solve his famous Millionaires' Problem. The protocol is also known as Yao's protocol, Yao's garbled circuit protocol or simply the GC protocol in the cryptography literature. In the garbled circuit protocol, the function has to be described as a Boolean circuit.
Contents
Yao's Millionaires' Problem
The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.
This problem is analogous to a more general problem where there are two numbers
Many solutions have been introduced for the problem.
Here we study the one presented by Yao himself using the garbled circuit protocol.
Oblivious Transfer
In the garbled circuit protocol, we make use of oblivious transfer. In the oblivious transfer, a string is transferred between a sender and a receiver in the following way: a sender has two strings
- the receiver doesn't get any information about
S ( 1 − i ) - the value of
i is not exposed to the sender.
The oblivious transfer can be built using asymmetric cryptography like the RSA cryptosystem.
Definitions and Notations
Operator
Garbled Circuit Protocol
The protocol consists of 6 steps as follows:
- The underlying function (e.g., in the millionaires' problem, comparison function) is described as a Boolean circuit with 2-input gates. The circuit is known to both parties. This step can be done beforehand by a third-party.
- Alice garbles (encrypts) the circuit. We call Alice the garbler.
- Alice sends the garbled circuit to Bob along with her encrypted input.
- Bob through oblivious transfer receives his encrypted inputs from Alice.
- Bob evaluates (decrypts) the circuit and obtains the encrypted outputs. We call Bob the evaluator.
- Alice and Bob communicate to learn the output.
Circuit Generation
The Boolean circuit for small functions can be generated by hand. It is conventional to make the circuit out of 2-input XOR and AND gates. It is important that the generated circuit has the minimum number of AND gates (see Free XOR optimization). There are methods that generates the optimized circuit in term of number of AND gates using logic synthesis technique. The circuit for the Millionaires' Problem is a digital comparator circuit (which is a chain of full adder work as a subtractor and outputs the carry flag). The circuit of full adder can be implemented using only one AND gates and some XOR gates. This means the total number of AND gates for the circuit of the Millionaires' Problem is equal to the bit-width of inputs.
Garbling
Alice (garbler) encrypts the Boolean circuit in this step to obtain a garbled circuit. 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.) Next, She goes to all the gates in the circuit and replace 0 and 1 in the truth tables with the corresponding labels. The table below shows the truth table for an AND gate with two inputs:
Alice replaced 0 and 1 with the corresponding labels:
She then encrypts the output entry of the truth table with the corresponding two input labels. The encrypted table is called garbled table. This is done such that one can decrypt the garbled table only if he has the correct two input labels. In the table below,
After this, Alice randomly permute the table such that no one can learn the output value based on row. The protocol's name, garbled is derived from this random permutation.
Data Transfer
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
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
Evaluation
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:
Revealing Output
After the evaluation, Bob obtains the output label,
Point-and-Permute
In this optimization, Alice generates a random bit,
Row Reduction
This optimization reduces the size of garbled tables from 4 rows to 3 rows. Here, instead of generating a label for the output wire of a gate randomly, Alice generates it using a function of the input labels. She generates the output labels such that the first entry of the garbled table becomes all 0 and no longer needs to be sent:
Free XOR
In this optimization, Alice generates a global random (k-1)-bit value
Implication
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.
Fixed-Key Blockcipher
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
Half And
This optimization reduce the size of garbled table for AND gates from 3 row in Row Reduction to 2 rows. It is shown that this is the theoretical minimum for the number of rows in the garbled table