Definition of perfect secrecy using ciphertext

Question

This week my professor in class taught us the definition of perfect secrecy. He said that for any ciphertext the probability that it might have come from any message in the message space should be equal.

$\Pr_{k\leftarrow Gen}[Enc_k(m)=c]=\Pr_{k\leftarrow Gen}[Enc_k(m')=c]$

He then said to think of the possibility where we vary the ciphertext and not the message. I think what he said might be interpreted as that the probability that a message encrypts into a ciphertext should be equal for all ciphertexts.

$\Pr_{k\leftarrow Gen}[Enc_k(m)=c]=\Pr_{k\leftarrow Gen}[Enc_k(m)=c']$

I thought about this but haven't been able to relate it to the original definition. I wanted to prove the equivalence or get a better inference of what he said. I don't know if this is even true. So a counterexample might be more useful.

If I haven't written any detail please let me know.

Answer 1

I think they are similar but not equivalent.

The first condition says that for any ciphertext $c$ all messages $m$ have equal probability to encrypt to $c$. The second says that for any message $m$ all ciphertexts $c$ have equally probability of encrypting $m$.

So I think you can demonstrate non-equivalence as follows:

Imagine a (somewhat contrived) scheme satisfying the first condition but not the second: The scheme has two disjointed sets of ciphertexts $C_0$ and $C_1$. Concretely, consider one-time-pad where keys and ciphertext contain one extra bit, simply indicating if we are in $C_0$ or $C_1$. Now, assume we pick the extra bit to be 0 with probability 1/3 and 1 with probability 2/3.

Now if $c \in C_0$ and $c' \in C_1$ it is clearly not the case that $$ Pr_{k \leftarrow Gen}[Enc_k(m) = c] = Pr_{k \leftarrow Gen}[Enc_k(m) = c'] $$ because the probability that $Enc_k(m) \in C_1$ is twice as big as $Enc_k(m) \in C_0$.

Alternatively, I think you can show that condition two implies condition one. I.e. condition one is more general than condition two.