Security Models and Proof Strategies for Plaintext-Aware Encryption

This paper presents, extends, and corrects errors in [12] and [8].

The original version of this result [8] claimed that plaintext awareness with respect to a single plaintext creator \(\mathcal {P}_{I}\), which chooses a random bit b and then consistently outputs m _b when given α=(m ₀,m ₁), was sufficient to prove IND-CCA2 security. We called this property PA2I plaintext awareness. Sadly, this result is not correct. We will sketch a counter-example here. Suppose \(\varPi=(\mathcal {G},\mathcal {E},\mathcal {D})\) is IND-CCA2 secure and PA2I plaintext aware. Let \(\varPi'=(\mathcal {G},\mathcal {E}',\mathcal {D}')\) be the encryption scheme with \(\mathcal {E}'(\mathit {pk},m)=0\|\mathcal {E}(\mathit {pk},m)\) and \(\mathcal {D}'(\mathit {sk},\delta \|C)=\mathcal {D}(\mathit {sk},C)\) for any δ∈{0,1}. This scheme is IND-CPA secure but not IND-CCA2 secure. We claim that this scheme is still PA2I plaintext aware. We may build a plaintext extractor \(\mathcal {A}^{*}\) for a ciphertext creator \(\mathcal {A}\) working against Π′ by noting two properties of the scheme. (a) Since Π is PA2I there exists a plaintext extractor which can decrypt all decryption queries of the form δ∥C where 0∥C∉CList. (b) If \(\mathcal {A}\) requests the decryption of 1∥C where 0∥C∈CList then the correct response must be either m ₀ or m ₁, which can be determined by observing the original encryption oracle query. Furthermore, since Π is IND-CCA2 secure, no algorithm can distinguish between the case where \(\mathcal {A}^{*}\) returns the correct decryption of 1∥C and the case where \(\mathcal {A}^{*}\) returns the message m _d (for some value d which was randomly chosen by \(\mathcal {A}^{*}\) during its first execution). Thus Π′ is IND-CPA secure and PA2I plaintext aware, but not IND-CCA2 secure, which contradicts the claimed result of [8].

This is also sometimes known as the Knowledge-of-Exponent assumption (KEA).

A smooth hash function has the property that the distribution of H(x), for \(x\stackrel {{\hspace {1pt}\scriptscriptstyle \$}}{\gets }\mathbb {G}\), is computationally indistinguishable from the uniform distribution on \(\mathcal {K}\)

The original proof that the Cramer–Shoup encryption scheme is simulatable [12] has a (minor) flaw. The proof does not “reset” the decryption oracle to its correct operation at the end of proof. This presentation sidesteps the issue by using a simplified proof.

The original proof of this result claimed that it was sufficient for the group \(\mathbb {G}\) to be computationally simulatable. This is incorrect: we require that the group \(\mathbb {G}\) is statistically simulatable. This error is relatively minor in practice as all the common groups which are used for cryptography are statistically simulatable (see Sect. 7.1). The original proof also failed to deal effectively with the differences in the way that the DHK extractor \(\mathcal {B}^{*}\) and the PA1+ plaintext extractor \(\mathcal {A}^{*}\) handle the random inputs of their respective underlying algorithms \(\mathcal {B}\) and \(\mathcal {A}\). The DHK extractor \(\mathcal {B}^{*}\) requires all random bits of \(\mathcal {B}\) to be known in advance, while the PA1+ extractor \(\mathcal {A}^{*}\) must allow for the possibility that fresh random bits will be generated by \(\mathcal {A}\) after \(\mathcal {A}^{*}\)’s execution.