0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One possibility is that the professor was trying to motivate the notion that encryption can be randomized while decryption is deterministic. So for the same message $m$ and key $k$, by using randomness, e.g. a salt, you would generate two different ciphertexts $c_1$ and $c_2$ in successive encryptions. In an ideal implementation, relation (2) would then hold against the adversary. $\endgroup$ – jayann Sep 15 '14 at 9:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, thanks. This is what I was thinking but couldn't put it formally. I voted your answer as the correct one. $\endgroup$ – gogogogo Sep 16 '14 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.