Secure Multi-Party Computation

The fundamental guarantee of MPC. 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: anything a party sees during the protocol execution can be simulated using only that party's input and the final output, proving no extra information is leaked.

• Example: In a joint salary average computation, participants learn only the final average, not any individual's salary.
• Threat Model: Holds even against semi-honest (passive) adversaries who follow the protocol but try to learn extra information, and malicious (active) adversaries who may deviate arbitrarily.

The protocol guarantees that the computed output is accurate according to the predefined function, provided that a sufficient number of participants are honest. This ensures the integrity of the computation against errors or adversarial manipulation.

• Robustness: In many protocols, if any party aborts or provides malformed messages, the honest parties can still compute the correct output.
• Verifiability: Some advanced MPC schemes allow participants to verify that the output was computed correctly, even if the other parties (or the computation servers) are malicious.

Participants must commit to their inputs at the start of the protocol, before learning anything about others' inputs. This prevents an adversary from choosing their input as a function of another party's input, which could be used to extract information or manipulate the result.

• Formal Requirement: Inputs are non-malleable. A party cannot transform its input based on another's encrypted or shared input.
• Implementation: Often enforced through a commitment phase, where parties cryptographically bind to their inputs before the main computation begins.

If one party learns the output, then all honest parties learn the output. This prevents a scenario where a malicious party learns the result and then aborts the protocol, leaving others with nothing. Achieving perfect fairness is challenging and often depends on the adversary's power.

• Gradual Release: Some protocols use a gradual release mechanism, where the output is revealed piece-by-piece, making it disadvantageous for a party to abort early.
• Trade-offs: Perfect fairness against a majority of malicious parties is not always possible; many practical protocols offer fairness with abort, where the protocol either delivers output to all or aborts for all.

A stronger property than fairness, ensuring that honest parties always receive the computed output, regardless of the actions of malicious participants. This property is crucial for business-critical computations where an abort is not an acceptable outcome.

• Dependency on Honest Majority: Guaranteed output delivery typically requires an honest majority (e.g., less than one-third or one-half of parties are malicious).
• Resource Cost: Protocols providing this guarantee are often more communication-intensive than those offering fairness with abort.

A high-security framework ensuring that an MPC protocol remains secure even when run concurrently with other arbitrary protocols or multiple instances of itself. A universally composable (UC) protocol guarantees security in any computational environment.

• Real/Ideal Paradigm: Security is proven by showing that anything an adversary can do in the real protocol execution can be simulated in an ideal world where a trusted third party performs the computation.
• Practical Impact: UC-secure protocols can be safely used as modular building blocks in larger, complex systems without introducing new vulnerabilities.

A cryptographic protocol central to many general-purpose Secure Multi-Party Computation constructions. One party (the garbler) encrypts a Boolean circuit representing the function to be computed. The other party (the evaluator) can then compute the encrypted output using their private inputs without learning intermediate values.

• Two-Party Focus: A foundational technique for secure two-party computation.
• Process: Involves oblivious transfer for the evaluator to obtain input keys.
• Modern Use: Optimized variants like Yao's Garbled Circuits are used in privacy-preserving auctions, biometric matching, and genomic computations.

A specialized Secure Multi-Party Computation protocol that 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.

• Direct Application: Contact discovery in encrypted messaging apps, where a user finds which contacts are also app users without exposing their full contact list.
• Variants: Includes Cardinality PSI (learn only the size of the intersection) and Threshold PSI (learn if intersection size exceeds a threshold).
• Performance: Modern PSI protocols using oblivious transfer and cuckoo hashing can process millions of items in seconds.