skills/crypto-research-framing/references/mpc-worked-example.md

# An intermediate requirement for an MPC communication question

This is a hypothetical research exercise adapted from §6 of the user-supplied *Learning from Amit Sahai: A Cryptography Research Distillate* (research cutoff September 20, 2026). It is not an attributed construction or a solved protocol. Use it when a concrete example helps isolate a preprocessing interface; do not import its target into unrelated work.

## Target and unknowns

Suppose the researcher seeks lower communication for a two-round maliciously secure two-party protocol with circuit-independent preprocessing. Before choosing a construction, resolve the allowed corruption and composition, abort or delivery, output recipients, speaking order, when the circuit and inputs are known, and the exact preprocessing distribution. An ideal source of correlations is distinct from a maliciously secure distributed protocol generating them.

Let `kappa` and `sigma` denote the computational and statistical security parameters for this exercise. Define disjoint phases and, if the task concerns total communication, use an accounting convention such as

`C_total = C_setup + C_circuit-dependent preprocessing + C_online`.

Count transmitted bits with an explicit aggregation convention, including all traffic in exactly one phase. For amortization over `B` executions, separate one-time setup from per-execution material; the setup cost per execution is `C_setup/B` only when that reuse and batch size are justified. No preprocessing is free because it is circuit-independent, and fresh correlations are not reusable merely because their distribution has not changed.

## Isolate what the expensive step supplies

Describe the component by party holdings and a joint law, not just by naming a primitive. Which values can a malicious participant choose? Which are public or later revealed? What does the simulator know when it must produce each message? Which consistency relation must hold for the next stage, and what happens on malformed input?

Then consider an applicable change: express a relation directly over its natural field; use internal executions as checkable objects; or expose a value to simplify a computation. Each is a candidate. The last changes the target unless the extra disclosure can be simulated under the original permitted leakage. Reduced bit encoding costs can also be offset by conversion or consistency checks.

## A small calculation can rule out a candidate

Suppose a component generates two field elements `(X,Y)` over a finite field `F`. The original joint law is `(R,R)` for uniform `R` in `F`; a candidate samples independent uniform `(R,S)` instead. Each coordinate has the same marginal distribution. Nevertheless, a party observing both coordinates can test equality:

`Pr[X=Y | original] = 1`, while `Pr[X=Y | candidate] = 1/|F|`.

The difference in acceptance probabilities is `1 - 1/|F|`. This refutes preservation of the joint law and any justification based solely on matching marginals. If no permitted observer ever sees both coordinates, this calculation is not itself an attack on the whole protocol; identify the actual observer and any later check consuming the relation.

## State the next lemma and its missing premise

A useful candidate statement might be: for every adversary allowed by the fixed model, replacing component A by component B preserves the specified joint view and state within a declared statistical-distance or computational-distinguishing bound, while producing the interface required by each later consistency check. Name the view, conditioning, simulator interface, and bound before attempting its proof. This sentence is a statement template, not a proved lemma.

For `m` replacements, define the consecutive experiments and justify every transition with its retained state and adaptive choices. Only then accumulate the applicable bounds; a fresh-copy calculation alone does not cover correlated reuse. End with the exact missing claim or the concrete counterexample, and connect it to the communication term it would improve. Passing a one-gate check is not a proof of the full compiler.