# Half Gate

The Half-Gate optimization further reduces the number of ciphertexts from to . This is also the protocol used in zkOracles, and more details of this algorithm will be given in this subsection. The algorithm is presented in the ZRE15 paper.

We first describe the basic idea behind half-gate garbling. Let’s say we want to compute the gate . With the Free-XOR optimization, let and denote the input wire labels to this gate, and denote the output wire labels, with each encoding .

Half-gate garbling contains two case: when the garbler knows one of the inputs, and when the evaluator knows one of the inputs.

Garbler half-gate. Considering the case of an gate , where are intermediate wires in the circuit and the garbler somehow knows in advance what the value will be.

When , the garbler will garble a unary gate that always outputs . The label table is as follows.

Then the garbler generates two ciphertexts:

When , the garbler will garble a unary identity gate. The label table is as follows.

Then the garbler generates two ciphertexts:

Since is known to the garbler, the two cases shown above could be unified as follows:

These two ciphertexts are then suitably permuted according to the color bits of . The evaluator takes a hash of its wire label for and decrypts the appropriate ciphertext. If , he/she obtains output wire label in both values of . If the evaluator obtains either or , depending on the bit . Intuitively, the evaluator will never know both and , hence the other ciphertext appears completely random.

By applying the row-reduction optimization, we reduce the number of ciphertexts from to as follows.

Evaluator half-gate. Considering the case of an gate , where are intermediate wires in the circuit and the evaluator somehow knows the value at the time of evaluation. The evaluator can behave differently based on the value of .

When , the evaluator should always obtain output wire label , then the garbled circuit should contains the ciphertext:

When , it is enough for the evaluator to obtain . He/she can then with the other wire label (either or ) to obtain either or . Hence the garbler should provide the ciphertext:

Combining the above two case together, the garbler should provide two ciphertexts:

Note that these two ciphertext do NOT have to be permuted according to the color bit of , because the evaluator already knows . If , the evaluator uses the wire label to decrypt the first ciphertext. If , the evaluator uses the wire label to decrypt the second ciphertext and s the result with the wire label for .

By applying the row-reduction optimization, we reduce the number of ciphertexts from to as follows.

Two halves make a whole. Considering the case to garble an gate , where both inputs are secret. Consider:

Suppose the garbler chooses uniformly random bit . In this case, the first gate can be garbled with a garbler-half-gate. If we further arrange for the evaluator to learn the value , then the second gate can be garbled with an evaluator-half-gate. Leaking this extra bit to the evaluator is safe, as it carries no information about the sensitive value . The remaining gate is free and the total cost is ciphertexts.

Actually the evaluator could learn without any overhead. The garbler choose the color bit of the 0 label on wire . Since that color bit is chosen uniformly, it is secure to use it. Then when a particular value is on that wire, the evaluator will hold a wire label whose color bit is .

Let be the labels for , let . is the color bit of the wire, is a secret known only to the garbler. When the evaluator holds a wire label for whose color bit is , the label is , corresponding to truth value .