Which categories of cipher are semantically secure under a chosen-plaintext attack?

Question

I am trying to get my head around the circumstances under which a cipher is (or is not) semantically secure under a chosen-plaintext attack.

I can't seem to find a good reference explaining this.

I think I am missing a fundamental concept, so If I explain it as I see it perhaps someone can correct me.

Semantic security means that the adversary cannot learn anything about the plaintext from the ciphertext (except for the length of the message which is known beforehand).

I.e. the message is entirely indistinguishable from random bits.

So it seems to me that if a stream cipher is using a true PRG, it's output will always be indistinguishable from random, a chosen plaintext attack will not assist the adversary.

However if the encryption is deterministic then a chosen plaintext attack will reveal "information" about messages, as the ciphertexts can be compared to one another.

Am I missing something?

Answer 1

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks.

To prevent this an initialisation vector or nonce can be used in combination with a cryptographic mode such as cipher block chaining or randomised counter mode which will prevent the encryption from being deterministic and allowing the comparison of ciphertexts.

Answer 2

To be secure against a chosen-plaintext attack, an encryption scheme must be non-deterministic — that is, its output must include a random element, so that e.g. encrypting the same plaintext twice will result in two different ciphertexts.

Indeed, if that was not the case, an attacker could easily win the IND-CPA game just by using the encryption oracle to encrypt the challenge ciphertexts in advance, and then comparing the response to the challenge with the ciphertexts obtained from the oracle.

Now, the usual way in which this non-determinism is achieved is by choosing a random "tweak" or "IV" of sufficient length (say, 128 bits), combining it somehow with the key to change the way the plaintext is encrypted, and then including it as part of the ciphertext. That way, it's as if every plaintext was encrypted with a different, random key, and there are so many possible effective keys that it's basically impossible for any of them to ever be used twice.

Of course, the tweak or IV itself need not be truly random; it only needs to be indistinguishable from random by any plausible attacker. For example, the output of a cryptographically secure pseudorandom number generator (which is pretty much the same thing as a stream cipher) seeded with a truly random number (or, again, something indistinguishable from it) will do just fine.