Secure Multi-Party Computation (SMPC)

Input privacy is the foundational guarantee of SMPC. Each party's private data remains encrypted or secret-shared throughout the computation. The protocol is designed so that no party learns anything about another's input beyond what can be inferred from the final output. This is formally proven using simulation-based security, which demonstrates that a party's view of the protocol execution can be simulated using only its own input and the final result, proving it gained no extra knowledge.

• Example: In a privacy-preserving salary analysis, each company submits its encrypted payroll. The SMPC protocol computes the industry average salary without revealing any individual company's figures.

Correctness ensures that the protocol computes the agreed-upon function accurately, even if some participants are malicious and attempt to deviate. The output must be identical to the result of applying the function to the plaintext inputs. This is enforced through cryptographic commitment schemes and verifiable secret sharing, which allow honest parties to detect and often abort in the face of cheating.

• Contrast with Trusted Third Parties: Unlike relying on a single trusted mediator, SMPC's correctness is guaranteed by distributed cryptographic mechanisms, eliminating the single point of failure and trust.

SMPC protocols are classified by their adversarial model, which defines the assumed power of corrupt participants. This determines the protocol's resilience and complexity.

• Semi-Honest (Passive): Adversaries follow the protocol but try to learn extra information from the transcript. Provides strong privacy with better performance.
• Malicious (Active): Adversaries can arbitrarily deviate from the protocol. Requires more complex zero-knowledge proofs and commitment rounds to enforce correctness, incurring higher overhead.
• Threshold Adversaries: Security is guaranteed as long as the number of corrupt parties is below a defined threshold (e.g., t-out-of-n).

Universal Composability (UC) is a strong security framework that guarantees an SMPC protocol remains secure even when run concurrently with arbitrary other protocols or multiple instances of itself. A UC-secure protocol acts like an ideal trusted functionality that receives inputs and returns outputs, with no insecure side-channels. This property is critical for deploying SMPC in complex, modular systems where protocols are composed.

• Importance: Without UC, a protocol proven secure in isolation might leak information when combined with others, a common pitfall in cryptographic design.

To overcome SMPC's traditional latency from multiple communication rounds, modern schemes use a preprocessing (or offline) phase. In this phase, parties generate correlated randomness (like multiplication triples) independently of their actual inputs. During the online phase, this precomputed material is consumed to compute the function with minimal interaction, often just a single round. This separates the communication-heavy cryptographic setup from the fast data-dependent computation.

• Benefit: Enables SMPC for real-time or latency-sensitive applications, such as private inference or real-time bidding.

SMPC protocols provide security guarantees based on different cryptographic assumptions:

• Information-Theoretic Security: Security holds even against an adversary with unlimited computational power. It relies on secrets being perfectly hidden by randomness, as in some secret-sharing schemes. However, it often requires strict conditions (e.g., honest majority) and secure point-to-point channels.
• Computational Security: Security holds under the assumption that certain cryptographic problems (like factoring large integers or solving discrete logs) are computationally hard. This allows for more efficient protocols and broader adversarial models (e.g., security against any number of corrupt parties), but is vulnerable to future advances in quantum computing or algorithm breakthroughs.

A form of encryption that allows specific types of computations to be performed directly on ciphertext, generating an encrypted result that, when decrypted, matches the result of operations performed on the plaintext. Unlike SMPC, which involves multiple parties, homomorphic encryption often involves a single data holder outsourcing computation to an untrusted server.

• Key Mechanism: Uses algebraic structures that preserve operations (addition, multiplication) under encryption.
• Primary Use Case: Enabling cloud services to process encrypted data without ever decrypting it, providing strong confidentiality guarantees against the cloud provider.
• Relation to SMPC: Can be used as a building block within certain SMPC protocols to perform computations on encrypted shares of data.

A decentralized machine learning approach where a global model is trained across multiple decentralized edge devices or servers holding local data samples, without exchanging the raw data itself. Instead, only model updates (e.g., gradients or weights) are shared with a central coordinator.

• Key Mechanism: Iterative training rounds where local models learn from local data, and their updates are aggregated to improve a global model.
• Privacy Consideration: While it avoids raw data exchange, shared gradients can sometimes be reverse-engineered to infer training data. Federated Learning is often combined with Differential Privacy or SMPC to strengthen privacy guarantees.
• Contrast with SMPC: SMPC computes a function on private inputs; Federated Learning trains a model on distributed data. Their goals (secure computation vs. decentralized training) are distinct but complementary.

A specific cryptographic protocol within the SMPC family where two or more parties, each holding a private set of items, can compute the intersection of their sets without revealing any information about items that are not in the intersection.

• Key Mechanism: Uses techniques like oblivious transfer, homomorphic encryption, or garbled circuits to compare encrypted representations of set elements.
• Real-World Example: A hospital and a research institute can identify common patients (the intersection) for a study without the hospital revealing its full patient list or the institute revealing its full candidate list.
• Application in Agentic Systems: Useful for agents from different organizations that need to discover shared context or overlapping knowledge bases without exposing their proprietary data stores.

A fundamental cryptographic primitive in which a sender transmits some of many pieces of information to a receiver, but remains "oblivious" as to which pieces have been transferred. It is a critical building block for many Secure Multi-Party Computation protocols, including garbled circuits.

• Core Principle: The receiver chooses which message to receive, and the sender learns nothing about that choice. The receiver learns nothing about the messages they did not choose.
• Analogy: A sender has two envelopes, only one contains the correct answer. The receiver picks one envelope to open, and the sender does not know which one was chosen.
• Role in SMPC: OT enables secure selection and transfer of data shares during multi-party computations, ensuring that parties cannot learn about inputs they are not authorized to access.

A powerful technique for implementing Secure Multi-Party Computation, allowing two parties to jointly evaluate a Boolean circuit (representing any function) without revealing their private inputs. One party "garbles" the circuit (encrypts its logic gates), and the other evaluates it using oblivious transfer to obtain the necessary decryption keys.

• Key Mechanism: The function to be computed is represented as a circuit of logic gates (AND, OR, XOR). Each gate's truth table is encrypted (garbled) so that evaluating it reveals only the output wire's encrypted label, not the underlying inputs.
• Performance Characteristic: Communication overhead is proportional to the size of the circuit, making it efficient for functions with compact circuit representations but less so for complex, data-intensive operations.
• Common Use: Often used in two-party computation scenarios, such as secure auctions or privacy-preserving biometric matching.

A method for distributing a secret (e.g., a private data value) among a group of participants, where each participant is allocated a share of the secret. The secret can only be reconstructed when a sufficient number of shares (the threshold) are combined; individual shares reveal no information about the secret.

• Foundational Scheme: Shamir's Secret Sharing, based on polynomial interpolation over a finite field.
• Core to SMPC: Most SMPC protocols use secret sharing as their foundation. Each party's private input is split into shares distributed among the other parties. Computations are then performed directly on these shares, and only the final result is reconstructed.
• Property: Provides information-theoretic security (security not based on computational hardness assumptions) when used correctly, making it exceptionally robust.