---
kind: concept
slug: garbled-circuits
title: Garbled circuits
summary: >-
  Garbled circuits let parties run a boolean circuit on wire keys that hide the values, with garblers building it and one evaluator running it. Only one card so far: a four-party ML framework that uses garbled sharing for bit-level conversions and softmax division, with the evaluator fixed to one party. Author-reported speed-ups are framework-wide, not garbled-only.
tags: [mpc, privacy-preserving-ml, garbled-circuits]
papers: ["1912.02631"]
related: []
status: draft
updated_at: 2026-10-19
---

## 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
[arxiv: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 [arxiv:1912.02631 §4]. The paper's garbling
uses free XOR, half gates and fixed-key AES [arxiv: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](/papers/1912.02631).

- **Roles.** Parties P1 to P3 garble, and P0 is the only evaluator [arxiv: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 [arxiv: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 [arxiv:1912.02631 §4.1].
- **No oblivious transfer.** The paper states that the garbled world needs none [arxiv: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 [arxiv: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 [arxiv:1912.02631 app. C, tab. 9]. The text gives no value for κ [arxiv:1912.02631 §4.1].
- **Division.** The softmax output layer divides by a sum inside a garbled circuit. The paper does not describe that circuit [arxiv: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.

| Situation | Use | Why |
|---|---|---|
| Only additions and multiplications, such as linear or logistic regression | Stay in arithmetic sharing | Those training updates run in arithmetic sharing without any garbled step [arxiv:1912.02631 §6.1] |
| A comparison, a sign bit or a division inside a mixed protocol | Convert to the garbled world for that step | The paper uses garbled circuits for the softmax division and for the conversions [arxiv:1912.02631 §4.3, §6.1] |
| Three parties with an honest majority, or no fourth server available | This setting does not apply | The paper's framework assumes four parties with at most one corrupt [arxiv:1912.02631 §1] |
| Latency is the main constraint | Use the paper's framework-level numbers, not garbled-only numbers | Its LAN and WAN results cover the whole framework. For neural-network prediction at batch size 1 on MNIST, WAN latency is 2.31 s against 6.02 s for ABY3 [arxiv:1912.02631 tab. 7] |

Trade-off: the evaluator is one party, so it does all the work in garbled
steps [arxiv: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.

```pseudocode
# 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
```

```pseudocode
# 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 [arxiv: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](/papers/1912.02631): a four-party framework with arithmetic, boolean and garbled sharing, using garbled circuits for conversions and the softmax division.