IND-CPA Security

The formal security definition is modeled as a game between a challenger and a probabilistic polynomial-time adversary.

• Setup: The challenger generates a key and provides the public key to the adversary.
• Challenge: The adversary submits two equal-length plaintexts, m0 and m1.
• Encryption: The challenger randomly selects a bit b and returns the encryption of mb.
• Guess: The adversary must determine b. A scheme is IND-CPA secure if the adversary's advantage over a random guess is negligible.

A fundamental requirement for IND-CPA security is that encryption must be non-deterministic. Encrypting the same plaintext multiple times must produce distinct ciphertexts.

• Randomized Padding: Schemes like OAEP add random bits before encryption.
• Initialization Vectors (IVs): A unique, random nonce ensures semantic security.
• HE Realization: Lattice-based HE schemes inherently achieve this by adding a fresh, random noise component during encryption. Without this, an adversary could trivially win the game by comparing ciphertexts.

IND-CPA security explicitly does not guarantee non-malleability. Homomorphic encryption is, by design, malleable.

• Definition: A scheme is malleable if an adversary can transform a ciphertext c (encrypting m) into a new ciphertext c' (encrypting f(m)) without knowing m.
• HE Context: This is a feature, not a bug. It enables computation on encrypted data.
• Implication: IND-CPA guarantees input privacy but not output integrity. An adversary can blindly modify an encrypted result. Circuit privacy or verifiable computation is required to detect such tampering.

IND-CPA provides security only against a passive adversary (eavesdropper). It offers zero protection against active attacks.

• Chosen-Ciphertext Attack (CCA): An adversary with a decryption oracle can break IND-CPA schemes. They can submit manipulated ciphertexts and observe the decrypted results to extract information.
• Real-World Risk: In cloud-based HE inference, a malicious client could send crafted ciphertexts to probe the model.
• Mitigation: For active security, one must upgrade to IND-CCA1 or IND-CCA2 secure schemes, though these are fundamentally incompatible with standard homomorphic operations.

Modern HE schemes achieve IND-CPA security by relying on the hardness of the Learning With Errors (LWE) or Ring-LWE problems.

• Mechanism: A ciphertext is a pair (a, b) where b = <a, s> + m + e. The secret key s is a vector, m is the encoded plaintext, and e is a small random noise term.
• Security Reduction: Distinguishing this from a random pair (a, u) is exactly the LWE problem. The noise e provides the probabilistic property.
• Quantum Resistance: This construction is believed to be secure against both classical and quantum adversaries, making it a post-quantum standard.

A critical operational constraint of IND-CPA is the prohibition on key reuse across distinct protocol sessions.

• Symmetric HE: Some schemes use a single secret key for encryption and decryption. Reusing this key for multiple independent data streams can leak relationships.
• Hybrid Encryption: In practice, a standard IND-CPA public-key scheme (like RSA-OAEP) encrypts a one-time symmetric key, which then encrypts the bulk data.
• HE Best Practice: Always generate fresh encryption randomness for each message. For multi-party HE, use distributed key generation protocols to avoid a single point of failure.

Indistinguishability under Adaptive Chosen-Ciphertext Attack is a strictly stronger security notion than IND-CPA. While IND-CPA protects against passive eavesdroppers, IND-CCA2 guarantees security even against adversaries who can submit arbitrary ciphertexts for decryption and adapt their attacks based on the results.

• Key Difference: IND-CCA2 allows the attacker access to a decryption oracle before and after seeing the challenge ciphertext
• Relevance to HE: Standard homomorphic encryption schemes are malleable by design and therefore cannot achieve IND-CCA2 security
• Practical Implication: Systems using HE must implement additional integrity checks at the application layer to prevent ciphertext manipulation attacks

Semantic security is the formal definition that captures the intuitive notion that a ciphertext reveals no partial information about the plaintext. IND-CPA is the game-based formulation proven equivalent to semantic security.

• Goldwasser-Micali 1984: Introduced the concept and proved equivalence to polynomial indistinguishability
• Core Guarantee: An adversary with any a priori knowledge about the plaintext gains no computational advantage after observing the ciphertext
• Practical Meaning: Even if an attacker knows the plaintext is either 'BUY' or 'SELL', the ciphertext provides no statistical advantage in guessing which one

Circuit privacy extends the IND-CPA guarantee to the homomorphic evaluation process itself. While IND-CPA ensures the input ciphertexts reveal nothing about the plaintexts, circuit privacy ensures the evaluated ciphertext reveals nothing about the function that was computed.

• Critical for ML: Protects proprietary model architectures during encrypted inference
• Achieved via noise flooding: Adding large statistical noise after evaluation to mask the computational path
• Trade-off: Circuit privacy significantly increases the noise budget consumption, requiring larger parameters or more frequent bootstrapping

Malleability is the property that allows ciphertexts to be meaningfully transformed without decryption—the very feature that enables homomorphic computation. It is also the reason HE schemes cannot achieve IND-CCA2 security.

• Controlled Malleability: HE schemes permit only specific algebraic transformations that preserve the underlying structure
• Double-Edged Sword: Enables private computation but requires application-layer integrity protections
• Mitigation: Use of zero-knowledge proofs or message authentication codes layered on top of HE ciphertexts to detect unauthorized modifications

The CPA model assumes an adversary can encrypt arbitrary plaintexts of their choosing using the public key. This models real-world scenarios where attackers have access to the encryption functionality.

• Realistic Threat: In public-key systems, anyone can encrypt; the CPA model captures this capability
• Encryption Oracle: The attacker can query the encryption function adaptively, choosing each plaintext based on previous ciphertexts
• Beyond Passive: While CPA is stronger than ciphertext-only attacks, it still assumes the attacker cannot request decryptions—a limitation addressed by CCA models

Left-or-Right (LOR) indistinguishability is an alternative game-based formulation equivalent to IND-CPA. The adversary submits pairs of plaintexts and receives encryptions of either all left-side or all right-side values, and must determine which.

• Equivalent to IND-CPA: LOR security implies and is implied by standard IND-CPA
• Multi-Message Security: LOR formulations naturally extend to proving security when multiple messages are encrypted under the same key
• Relevance: Guarantees that encrypting an entire database row-by-row with the same key remains semantically secure