# show that key recovery is not possible in a computationally secure system

(G, E, D) is a computationally secure encryption scheme over the message space $$\{0,1\}^n$$. Show that the probability that a PPT adversary can recover the key after seeing the encryption of a random (uniform distribution) message is negligible.

I want to show that if the attacker A has the ability to recover the key with non-negligible probability, e.g. 20%, it breaks semantic security, as A can guess much better $$f(M)$$ than a blind attacker A' that does not see the cipher.

BUT I'm stumped, as suppose $$f(M)$$ distribution is very skewed and the most frequent value occurs 30% of the time, the blind attacker A' can simply always guess that and beat A, thus not breaking semantic security...

Reminder - semantic security definition I'm using: $$Pr_K[A(E_K(M))=f(M)]\leq Pr_K[A'(1^n)=f(M)]+neg(n)$$

• Then, it is already not semantical security. You should assume that the blind has negligible advantage. Apr 12 at 18:39
• what do you mean @kelalaka ? the blind attacker currently has an advantage - it can guess with 30% and no attacker can guess better. Apr 12 at 18:46
• If the blind attacker has the non-negligible advantage then how the scheme can have semantical security? Apr 12 at 18:49
• @kelalaka - semantic security means that no attacker A that can see the cipher can guess better than the blind attacker A' that does not see the cipher. It does not have a non-negligible advantage, as the attacker A can also guess the most frequent value and they both will have 30% accuracy... Apr 12 at 18:53
• Try allowing $A$ a sensible guess in the event that they fail to recover the key. Apr 12 at 19:12