Garbled circuits

Overview

A garbled circuit is a boolean circuit whose wire values are hidden behind keys. Garblers build it, and one evaluator runs it on the keys it holds 1912.02631 §4.1. The only card so far uses garbled circuits as one of three sharing types in a mixed framework. The other two are arithmetic and boolean sharing, and conversions move a value between the three 1912.02631 §4. The paper's garbling uses free XOR, half gates and fixed-key AES 1912.02631 §4.1.

Variants

Garbled sharing in a four-party mixed framework

This is the only variant covered so far. Card: Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning.

• Roles. Parties P1 to P3 garble, and P0 is the only evaluator 1912.02631 §4.1.
• Sharing a bit. The garblers commit to both wire keys, and P0 checks the commitments before using them. The verifiable variant follows ABY3 1912.02631 §4.1, §4.2.
• AND gates. One garbler sends a garbled table and another sends a hash of it. XOR gates need no table, because of free XOR 1912.02631 §4.1.
• No oblivious transfer. The paper states that the garbled world needs none 1912.02631 §4.1.
• Conversions. Four conversions connect the garbled world to the others: garbled to boolean, garbled to arithmetic, boolean to garbled and arithmetic to garbled 1912.02631 §4.3. The paper lists their offline and online costs in rounds and communication. Online communication, as listed, is 3 for garbled to boolean, 3ℓ for garbled to arithmetic, κ for boolean to garbled and ℓκ for arithmetic to garbled. Here ℓ is the ring size and κ the security parameter 1912.02631 app. C, tab. 9. The text gives no value for κ 1912.02631 §4.1.
• Division. The softmax output layer divides by a sum inside a garbled circuit. The paper does not describe that circuit 1912.02631 §6.1.

Other garbled-circuit constructions

No other card covers this concept. Constructions described in other papers are left out until their cards exist.

When to use which

The table reflects one paper. It names the design points that paper uses and the conditions under which it applies them.

Trade-off: the evaluator is one party, so it does all the work in garbled steps 1912.02631 §4.1. The paper does not measure how this affects load or latency in practice beyond the reported totals.

Implementation sketch

Language-agnostic outline of the common core. The steps follow the card's description of the garbled world. The parts that vary between constructions are not covered, since only one is on record.

# Garbling side: P1 to P3 build the garbled circuit  [arxiv:1912.02631 §4.1]
def garble(circuit):
    # Draw one key per wire value  [§4.1]
    keys = random_wire_keys(circuit)
    # Commit to the wire keys of the inputs being shared  [§4.1]
    commitments = commit_input_keys(keys, circuit.inputs)
    # Free XOR: XOR gates need no table. AND gates get one  [§4.1]
    tables = [garble_and(g, keys) for g in circuit.and_gates]
    return keys, commitments, tables

# Evaluation side: P0 is the only evaluator  [arxiv:1912.02631 §4.1]
def evaluate(circuit, tables, commitments, input_keys):
    # Check the commitments before using the input keys  [§4.1]
    assert all(verify(c, k) for c, k in zip(commitments, input_keys))
    # Run the gates in circuit order, one key per output wire  [§4.1]
    wire = dict(zip(circuit.inputs, input_keys))
    for gate, table in zip(circuit.gates, tables):
        wire[gate.out] = eval_gate(gate, table, wire)
    return [wire[o] for o in circuit.outputs]

Contradictions

Only one card lists this concept, so no two papers disagree. Within that paper, the headline speed-up differs between the abstract and the text. The abstract gives up to 187x for training, while the text gives up to 251.84x for LAN linear-regression training 1912.02631 §1, §6.1. The card records this in its Pitfalls section, and the table values do not reproduce the 251.84x figure exactly. Do not use either figure without checking the source.

Papers

• Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning: a four-party framework with arithmetic, boolean and garbled sharing, using garbled circuits for conversions and the softmax division.