15.1.4 Plaintext integrity

In terms of the integrity of symmetric encryption schemes, the notion of plaintext integrity requires an encryption scheme to be designed in such a way that no algorithm running in polynomial time is able to produce a ciphertext that decrypts to a valid message that the sender has never encrypted [18].

In more formal terms, the notion of plaintext integrity is expressed using a game similar to those we previously used for CPA-secure and CCA-secure definitions. The INT-PTX game is as follows:

1. Owen generates a random secret key k.
2. Eve can ask Owen to compute the ciphertext for any plaintext m of her choice. While doing this, Owen adds m to the set of plaintexts ℳ that Eve asked him to encrypt.
3. Next, Eve must generate the challenge ciphertext c that decrypts to a valid plaintext message mi and give c to Owen.
4. Owen verifies that c decrypts to a valid message mi and miℳ. If this is the case, we say that Eve succeeds.

We say that a secret key encryption scheme provides plaintext integrity, also referred to as INT-PTX, if Eve succeeds in the above game with a probability p that is negligible in the encryption scheme’s security parameter n, that is:

In other words, the probability that Eve can generate a ciphertext that decrypts to a valid plaintext message is negligibly small even if Eve has the ability to encrypt any number of chosen plaintexts before she generates the challenge ciphertext c.

As a result, an INT-PTX encryption scheme ensures that Eve won’t be able to generate a ciphertext that decrypts to some valid plaintext even if she observed an (arbitrary) large number of encryptions.

15.1.5 Ciphertext integrity

The notion of ciphertext integrity requires an encryption scheme to be designed in such a way that no efficient algorithm can compute a valid ciphertext that was not previously produced by the sender, regardless of whether the underlying plaintext is new [18]. Here, valid refers to any ciphertext that corresponds to some meaningful plaintext.

The game used to formalize the notion of ciphertext integrity is almost identical to that of plaintext integrity. The only difference is instead of memorizing the plaintext messages he was asked to encrypt, this time Owen memorizes the ciphertexts returned to Eve upon her queries. So, the INT-CTX game is defined as follows:

1. Owen generates a random secret key k.
2. Eve can ask Owen to compute the ciphertext c′ = ek(m′) for any plaintext m′ of her choice. After each such calculation, before giving c′ to Eve, Owen adds c′ to the set of ciphertexts 𝒞 that correspond to the plaintexts Eve asked him to encrypt.
3. Next, Eve must generate the challenge ciphertext c that decrypts to a valid plaintext message m and give c to Owen.
4. Owen verifies that c decrypts to a valid message m and c𝒞, in which case we say that Eve succeeds.

Similar to INT-PTX, we say that a secret key encryption scheme provides ciphertext integrity (INT-CTX) if Eve succeeds in the above game with probability p that is negligible in the security parameter n:

This inequality is just another way of saying that it is practically infeasible for Eve to generate new valid ciphertexts even if she has access to an encryption oracle. More precisely, an INT-CTX encryption scheme guarantees that Eve – or, equivalently, any polynomial time algorithm – cannot generate a ciphertext corresponding to a meaningful plaintext if neither Bob nor Alice has computed that ciphertext before, even if Eve is allowed to observe an (arbitrary) large number of encryptions for plaintexts of her choice.

We will now take a look at three traditional ways to achieve confidentiality and authenticity and how they fare in terms of the security notions we just introduced.