MPC via Arithmetic Circuits and Beaver's Protocol

Corresponds to Chapter 23.1–23.2, 23.4, 23.7 (the basic idea and informal security goals of MPC are already covered in secret-sharing-multi-party-and-computational-differential-privacy). Covers the concrete, constructive side: representing a computation as an arithmetic circuit over secret-shared inputs, where addition gates are free (shares just add locally) but multiplication gates need interaction — Beaver’s protocol solves this using precomputed, correlated random triples ($a$, $b$, $a\cdot b$, secret-shared ahead of time, independent of the actual inputs) that let an online multiplication be computed with just one round of communication, first in the simpler honest-but-curious (“2.5-party”) setting and then hardened against actively malicious parties. Covers extending this core to a general multi-party protocol (processing arbitrary inputs/outputs around a secure distributed core — see garbled-circuits-and-the-uc-framework for the alternative garbled-circuit approach and the formal UC security framework both are proved secure in) and OT extension — the key efficiency trick letting a handful of expensive public-key-based oblivious transfers be stretched, using only cheap symmetric-key operations, into as many OTs as a protocol needs.

Outline (TODO — flesh out each)

• The basic idea of MPC — informal security, assumptions, other applications
• Arithmetic circuit evaluation via secret sharing
• Beaver’s protocol — an honest-but-curious 2.5-party protocol
• Abstracting Beaver’s 2.5-party protocol
• A maliciously secure version of Beaver’s protocol
• Multi-party computation based on a secure distributed core
• Processing inputs and outputs
• OT extension
• Fun application: private set intersection, revisited