Secure Multi-Party Computation (SMPC)

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 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.