Theorem 2.6 from the lecture

Theorem 2.6 from the lecture

Hila Chefer 01 Nov 2019 11:07

Hi,

In theorem 2.6 we proved that any perfect cipher holds: n>=l, but in the proof we have not clarified which definition is contradicted if n<l.
Seems pretty intuitive to me that it isn't a perfect cipher since the cipher "adds knowledge" in the form of a higher probability to guess the message using E.
Is this a good enough explanation or do we always have to show a contradiction to one of the definitions?
If so, it seems to me that the third definition may be the most convenient one to show the contradiction since if M is the uniform distribution, then I think that the inequality that we've shown is enough to contradict the definition (2^-l != 2^-n), is this a good explanation?

Thanks!

Re: Theorem 2.6 from the lecture

nbitansky 01 Nov 2019 19:11

Right, it follows quite directly from the third definition.

Re: Theorem 2.6 from the lecture

Hila Chefer 03 Nov 2019 18:08

Thanks.
Also, I think that this proof does not hold if E is not deterministic since in that case guessing the key isn't enough (since the adversary does not know the random vector that was selected), right?
If so, is there a proof for the non-deterministic case that we can read? If the same proof still holds, could you explain why?

Thanks again.

Re: Theorem 2.6 from the lecture

nbitansky 03 Nov 2019 18:47

Decryption only requires the secret key and not the randomness that was used to encrypt (otherwise, thinking about randomized encryption is meaningless, think why…).