Secure multi-party computation

Overview

Several parties hold private inputs and want a function of all of them, without any party seeing another's input. The paper's setting is machine learning: servers hold secret-shared data and jointly train or query a model 1912.02631 §1. Each server sees only a random-looking piece of every value, and the protocol works on those pieces.

Three ideas recur in the one card on record:

1. Sharing. Each value is split into pieces, one per party, so that no single piece reveals it. The paper uses three sharing types: additive, replicated and masked 1912.02631 §3.1.
2. Local work where possible. Addition, and multiplication by a public constant, need no communication in any of the three sharing types 1912.02631 §3.1.
3. Checks. Parties that receive shares also receive hashes of them, so a party that cheats is caught, usually at output time rather than at the step where it cheated 1912.02631 §3.2.

The main difficulty is the non-linear step. Multiplication needs communication, and comparisons, truncation after fixed-point products, and activation functions need still more 1912.02631 §1, §5.

Variants

Only one variant has a card. It is named here so that it can be compared with future cards.

Four-party mixed-world framework (Trident)

Four servers, P0 to P3, with at most one corrupt. The protocol holds arithmetic, boolean and garbled sharings and converts between them, so each step runs in the sharing type that is cheapest for it 1912.02631 §1, §4. The paper states the security model as static malicious, in a hybrid model with a setup functionality 1912.02631 app. F. Card: Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning.

• Multiplication. A verified four-party multiplication costs 3 ring elements online per gate. The paper counts 6 elements per gate in total, 3 offline and 3 online, against 4 online for the four-party protocol of Gordon et al. at the same total 1912.02631 §1, §3.2.
• Dot products. The communication for a dot product does not depend on the vector length 1912.02631 §4.2.
• Truncation. Truncation after a multiplication uses no boolean circuit 1912.02631 §5.1.
• Comparisons and activations. ReLU and the piecewise sigmoid run in a constant number of rounds 1912.02631 §5.3, tab. 10.
• Stages. Input sharing, evaluation, then output reconstruction 1912.02631 §3.3.
• Baseline. The paper compares against ABY3 in its malicious and semi-honest versions, both re-implemented by the authors, since their code was not public 1912.02631 §6, app. E.

Other constructions

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

When to use which

The table reflects one paper, its own benchmarks, and the constraints it names. Its numbers are author-reported.

Trade-off: a fourth server costs more to run, which the authors discuss as monetary cost 1912.02631 §1, app. E. Their WAN comparison with Gordon et al. has the paper's protocol at 16.19 s total online runtime, against 21.52 s for Gordon et al. on the AES-128 circuit [arxiv:1912.02631 app. E, tab. 11].

Implementation sketch

Language-agnostic outline of the three stages. The shapes are the card's; the details of each step are in the linked cards and in the paper.

# Stage 1: the owner of each input shares it  [arxiv:1912.02631 §3.3]
def share_inputs(inputs):
    # Each value gets one piece per party, plus hashes for checks  [§3.2]
    return {name: share_value(v) for name, v in inputs.items()}

# Stage 2: evaluate gates in topological order  [arxiv:1912.02631 §3.3]
def evaluate(circuit, shares):
    for gate in circuit.gates:
        # Addition is local for every sharing type  [§3.1]
        if gate.op == "add":
            shares[gate.out] = add_local(shares[gate.a], shares[gate.b])
        # Multiplication runs the interactive protocol  [§3.2]
        else:
            shares[gate.out] = mult_protocol(shares[gate.a], shares[gate.b])
    return shares

# Stage 3: reconstruct each output  [arxiv:1912.02631 §3.3]
def reveal(shares, outputs):
    # Each party receives its missing piece and a hash of it  [§3.2]
    return [reconstruct(shares[o]) for o in outputs]

Contradictions

Only one card lists this concept, so no two papers disagree. Within that paper:

• Headline speed-ups. The abstract gives up to 187x for training and up to 158x for prediction. The text gives up to 251.84x for LAN linear-regression training, and the table values do not reproduce that figure exactly. The 158x figure matches one logistic prediction ratio in the text [arxiv:1912.02631 §1, §6.1, §6.2]. Do not use either headline without checking the source.
• ABY3 semi-honest baseline. The introduction quotes 2.5 iterations per second for ABY3 on the neural network at batch size 128. The authors' own ABY3S measurement is 1.01 1912.02631 §1, app. E, tab. 13.
• Sign convention of additive sharing. The three parts of an additive sharing are defined with one sign in one step and read with another sign in others. Read literally, one of those steps is inconsistent with the definition 1912.02631 §3.2, §4.3, §5.1. An implementation has to pick one convention and test it.
• Truncation and sharing soundness. Truncation is probabilistic and its error bound is deferred to the earlier work it builds on. The soundness of the random checks on the sharings is not quantified [arxiv:1912.02631 §5.1, §6.2].

Papers

• Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning: a four-party framework, at most one corrupt, mixing arithmetic, boolean and garbled sharings for ML training and prediction.