Secure Multi-Party Computation (MPC)

Privacy is the paramount security guarantee of MPC. It ensures that no party learns anything about another party's private input beyond what can be inferred from the protocol's final output. This is formalized using a simulation-based security paradigm, which proves that a party's view of the protocol (its internal state, messages received) can be simulated using only its own input and the final output, meaning it contains no extra information about other inputs.

• Example: In a joint salary average computation, each company learns only the final average, not any other company's individual salary figure.
• This property holds even against semi-honest (passive) or malicious (active) adversaries, depending on the protocol design.

Correctness guarantees that the protocol computes the intended function accurately. All honest participants are assured to receive the correct output, provided the protocol is followed. This property is challenged in the presence of malicious adversaries who may deviate from the protocol to produce a wrong result.

• Robust MPC protocols ensure correctness regardless of malicious behavior, often using techniques like verifiable secret sharing and commitments.
• Fairness is a stronger form of correctness, ensuring that if any party receives the output, all honest parties receive it, preventing one party from gaining an advantage by aborting early.

This property ensures that each party's input is fixed and chosen independently at the protocol's start, and cannot be changed based on inputs from other parties. It prevents adaptive input selection attacks, where a malicious party could tailor its input after seeing others' contributions to manipulate the output or learn more information.

• Protocols enforce this through commitment schemes, where parties first commit to their inputs (e.g., by publishing a cryptographic hash) before the computation phase begins.
• This is crucial for applications like sealed-bid auctions or secure voting, where a bidder's or voter's choice must be immutable.

Guaranteed Output Delivery ensures that honest parties will always receive the computed output, even if some participants abort the protocol or refuse to cooperate. This is a stronger guarantee than fairness and is essential for business-critical computations.

• Achieving this typically requires a majority of honest participants (e.g., honest majority assumption).
• Protocols without this property may only offer fairness (all get output or none do) or may allow a single malicious party to abort the computation, wasting resources.
• This property is often implemented using robust reconstruction techniques in secret sharing, where the secret can be recovered from any sufficient subset of shares.

MPC protocols are designed and proven secure under specific adversarial models and trust assumptions, which define their practical applicability.

• Semi-Honest (Passive) Adversaries: Follow the protocol but try to learn extra information from their view. Provides privacy but not correctness against active cheating. More efficient.
• Malicious (Active) Adversaries: Can arbitrarily deviate from the protocol. Protocols must ensure both privacy and correctness. More computationally intensive.
• Trust Assumptions:
  • Honest Majority: Security holds if more than half (or two-thirds) of parties are honest.
  • Threshold Trust: Security holds if the number of corrupt parties is below a fixed threshold (t-out-of-n).
  • Trusted Dealer: Some setups assume a one-time trusted party to distribute initial secret keys or material.

MPC protocols are not monolithic but are constructed from lower-level cryptographic building blocks. Understanding these primitives is key to understanding MPC's mechanics.

• Secret Sharing: Splits a secret into shares distributed among parties (e.g., Shamir's Secret Sharing). The secret is reconstructed only when a threshold of shares are combined. Forms the basis for secure computation.
• Garbled Circuits: A two-party computation technique where one party (the garbler) encrypts a Boolean circuit, and the other (the evaluator) computes on it without learning intermediate values.
• Oblivious Transfer (OT): A fundamental primitive where a receiver obtains one of several messages from a sender without the sender learning which message was chosen, and the receiver learns nothing about the other messages. Essential for many MPC constructions.
• Homomorphic Encryption: Allows computation on encrypted data. While distinct from MPC, fully homomorphic encryption (FHE) can be used to build MPC protocols where one party does most of the computation.

A form of encryption that allows computations to be performed directly on encrypted data. The encrypted result, when decrypted, matches the result of operations performed on the plaintext. This enables outsourced computation on sensitive data without granting the processor access to the raw information.

• Key Types: Supports partially homomorphic (one operation), somewhat homomorphic (limited operations), and fully homomorphic encryption (unlimited operations).
• Contrast with MPC: While MPC involves multiple parties jointly computing a function, homomorphic encryption often involves a single party performing computation on another party's encrypted data. They can be combined for hybrid protocols.

A decentralized machine learning paradigm where a global model is trained across multiple client devices or servers, each holding local data. Training occurs locally; only model updates (e.g., gradients or weights) are shared with a central coordinator, not the raw data.

• Core Principle: Data remains at the source. This mitigates privacy risks associated with centralizing sensitive datasets.
• Relationship to MPC: MPC can secure the aggregation step in federated learning, ensuring the central server learns only the final aggregated update and nothing about individual client contributions.

A cryptographic protocol where one party (the prover) can prove to another party (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself.

• Key Properties: Completeness, soundness, and zero-knowledge.
• Use with MPC: ZKPs can be integrated into MPC protocols to allow parties to prove they are following the protocol correctly (e.g., proving a computed value lies within a valid range) without leaking their private inputs, enhancing verifiability and security against malicious participants.

A rigorous mathematical framework that provides a quantifiable privacy guarantee. It ensures the output of a computation is statistically indistinguishable whether any single individual's data is included or excluded from the input dataset.

• Mechanism: Achieved by injecting calibrated random noise (e.g., via Laplace or Gaussian mechanisms) into query results or model outputs.
• Synergy with MPC: MPC can be used to implement differential privacy in a distributed setting. Parties can jointly compute a noisy aggregate without any party seeing the raw data or the exact noise value, strengthening trust in the privacy mechanism.

A secure, isolated area within a main processor (e.g., Intel SGX, AMD SEV) that guarantees confidentiality and integrity for code and data executing inside it. The host operating system and other software cannot view or tamper with the TEE's contents.

• Hardware Root of Trust: Relies on hardware features to enforce isolation.
• Alternative/Complement to MPC: TEEs offer a different trust model. MPC provides cryptographic security without trusted hardware, while a TEE creates a 'trusted black box.' They are sometimes used together, where MPC protocols run inside attested TEEs for enhanced performance and security.

A specific cryptographic protocol and a classic application of MPC. It allows two or more parties, each holding a private set of items, to compute the intersection of their sets without revealing any information about items not in the intersection.

• Practical Applications: Finding common contacts in encrypted contact lists, matching compromised passwords across services without revealing the lists, or collaborative fraud detection between banks.
• Protocol Types: Can be built using generic MPC frameworks, oblivious transfer, or specialized cryptographic techniques like Diffie-Hellman-based approaches for two-party cases.