CPA

Overview

Chosen Plaintext Attack (CPA) security is the baseline security notion for encryption schemes. It captures the requirement that an adversary who can choose plaintexts and observe their encryptions should not be able to distinguish which of two chosen messages was encrypted in a challenge ciphertext.

CPA was originally called “polynomial security” by Goldwasser and Micali. It has been shown to be equivalent to semantic security [Goldwasser, Micali (1984); Watanabe, Shikata, Imai (2003)]. The motivation is straightforward: since a public-key adversary can always encrypt messages of their choice, the scheme must remain secure even under this capability. In the context of FHE, CPA security is the default assumption for most constructions, as homomorphic evaluation does not inherently require stronger guarantees.

A classical result from Bellare, Desai, Jokipii, and Rogaway (FOCS 1997) establishes that the single-challenge (Find-Then-Guess) and multiple-challenge (Left-or-Right) variants of IND-CPA are equivalent.

Formal Definition

The IND-CPA security game proceeds as follows:

1. The challenger generates a key pair and gives to the adversary .
2. may encrypt any message of its choice using . In the public-key setting, the adversary implicitly has access to an encryption oracle since it holds . In the private-key setting, an explicit encryption oracle is provided.
3. outputs two equal-length messages .
4. The challenger samples a bit , computes , and sends to .
5. outputs a guess .

The advantage is defined as:

The scheme is IND-CPA secure if this advantage is negligible for all PPT adversaries.

Attacks & Relevance

CPA security prevents any passive eavesdropper from extracting information about the plaintext from the ciphertext. It rules out deterministic encryption and any scheme where the ciphertext leaks partial information about the message.

Most lattice-based FHE schemes (BGV, BFV, CKKS, TFHE) are proven secure under IND-CPA, relying on the hardness of (Ring-)LWE or related problems.

However, CPA alone does not protect against active adversaries who may tamper with ciphertexts. Since homomorphic evaluation inherently modifies ciphertexts, CPA security says nothing about the integrity or correctness of computed results.

Achieving This Notion

CPA security is achieved by essentially all modern public-key encryption schemes. For FHE specifically, the standard constructions based on LWE or RLWE assumptions all satisfy IND-CPA.

Further Reading

The equivalence between semantic security and indistinguishability was established by Goldwasser and Micali (1984). For a textbook treatment of CPA and its place in the hierarchy of security notions, see Katz and Lindell, Introduction to Modern Cryptography. In the FHE setting, Gentry (2009) established CPA as the baseline security target, a convention that has persisted throughout subsequent generations of FHE schemes.