Malicious Security

The baseline threat model where all parties follow the protocol specification correctly but may attempt to learn additional information from the protocol transcript. Also known as honest-but-curious or passive security.

• Adversary behavior: Passive observation only; no deviation from the protocol
• Efficiency: Significantly faster than malicious security (often 2-10x)
• Real-world risk: Fails completely if a party is compromised and sends malformed messages
• Use case: Suitable when all parties are audited or trusted to execute code as written

Most efficient PSI protocols (e.g., KKRT) are initially designed in this model before being upgraded with malicious countermeasures.

A cryptographic protocol enabling secure two-party computation of any Boolean function. One party garbles the circuit by encrypting each gate's truth table; the other party evaluates it obliviously using encrypted inputs.

• Role in malicious security: Requires additional mechanisms like cut-and-choose to prevent garbler cheating
• Cut-and-choose overhead: Typically 3-40x more circuits must be generated and checked
• Authenticated garbling: Modern approach using BMR-style protocols to achieve malicious security more efficiently
• Key limitation: High communication cost for complex functions compared to vector OLE-based approaches

Garbled circuits provide the theoretical foundation for general-purpose maliciously secure computation.

Cryptographic protocols allowing a prover to convince a verifier that a computation was performed correctly without revealing the inputs or model weights. Essential for adding malicious security to ML inference.

• zkSNARKs: Succinct proofs with constant-size verification; require trusted setup
• zkSTARKs: Transparent setup with no trusted ceremony; larger proof sizes but post-quantum secure
• Application: Proving that an inference result is correct without exposing the proprietary model
• Performance: Modern proving systems (e.g., Plonky2, Halo2) achieve sub-second proof generation for modest neural networks

Zero-knowledge proofs transform semi-honest ML protocols into verifiably correct, maliciously secure systems.

A fundamental cryptographic primitive that binds a party to a chosen value while keeping it hidden from other parties until a later reveal phase. Critical for enforcing honest behavior in malicious security.

• Hiding property: The commitment reveals nothing about the committed value
• Binding property: The committer cannot change the value after committing
• Pedersen commitments: Additively homomorphic; widely used in maliciously secure MPC
• Use in PSI: Parties commit to their input sets before the protocol begins, then prove consistency with those commitments throughout execution

Commitment schemes prevent adaptive cheating where an adversary tries to modify inputs based on observed protocol messages.

The gold-standard methodology for formally proving security of cryptographic protocols. Demonstrates that any attack in the real world corresponds to an attack in an idealized world where a trusted third party performs the computation.

• Ideal world: A trusted party receives inputs, computes the function, and returns outputs
• Simulator: Constructs a transcript indistinguishable from the real protocol execution using only the ideal-world outputs
• Malicious security proof: The simulator must extract the adversary's effective input even when they deviate arbitrarily
• UC security: Universal Composability ensures security holds even when the protocol runs alongside other protocols

A protocol without a simulation-based proof should not be considered maliciously secure, regardless of heuristic defenses.

Mechanisms that verify a party's behavior is consistent across multiple protocol rounds and matches their committed inputs. The primary tool for detecting malicious deviation.

• Linear consistency: Verifying that a party uses the same input across multiple OT or OPRF instances
• Batch verification: Amortizing the cost of checking many consistency proofs into a single efficient verification
• Cut-and-choose: Randomly sampling a subset of garbled circuits for correctness verification
• MAC-based approaches: Using information-theoretic message authentication codes to detect tampering with intermediate values

Modern maliciously secure protocols (e.g., SPDZ-family) use MACs to achieve consistency with minimal overhead compared to older cut-and-choose techniques.