Computing on Secrets Together

Part 5 of 6. Ideal-world security, oblivious transfer, Yao’s garbled circuits, GMW, and privacy-preserving applications.

Outline — prose not written

Use one AND gate as the concrete walkthrough. Keep the broader protocols at comparison level.

Throughline

Several parties can compute a function of private inputs while revealing no more than the function's output already implies.

Start with two private bits $a,b$ and the desired output $a\land b$ .
Explain unavoidable leakage: if $a=1$ and the output is $0$ , then $b=0$ follows from the output.
Define the goal correctly: learn nothing beyond one's own input and the prescribed output.
Use the five-card AND protocol as a no-hardness-assumption warm-up.

Reference: Evans–Kolesnikov–Rosulek ch. 1

Introduce the ideal world: a trusted party receives inputs and returns only the allowed outputs.
Define real-world security through simulation of the adversary's view.
Separate:
- semi-honest: follows the protocol but inspects everything
- malicious: deviates, lies, aborts, or sends malformed values
Ground the goal with Yao's millionaires and private set intersection.

Reference: Evans–Kolesnikov–Rosulek ch. 2; Lindell, “How to Simulate It”

Define 1-out-of-2 OT:
- sender holds $(m_0,m_1)$
- receiver holds $b$
- receiver learns only $m_b$
- sender learns nothing about $b$
Sketch a DH-based construction without proving it.
Explain OT extension: a small number of public-key OTs bootstrap many symmetric-key OTs.
State why it matters: garbled circuits need one OT per evaluator input bit.

Reference: Evans–Kolesnikov–Rosulek §3.7; IKNP (2003)

Explain why exactly one row decrypts and why intermediate labels reveal no bit values.

Build these in order so each optimization has a visible target:

Optimization	What it changes
Point-and-permute	Adds a selection bit to each label so the evaluator opens one row instead of trying all four.
Free-XOR	Correlates labels with a global offset so XOR gates need no garbled rows.
Half-gates	Reduces each AND gate from four ciphertexts to two while remaining compatible with free-XOR.
OT extension	Replaces most public-key input OTs with cheap symmetric operations.

Use a tiny before/after circuit to count garbled ciphertexts.
Mention the extra assumptions behind free-XOR and the hash/cipher instantiation.
Keep row reduction as a historical footnote; half-gates are the cleaner modern endpoint.

Reference: Evans–Kolesnikov–Rosulek §3.1–3.4

Optimization reference: Kolesnikov–Schneider (2008); Zahur–Rosulek–Evans (2015)

Explain the malicious-security compiler at a high level: commitments and zero-knowledge proofs enforce honest execution.

Reference: Evans–Kolesnikov–Rosulek §3.5 and ch. 6; GMW (1987)

Private set intersection: compromised-credential checks.
Privacy-preserving ML: inner products are cheap; comparisons and nonlinear activations dominate cost.
Joint analytics: aggregate across organizations without pooling raw records.
Keep performance caveats explicit: circuit size, communication, malicious security, and aborts.

MPC keeps parties online and interacting. Homomorphic encryption lets one server compute alone.

Evans, Kolesnikov, and Rosulek, A Pragmatic Introduction to Secure Multi-Party Computation
Lindell, How to Simulate It
Yao (1986) and Goldreich–Micali–Wigderson (1987)
Scribed applied cryptography notes, §16–20