Secure Multi-Party Computation (MPC)

Privacy is the fundamental guarantee that no party learns anything more about another party's private input than what can be inferred from the output of the computed function. This is formalized using simulation-based security: the view of any participant during the protocol execution can be computationally simulated using only that party's input and the final output, proving no extra information is leaked.

• Example: In a joint salary average calculation, participants learn only the final average, not individual salaries.
• Threshold Adversaries: Protocols are often characterized by a threshold t, specifying the maximum number of colluding, malicious parties the protocol can tolerate while still preserving privacy (e.g., 'privacy against t < n/2 corruptions').

Correctness ensures that the protocol computes the intended function accurately. All honest participants are guaranteed to receive the correct output, even in the presence of malicious parties who may deviate from the protocol. This property is typically enforced through cryptographic commitments and verifiable secret sharing.

• Guaranteed Output Delivery: A stronger variant ensures honest parties always receive an output, preventing malicious parties from aborting the protocol to deny service.
• Robustness: The protocol produces the correct output regardless of adversarial behavior, often requiring mechanisms to identify and exclude cheating parties.

This property guarantees that parties must commit to their inputs before learning anything about the inputs of others. It prevents an adversary from choosing their input as a function of another party's input, which could leak information or manipulate the result.

• Formalization: Achieved via a commitment phase where inputs are cryptographically locked in.
• Importance: Critical for fairness in auctions or financial computations where a late-choosing party could gain a decisive advantage.

Fairness ensures that if any party learns the output of the computation, then all honest parties learn the output. It prevents a scenario where a malicious party gains the result (e.g., the winning bid in an auction) and then aborts the protocol to prevent others from learning it. Achieving perfect fairness in asynchronous networks is generally impossible; most practical protocols offer partial fairness or incorporate a trusted arbiter for dispute resolution.

A stronger property than fairness, Guaranteed Output Delivery ensures that all honest parties will always receive the computation's output, regardless of whether malicious participants abort the protocol. This is crucial for business-critical operations where denial-of-service is unacceptable.

• Implementation: Often requires a trusted dealer in the setup phase or sophisticated non-blocking consensus among parties.
• Trade-off: Protocols with this guarantee typically have higher communication complexity or require a strict majority of honest participants.

A protocol is secure under composition if its security guarantees hold even when it is executed concurrently with other instances of itself or other protocols. This is essential for real-world systems where multiple MPC sessions run in parallel.

• Universal Composability (UC): A rigorous framework that defines security such that a UC-secure protocol can be used as a modular 'black box' within any larger system without compromising security.
• Stand-alone vs. Concurrent: Weaker stand-alone security analyzes a protocol in isolation, while stronger concurrent security accounts for coordinated attacks across multiple sessions.

Algorithms designed for distributed systems where some participants may be malicious ('Byzantine' nodes). These algorithms compute a correct aggregate value (like a model update average) even when a subset of nodes send arbitrary, adversarial, or faulty data.

• Critical for Decentralized AI: Essential for secure federated learning and MPC in adversarial environments.
• Techniques: Includes median-based methods, trimmed means, and Krum, which identify and exclude outlier updates.
• Without Byzantine robustness, a single malicious participant in an MPC or federated learning round could corrupt the final model.