12c-yaos-garbled-circuits.ipynb

Kernel: SageMath 10.5

Notebook 12c: Yao's Garbled Circuits

Module 12: Multi-Party Computation

---

Motivating Question. Secret sharing lets multiple parties compute additions cheaply, but multiplication requires Beaver triples and communication rounds. Is there a way for two parties to compute any function with just one round of interaction? Yao's Garbled Circuits (1986) achieves this: one party "garbles" a Boolean circuit, the other evaluates it, learning only the output.

---

Prerequisites. You should be comfortable with:

• Secret sharing (Notebooks 12a-12b)

• Symmetric encryption (basic concept)

• Boolean logic gates (AND, OR, XOR)

Learning objectives. By the end of this notebook you will be able to:

1. Assign random wire labels to each wire in a Boolean circuit.

2. Garble a single gate by encrypting output labels.

3. Evaluate a garbled gate using one label per input wire.

4. Assemble a complete garbled circuit for a small function.

5. Understand the role of oblivious transfer in the protocol.

1. The Idea: Encrypt the Circuit Itself

Bridge from Notebook 12b. With secret sharing, parties interact during computation (each gate requires communication). Garbled circuits take a different approach: the garbler (Alice) encrypts the entire circuit in advance, and the evaluator (Bob) processes it in a single pass.

The protocol at a high level:

1. Alice builds a Boolean circuit for the function $f(a, b)$

2. Alice assigns random wire labels, two per wire (one for 0, one for 1)

3. Alice garbles each gate: encrypts output labels under input labels

4. Alice sends the garbled circuit + her input labels to Bob

5. Bob gets his input labels via oblivious transfer (next notebook)

6. Bob evaluates the garbled circuit, learning only the output

import hashlib
import os

def random_label():
    """Generate a random 128-bit wire label."""
    return os.urandom(16)

def label_hex(label):
    """Short hex representation of a label."""
    return label.hex()[:8] + '...'

# Each wire has two labels: one for bit 0, one for bit 1
wire_A = (random_label(), random_label())  # (label_for_0, label_for_1)
wire_B = (random_label(), random_label())
wire_C = (random_label(), random_label())  # output wire

print("=== Wire Labels ===")
print(f"Wire A: 0 → {label_hex(wire_A[0])}, 1 → {label_hex(wire_A[1])}")
print(f"Wire B: 0 → {label_hex(wire_B[0])}, 1 → {label_hex(wire_B[1])}")
print(f"Wire C: 0 → {label_hex(wire_C[0])}, 1 → {label_hex(wire_C[1])}")
print(f"\nThe evaluator sees ONE label per wire but doesn't know if it's 0 or 1.")
print(f"Labels are random, they carry no information about the bit value.")

Checkpoint 1. Wire labels are the core idea: replace each bit value (0 or 1) with a random 128-bit string. The evaluator works with labels, never knowing the actual bits. This is why the evaluation reveals nothing about the inputs.

2. Garbling a Gate

For a gate $C = \text{AND}(A, B)$, we have the truth table:

A	B	C = A AND B
0	0	0
0	1	0
1	0	0
1	1	1

For each row, we encrypt the output label using the two input labels as the key:

$$\text{garbled entry}_{a,b} = \text{Enc}(k_A^a \| k_B^b, \; k_C^{f(a,b)})$$

We shuffle the four entries so the order reveals nothing.

def encrypt_label(key_a, key_b, plaintext):
    """Encrypt a label using two input labels as key.
    
    Uses H(key_a || key_b) XOR plaintext.
    """
    h = hashlib.sha256(key_a + key_b).digest()[:16]
    return bytes(a ^^ b for a, b in zip(h, plaintext))

def decrypt_label(key_a, key_b, ciphertext):
    """Decrypt a label (same operation since XOR is its own inverse)."""
    return encrypt_label(key_a, key_b, ciphertext)

def garble_gate(wire_in1, wire_in2, wire_out, truth_table):
    """Garble a gate given wire labels and truth table.
    
    wire_in1, wire_in2, wire_out: tuples (label_0, label_1)
    truth_table: function (a, b) -> output bit
    Returns: list of 4 garbled entries (shuffled)
    """
    entries = []
    for a in [0, 1]:
        for b in [0, 1]:
            out_bit = truth_table(a, b)
            ct = encrypt_label(wire_in1[a], wire_in2[b], wire_out[out_bit])
            entries.append(ct)
    
    # Shuffle so the order doesn't reveal input/output relationships
    shuffle(entries)
    return entries

# Garble an AND gate
and_gate = lambda a, b: a & b
garbled = garble_gate(wire_A, wire_B, wire_C, and_gate)

print("=== Garbled AND Gate ===")
print(f"4 encrypted entries (shuffled):")
for i, entry in enumerate(garbled):
    print(f"  Entry {i}: {entry.hex()[:24]}...")
print(f"\nEach entry encrypts an output label under two input labels.")
print(f"The evaluator can only decrypt ONE entry (the one matching their input labels).")

3. Evaluating a Garbled Gate

The evaluator has one label per input wire. They try to decrypt each entry, exactly one will produce a valid output label.

def evaluate_gate(garbled_entries, label_in1, label_in2, valid_labels):
    """Evaluate a garbled gate.
    
    Try decrypting each entry; return the one that matches a valid output label.
    valid_labels: set of valid output labels (both 0 and 1 labels)
    """
    for entry in garbled_entries:
        candidate = decrypt_label(label_in1, label_in2, entry)
        if candidate in valid_labels:
            return candidate
    return None  # shouldn't happen if inputs are valid

# Evaluator has labels for specific input values
# Suppose A = 1, B = 1 (so AND should give 1)
a_val, b_val = 1, 1
label_a = wire_A[a_val]  # evaluator's label for A
label_b = wire_B[b_val]  # evaluator's label for B

valid_output = {wire_C[0], wire_C[1]}
output_label = evaluate_gate(garbled, label_a, label_b, valid_output)

# Determine the output bit
output_bit = 0 if output_label == wire_C[0] else 1

print(f"Input: A = {a_val}, B = {b_val}")
print(f"Expected: AND({a_val}, {b_val}) = {a_val & b_val}")
print(f"\nEvaluator's input labels:")
print(f"  A: {label_hex(label_a)}")
print(f"  B: {label_hex(label_b)}")
print(f"\nDecrypted output label: {label_hex(output_label)}")
print(f"Output bit: {output_bit}")
print(f"Correct? {output_bit == (a_val & b_val)}")

# Verify all four input combinations
print("=== Evaluating All Inputs ===")
print()
for a in [0, 1]:
    for b in [0, 1]:
        out_label = evaluate_gate(garbled, wire_A[a], wire_B[b], valid_output)
        out_bit = 0 if out_label == wire_C[0] else 1
        expected = a & b
        status = '✓' if out_bit == expected else '✗'
        print(f"  AND({a}, {b}) = {out_bit} (expected {expected}) {status}")

print(f"\nAll correct! The evaluator learns only the output, not which")
print(f"truth table row was used or which garbled entry decrypted.")

Checkpoint 2. The evaluator decrypts exactly one entry per gate. They learn the output label but cannot tell which input combination produced it (because the entries are shuffled and the labels are random).

4. A Complete Garbled Circuit

Let's garble a small circuit that computes $f(a_0, a_1, b_0, b_1) = (a_0 \text{ AND } b_0) \text{ XOR } (a_1 \text{ AND } b_1)$.

This is a 1-bit inner product: $\langle a, b \rangle = a_0 b_0 \oplus a_1 b_1$.

Circuit structure:

a0 ──┐
     AND ── w1 ──┐
b0 ──┘           XOR ── output
a1 ──┐           │
     AND ── w2 ──┘
b1 ──┘

# Wire labels for the full circuit
wires = {}
for name in ['a0', 'a1', 'b0', 'b1', 'w1', 'w2', 'out']:
    wires[name] = (random_label(), random_label())

# Garble three gates
and_tt = lambda a, b: a & b
xor_tt = lambda a, b: a ^^ b

g1 = garble_gate(wires['a0'], wires['b0'], wires['w1'], and_tt)  # w1 = a0 AND b0
g2 = garble_gate(wires['a1'], wires['b1'], wires['w2'], and_tt)  # w2 = a1 AND b1
g3 = garble_gate(wires['w1'], wires['w2'], wires['out'], xor_tt) # out = w1 XOR w2

# Output decoding table: maps output labels to bits
decode_table = {wires['out'][0]: 0, wires['out'][1]: 1}

print("=== Garbled Circuit: 1-bit Inner Product ===")
print(f"Circuit: (a0 AND b0) XOR (a1 AND b1)")
print(f"Garbled gates: 3 (two AND, one XOR)")
print(f"Wires: 7 (4 input, 2 intermediate, 1 output)")
print(f"Wire labels: {7 * 2} = 14 random 128-bit strings")

def evaluate_circuit(inputs_alice, inputs_bob):
    """Evaluate the garbled inner product circuit."""
    a0, a1 = inputs_alice
    b0, b1 = inputs_bob
    
    # Get input labels
    la0 = wires['a0'][a0]
    la1 = wires['a1'][a1]
    lb0 = wires['b0'][b0]
    lb1 = wires['b1'][b1]
    
    # Evaluate gate 1: w1 = a0 AND b0
    valid_w1 = {wires['w1'][0], wires['w1'][1]}
    lw1 = evaluate_gate(g1, la0, lb0, valid_w1)
    
    # Evaluate gate 2: w2 = a1 AND b1
    valid_w2 = {wires['w2'][0], wires['w2'][1]}
    lw2 = evaluate_gate(g2, la1, lb1, valid_w2)
    
    # Evaluate gate 3: out = w1 XOR w2
    valid_out = {wires['out'][0], wires['out'][1]}
    l_out = evaluate_gate(g3, lw1, lw2, valid_out)
    
    return decode_table[l_out]

# Test all 16 input combinations
print("a0 a1 b0 b1 | Expected Got ")all_correct = True
for a0 in [0, 1]:
    for a1 in [0, 1]:
        for b0 in [0, 1]:
            for b1 in [0, 1]:
                expected = (a0 & b0) ^^ (a1 & b1)
                got = evaluate_circuit((a0, a1), (b0, b1))
                ok = '✓' if got == expected else '✗'
                if got != expected:
                    all_correct = False
                print(f"{a0} {a1} {b0} {b1} | {expected} {got} {ok}")

print(f"\nAll 16 combinations correct? {all_correct}")

5. The Full Yao Protocol

In a real two-party computation:

1. Alice (garbler) knows her input $a$ and builds the garbled circuit

2. Alice sends Bob: the garbled circuit + her input labels (for her actual bits)

3. Bob (evaluator) needs his input labels, but Alice can't just send them (she'd learn $b$!)

4. They use Oblivious Transfer (OT): Bob selects his labels without Alice learning which

5. Bob evaluates the garbled circuit and gets the output label

6. The decoding table maps the output label to the actual result

# Simulate the protocol flow
alice_input = (1, 0)  # Alice's bits
bob_input = (1, 1)    # Bob's bits
expected = (alice_input[0] & bob_input[0]) ^^ (alice_input[1] & bob_input[1])

print("=== Yao's Protocol Simulation ===")
print()
print(f"Alice's input: a = ({alice_input[0]}, {alice_input[1]})")
print(f"Bob's input:   b = ({bob_input[0]}, {bob_input[1]})")
print(f"Expected output: f(a, b) = {expected}")
print()
print("Step 1: Alice garbles the circuit (already done above)")
print(f"Step 2: Alice sends garbled circuit + her input labels:")
print(f"  Label for a0={alice_input[0]}: {label_hex(wires['a0'][alice_input[0]])}")
print(f"  Label for a1={alice_input[1]}: {label_hex(wires['a1'][alice_input[1]])}")
print(f"Step 3: Bob gets his labels via OT (simulated):")
print(f"  Label for b0={bob_input[0]}: {label_hex(wires['b0'][bob_input[0]])}")
print(f"  Label for b1={bob_input[1]}: {label_hex(wires['b1'][bob_input[1]])}")
print(f"Step 4: Bob evaluates the garbled circuit")

result = evaluate_circuit(alice_input, bob_input)
print(f"Step 5: Output = {result}")
print(f"Correct? {result == expected}")
print()
print("What each party learns:")
print("  Alice: nothing (she doesn't see Bob's labels or the evaluation)")
print("  Bob: only the output bit (labels are random, he can't infer inputs)")

Misconception alert. "The evaluator can figure out the input bits by looking at the wire labels." No! Each label is a random 128-bit string with no relation to 0 or 1. The evaluator cannot distinguish label-for-0 from label-for-1 without the decoding table (which is only provided for the output wire).

Crypto foreshadowing. The missing piece is Oblivious Transfer, how Bob gets his input labels without Alice learning Bob's input bits. The next notebook covers OT in detail.

6. Exercises

Exercise 1 (Worked): Garbled OR Gate

Problem. Garble an OR gate and verify it works for all four input combinations.

Solution:

# Exercise 1: Worked solution
w_or_a = (random_label(), random_label())
w_or_b = (random_label(), random_label())
w_or_out = (random_label(), random_label())

or_tt = lambda a, b: a | b
garbled_or = garble_gate(w_or_a, w_or_b, w_or_out, or_tt)
valid_or = {w_or_out[0], w_or_out[1]}

print("Garbled OR gate:")
for a in [0, 1]:
    for b in [0, 1]:
        label_out = evaluate_gate(garbled_or, w_or_a[a], w_or_b[b], valid_or)
        bit_out = 0 if label_out == w_or_out[0] else 1
        expected_or = a | b
        print(f"  OR({a}, {b}) = {bit_out} (expected {expected_or}) {'✓' if bit_out == expected_or else '✗'}")

Exercise 2 (Guided): Garbled Comparison

Problem. Garble a circuit that computes whether $a > b$ for 1-bit inputs. (Hint: $a > b$ iff $a = 1$ and $b = 0$, which is $a \text{ AND } (\text{NOT } b)$.)

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Create wire labels for inputs a, b and output
# w_a = (random_label(), random_label())
# w_b = (random_label(), random_label())
# w_gt = (random_label(), random_label())

# TODO 2: Define truth table for a > b (1-bit)
# gt_tt = lambda a, b: 1 if (a == 1 and b == 0) else 0

# TODO 3: Garble the gate
# garbled_gt = garble_gate(w_a, w_b, w_gt, gt_tt)

# TODO 4: Test all 4 combinations
# valid_gt = {w_gt[0], w_gt[1]}
# for a in [0, 1]:
#     for b in [0, 1]:
#         lbl = evaluate_gate(garbled_gt, w_a[a], w_b[b], valid_gt)
#         bit = 0 if lbl == w_gt[0] else 1
#         print(f"  {a} > {b}? {bit} (expected {gt_tt(a,b)})")

Exercise 3 (Independent): Cost Analysis

Problem.

1. How many garbled entries does a circuit with $g$ gates require?

2. For a 32-bit integer comparison circuit, estimate the number of gates and the total size of the garbled circuit.

3. Why is Yao's protocol called a "constant-round" protocol? How many rounds of communication does it need?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Wire labels	Two random labels per wire (one for 0, one for 1)
Garbling	Encrypt output labels under input labels; shuffle entries
Evaluation	Try decrypting each entry; exactly one succeeds
Security	Labels are random, evaluator can't tell 0 from 1
Protocol	Alice garbles, Bob evaluates, OT provides Bob's labels
Rounds	Constant (2-3), entire circuit evaluated in one pass

Yao's garbled circuits turn any Boolean function into a secure two-party protocol. The garbler encrypts the circuit; the evaluator decrypts gate by gate. The missing ingredient, how the evaluator gets their input labels without revealing their input, is Oblivious Transfer.

---

Next: 12d: Oblivious Transfer