In a garbled gate, the garbler encrypts four entries: one for each combination of input labels. The evaluator has one label per input wire and can decrypt exactly one entry. Why can't the evaluator try all four entries to learn extra information?
Think about your answer, then reveal below.
Model answer: Each entry is encrypted under the corresponding pair of input labels using a symmetric cipher (keyed hash or AES). The evaluator knows only one label per wire, giving them exactly one valid decryption key pair. The other three entries decrypt to random-looking garbage because the evaluator doesn't have the correct key pairs. With point-and-permute optimization, each label includes a signal bit that directly identifies which entry to decrypt, so the evaluator doesn't even attempt the others.
The encryption ensures that each combination of input labels acts as a unique key. Without both correct labels, decryption produces meaningless output. This is the core mechanism that hides intermediate wire values — the evaluator computes the correct function but never learns whether any intermediate wire carried 0 or 1.
Question 2 Multiple Choice
The 'free XOR' optimization allows XOR gates to be evaluated without any ciphertext or communication. How does this work?
AXOR gates are removed from the circuit during preprocessing
BThe garbler chooses a global random offset R. For every wire, the two labels differ by XOR with R (label_1 = label_0 XOR R). XOR gate output labels are computed as the XOR of input labels: if label_a and label_b are inputs, the output label is label_a XOR label_b, which automatically encodes the XOR of the underlying bits due to the algebraic relationship with R
CXOR gates use a special hash function that requires no encryption
DThe evaluator already knows XOR results from the input labels without computation
The free XOR technique (Kolesnikov-Schneider 2008) is one of the most important garbled circuit optimizations. By maintaining the invariant that labels for 0 and 1 on every wire differ by the same global R, XOR gates require zero ciphertexts and zero communication — just a local XOR of labels. Since many circuits are rich in XOR gates (especially those designed with this optimization in mind), this dramatically reduces both communication and computation.
Question 3 True / False
A garbled circuit can only be evaluated once. If the evaluator could evaluate it on two different inputs, they could learn the garbler's input.
TTrue
FFalse
Answer: True
Each garbled gate entry is encrypted under specific input labels. If the evaluator learns labels for both 0 and 1 on any wire (by evaluating with different inputs), they can decrypt multiple entries per gate, eventually reconstructing the full truth table and recovering the garbler's input. This one-time-use property means each computation requires a fresh garbled circuit. This is a significant practical constraint, driving research into reusable garbled circuits and alternative MPC approaches for repeated computations.
Question 4 Multiple Choice
Half-gates (Zahur-Rosulek-Evans 2015) reduce the cost of a garbled AND gate from 3 ciphertexts to 2. What is the conceptual idea?
AHalf-gates split the circuit in half, garbling each half independently
BAn AND gate is decomposed into two 'half-gates': one where the garbler knows one input bit, and one where the evaluator knows one input bit. Each half-gate requires only one ciphertext (using the free XOR technique internally), totaling 2 ciphertexts per AND gate
CHalf-gates use elliptic curve operations to compress the gate representation
DThe optimization skips half the AND gates by approximating the circuit
Half-gates exploit the observation that AND(a,b) can be decomposed based on which party knows which input. The garbler-half-gate handles the case where the garbler knows bit a (from their input), requiring 1 ciphertext. The evaluator-half-gate handles the case where the evaluator knows bit b (from their input), requiring 1 ciphertext. The final output combines both half-gates using free XOR. This is provably optimal: 2 ciphertexts per AND gate is the minimum for garbled circuits under standard techniques.
Question 5 True / False
Garbled circuits achieve security against semi-honest adversaries directly. Achieving security against malicious adversaries requires additional techniques.
TTrue
FFalse
Answer: True
In the semi-honest model, both parties follow the protocol but try to learn extra information from the transcript. Yao's basic protocol is secure here. Against malicious adversaries (who may deviate arbitrarily), additional protections are needed: the garbler might construct an incorrect circuit, and the evaluator might use OT maliciously. Techniques include cut-and-choose (the garbler sends multiple garbled circuits and the evaluator randomly checks some, evaluating the rest), authenticated garbling, and dual execution. These add overhead but are necessary for strong security guarantees.