# Security of Randomized Encryption Scheme

I have the following question which I'm struggling with

Suppose we are interested in encrypting bit strings. Consider a randomized encryption scheme that always produces ciphertexts of the same length as the plaintexts.

Show that this scheme cannot be IND-CPA secure

Intuitively to me this kind of scheme shouldn't even be decryptable if the randomness lies in the mapping between plaintexts and ciphertexts. How can a single plaintext map to multiple ciphertexts (of the same length) without avoiding collisions and whilst also being decryptable? Am I misunderstanding what it means for an encryption scheme to be "randomized"?

I remember seeing a rough solution once which used the idea of mapping plaintexts to sets of ciphertexts but can't see how that would work / solve the problem.

• Hint: by a counting argument, show that any encryption scheme with a working decryption procedure that always produces ciphertext of the same length as the plaintext, is bound to always produce the same ciphertext for a given plaintext; hence can only be said randomized by a far stretch of imagination, and is not IND-CPA secure.
– fgrieu
Jan 13, 2017 at 10:50
• @fgrieu Maybe I'm very dense on this topic, but do we assume here that the randomization is part of the ciphertext and not communicated out of band? Jan 17, 2017 at 1:03
• @Maarten Bodewes: yes, I believe that in this question the randomization (e.g. IV) is assumed part of the ciphertext (a standard assumption in modern expositions, like Katz & Lindell), rather than out-of-band. Otherwise, what's asked would amount to: prove that no cipher with only constant expansion is IND-CPA secure [reposted with disambiguation]
– fgrieu
Jan 17, 2017 at 16:05

Ciphertext Indistinguishability means that if you encrypt a message many times, each time the ciphertexts must be different.

For example, think about a device that searches flaws in a dam. Every time, when this device traverses, it will send "Yes" or "No" signals that it means for a receiver that the device has found a flaw or not. If an eavesdropper sniffs these signals, because of the number of "no" signals are more Than "yes" signals, he could understand the meaning of these signals even though they are encrypted and could not break their encryption. This weakness happens because the encryption algorithm is DETERMINISTIC and it means that always it produces same encryptions for "YES" signal and same encryptions for "NO" signals, in other words, the attacker could distinguish these encrypted messages without knowing the nature of the encryptions.

The solution for making messages resistance against distinguishability is using Non-Deterministic encryption and use parameters like IV and so for make ciphertext Random and each time giving the same message, it produces different ciphertexts and the attacker could not distinguish them.

Lets assume first that the bit string can have any value. This is not explicit from the question, but it does't make any other claims about the contents either, so we have to assume this is the case.

Furthermore, let's assume that no out of band communication can exist. That means that, for instance, that no state can be kept. In other words, we cannot use a counter on both sides to create indistinguishability.

The ciphertext needs to be the same size as the plaintext. That means that the number of plaintext messages and ciphertext messages are equal: both are limited to $2^n$ where $n$ is the number of bits. Each plaintext message will therefore be mapped to exactly one ciphertext message; if this isn't the case then some plaintext messages are impossible to encrypt/decrypt.

This in turn means that an adversary can see identical messages because each message will be mapped to the same ciphertext message. This means that information about the messages is leaked: identical messages can be distinguished and conversely it is also possible to see that no identical messages are send.

To change the mapping we need to add state, as both the encryption and decryption will have to change the mapping in the same way. We cannot use any of the bits of the ciphertext, because if we re-assign one of the bits or even one pattern then some plaintext messages cannot be reached anymore by the mapping.

This means that the encryption / decryption needs to be deterministic; there is no way to add information to the ciphertext message that can be used on both sides to generate a different ciphertext / plaintext message given identical input.

The pseudo random 1:1 mapping of plaintext and ciphertext is called a permutation. Block ciphers are permutations for a specific value of $n$: the block size.

From this question you can see that ECB mode cannot be IND_CPA secure: information is leaked already when you encrypt the second block. If the second plaintext block is identical to the first one then the second ciphertext block will be identical to the first ciphertext block. So you can find any identical sets of blocks, or you can identify that there aren't any, which of course also leaks information.

Hence you require a mode of operation to make a block cipher IND_CPA secure.

• Added this answer because I think that the answer of Arsalan doesn't explain why the messages need to be deterministic, which is what was asked. It does a fine job explaining the consequences and how to void messages being deterministic, but that is not what was asked IMHO. Aug 22, 2018 at 14:11