Shannon theorem of perfect secrecy

Question

From the class:

Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability).

Proof:
Consider ciphertext $c$. $c$ must be a possible encryption of any plaintext $m$. But, for this we need a different key per message $m$. $m \neq m' \iff c \neq c' $. Why?

Can someone explain the logic behind the proof? I understand that the one above is a partial one but still can I have an easy to understand explanation? No need a formal one.

$c$ must be a possible encryption of any plaintext $m$.

I understand that.

But, for this we need a different key per message $m$.

Why? I can have the same key for different messages and still produce different ciphers, and those ciphers would be " a possible encryption of any plaintext m ".

$m \neq m' \iff c \neq c'$ Why?

Didn't understand that either, could have different messages but same ciphers. But if we indeed force that each message has it's own unique key then it is true, and then we showed that size of keys space > size of messages space.

Answer 1

If $c$ is a possible encryption for each $m \in M$, that means that for each message $m$ exists a key $k$ such that $Enc_k(m)=c$. Now, if you encrypt, you need to be able to decrypt. Since $c$ is fixed, the only variable for $Dec_k(c)=m$ is $k$. Since you need to be able to use the decryption process to get any value of $m$, that means that you have $|M|$ values of $k$.

In other words, you need to be able to go from the any value in the message space to any value in the ciphertext space (encrypt) and from any value in the ciphertext space to any value in the message space (decrypt), and for that you need $|M|=|C|$ keys.

Answer 2

The statement "But, for this we need a different key per message m" implies a different key for each fixed message, that's what "per message" is intended to mean. So the number of keys must be at least the number of messages.