# The number of cipher texts possible for each plaintext

This is from Dan Boneh's book

Theorem 2.1. Let X = (E, D) be a Shannon cipher defined over (K, M, C). The following are equivalent:

(i) X is perfectly secure.

(ii) For every $$c \in C$$, there exists $$N_c$$ (possibly depending on c) such that for all $$m \in M$$, we have

$$|\{k \in K : E(k, m) = c\}| = N_c$$

(iii) If the random variable k is uniformly distributed over K, then each of the random variables E(k, m), for $$m \in M$$, has the same distribution.

Proof:

For every $$c \in C$$, there exists a number $$P_c$$ (depending on c) such that for all $$m \in M$$, we have Pr[E(k, m) = c] = $$P_c$$. Here, k is a random variable uniformly distributed over K. Note that $$P_c = N_c/|K|, where N_c$$ is as in the original statement of (ii)

(Partially copied, not the full thing)

Point (ii) is not clear to me. What exactly is $$N_c$$? If is the number of ciphertexts possible for each plaintext, then it's always equal to 0 or 1 for perfect secrecy, right. Or can it be something else?

What exactly is $$N_c$$?
For perfectly secret schemes with $$|K|=|M|$$ this will always be either 1 or 0. It could be 0 e.g. if the ciphertext is longer than anything in the message space for a OTP.
• @user93353 One can e.g. modify the OTP to lead with 10 unused keybits and agree that there will always be 10 of them at the start and they're simply ignored on decryption. This gives you either 0 or $2^{10}$ (instead of 1) as the Nc. – SEJPM Nov 2 '20 at 11:25