Secure Multi-Party Computation (MPC)

This is the paramount property of MPC. It guarantees that no party learns anything more about another party's private input than what can be inferred from the protocol's output. Formally, each party's view of the protocol execution (its input, random coins, and received messages) can be computationally simulated using only its own input and the final output. This holds even if parties collude.

• Example: In a private salary comparison, two employees learn only who has the higher salary, not the exact figure of the other.
• Formalization: Achieved through cryptographic primitives like secret sharing or garbled circuits, which ensure data is never reconstructed in plaintext by any single party.

An MPC protocol must guarantee that the computed output is accurate and corresponds to the result of applying the agreed-upon function to the honest parties' inputs. This must hold even in the presence of malicious adversaries who may attempt to deviate from the protocol to corrupt the result. Protocols achieve this through mechanisms like commitment schemes and verifiable secret sharing.

• Honest-Majority vs. Dishonest-Majority: Some protocols guarantee correctness only if a majority of parties are honest (e.g., 2 out of 3). Others, using heavier cryptography, can ensure correctness even if all but one party are malicious.
• Robustness: A stronger property where the protocol always delivers output. Fairness ensures if one party gets the output, all do.

The security guarantees of an MPC protocol are defined relative to a specific adversarial model, which specifies the corruption power of participating parties.

• Semi-Honest (Passive): Adversaries follow the protocol but try to learn extra information from the transcript. Provides privacy but not correctness against active cheating.
• Malicious (Active): Adversaries can arbitrarily deviate from the protocol. Protocols must ensure both privacy and correctness against such attacks, often using zero-knowledge proofs to force compliance.
• Static vs. Adaptive: Static corruption chooses which parties to corrupt before the protocol runs. Adaptive corruption can decide during execution, a stronger model.
• Coalition Size: Security is often parameterized by a threshold t, defining the maximum number of colluding parties the protocol can tolerate (e.g., t < n/2 for honest-majority).

A critical framework for analyzing MPC protocols in complex, real-world environments. A protocol that is Universally Composable (UC) remains secure even when run concurrently with arbitrary other protocols or multiple instances of itself. This is essential for deployment in modular systems.

• Ideal vs. Real Paradigm: Security is proven by showing that anything an adversary can do in the real protocol execution can also be done in an ideal world where a trusted third party computes the function. If the two worlds are indistinguishable, the protocol is UC-secure.
• Implication: A UC-secure protocol can be used as a black-box module without fear of unforeseen security interactions, a key requirement for enterprise cryptographic infrastructure.

MPC protocols are characterized by their communication overhead and computational complexity, which determine practical feasibility.

• Rounds of Communication: The number of sequential message exchanges between parties. Constant-round protocols (e.g., using garbled circuits) are vital for high-latency networks.
• Total Bandwidth: The volume of data sent. Some protocols have bandwidth linear in circuit size, while others may be quadratic.
• Computational Cost: The local cryptographic operations (encryptions, modular exponentiations) each party must perform. This is often the primary bottleneck.
• Trade-offs: Protocols make explicit trade-offs between these resources and the adversarial model (e.g., malicious security requires more rounds and bandwidth than semi-honest).

MPC is not an isolated construct; it leverages and is related to several core cryptographic primitives.

• Secret Sharing (e.g., Shamir's): Splits a secret into n shares; t+1 shares are needed to reconstruct. The foundation of many MPC protocols.
• Garbled Circuits (Yao's Protocol): Allows two-party computation. One party garbles a Boolean circuit; the other evaluates it without learning intermediate values.
• Homomorphic Encryption (HE): Allows computation on ciphertexts. Somewhat HE (add/mult) is used as a component in hybrid MPC protocols. Fully HE is an alternative to MPC but is often less efficient for complex functions.
• Oblivious Transfer (OT): A fundamental building block where a receiver gets one of several messages from a sender without the sender learning which was chosen. Essential for garbled circuits and many MPC protocols.