crypto-garbled-circuits

name: crypto-garbled-circuits description: Garbled circuits and multi-party computation — Yao's protocol, oblivious transfer, and MPC extensions

What I do

• Guide garbled circuit protocol implementation from circuit design to evaluation
• Document oblivious transfer protocols and amortized OT extensions
• Cover optimization techniques (free-XOR, half-gates, point-and-permute)
• Provide multi-party computation extensions and MPC tooling guidance

When to use me

Use this skill when implementing two-party or multi-party computation protocols, designing garbled circuits, or working with oblivious transfer. Pair with crypto-core for shared foundations and security checklists.

Security Models

Always state which security model your implementation targets. Semi-honest protocols are NOT secure against malicious adversaries.

Yao's Garbled Circuits Protocol

Protocol Flow (Semi-Honest)

1. Agree on function -- Both parties agree on a Boolean circuit C computing f(x, y) Security: circuit is public; no information leaks here

2. Garbler generates wire labels -- For each wire w, create two random labels (w0, w1) representing bit values 0 and 1 Security: labels must be indistinguishable; use crypto RNG

3. Garbler garbles gates -- For each gate, encrypt the output labels under the corresponding input labels using a PRF or hash Security: garbled table reveals nothing about gate semantics

4. Garbler sends garbled circuit + own input labels -- Transmit garbled tables and labels corresponding to the garbler's actual input bits Security: only labels for garbler's actual bits are sent

5. Oblivious transfer for evaluator's input -- Evaluator obtains labels for their input bits via 1-out-of-2 OT without revealing choice bits Security: OT ensures garbler cannot learn evaluator's input

6. Evaluator evaluates -- Decrypt each garbled gate using the received input labels to obtain the output labels Security: evaluator sees only one label per wire (their path)

7. Output decoding -- Garbler reveals the mapping from output labels to plaintext bits Security: only the output wire mapping is revealed

Oblivious Transfer

1-out-of-2 OT

Sender holds two messages (m0, m1). Receiver holds a choice bit b. After the protocol, receiver obtains m_b and sender learns nothing about b.

OT Extensions

Base OT is expensive (requires public-key cryptography). OT extensions amortize the cost: perform ~128 base OTs using public-key crypto, then derive millions of OTs using only symmetric-key operations.

Role in Garbled Circuits

OT is the mechanism that makes garbled circuit evaluation secure. Without it, the garbler could infer the evaluator's input from which wire labels were requested.

Optimizations

Modern implementations combine free-XOR + half-gates + point-and-permute. This gives XOR gates for free and AND gates at 2 ciphertexts each.

Multi-Party Extensions

When to use which approach:

• Use garbled circuits when the function is naturally Boolean and round count must be low
• Use secret sharing when the function is naturally arithmetic or the party count is high
• Use hybrid (ABY) when the function mixes Boolean and arithmetic operations

Circuit Representation

Bristol Format

Standard text format for Boolean circuits used by most MPC frameworks:

<num_gates> <num_wires>
<num_input_wires_party1> <num_input_wires_party2>
<num_output_wires>
<input_wires...> <output_wire> <gate_type>

Gate types: AND, XOR, INV, OR

Convert high-level functions to Bristol circuits using circuit compilers (CBMC-GC, HyCC) for C/C++ programs, or manual decomposition for small circuits. Minimize AND gate count -- AND gates are expensive while XOR gates are free with the free-XOR optimization.

Workflow: Implementing a Garbled Circuit Protocol

1. Specify -- Define the 2PC/MPC function f(x1, ..., xn). Identify which inputs are private to which party. Choose security model (semi-honest vs malicious).
2. Compile to Boolean circuit -- Convert the function to Boolean gates. Optimize for AND gate count (not total gate count). Use Bristol format.
3. Choose protocol -- 2 parties + Boolean: Yao's GC. n parties: GMW or BMR. Mixed computation: ABY. Malicious security: cut-and-choose or SPDZ.
4. Implement -- Use a framework (EMP-toolkit, MP-SPDZ, ABY). Do not implement OT or garbling primitives from scratch.
5. Test -- Verify correctness against plaintext computation. Test with adversarial inputs. Measure communication cost and round count.
6. Audit -- Run crypto-core code review checklist. Verify OT security. Check for wire label leakage. Confirm security model assumptions hold.

MPC Tooling

Anti-Patterns