(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)$

  • $\begingroup$ Then, it is already not semantical security. You should assume that the blind has negligible advantage. $\endgroup$ – kelalaka Apr 12 at 18:39
  • $\begingroup$ what do you mean @kelalaka ? the blind attacker currently has an advantage - it can guess with 30% and no attacker can guess better. $\endgroup$ – ihadanny Apr 12 at 18:46
  • $\begingroup$ If the blind attacker has the non-negligible advantage then how the scheme can have semantical security? $\endgroup$ – kelalaka Apr 12 at 18:49
  • $\begingroup$ @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... $\endgroup$ – ihadanny Apr 12 at 18:53
  • $\begingroup$ Try allowing $A$ a sensible guess in the event that they fail to recover the key. $\endgroup$ – Daniel Shiu Apr 12 at 19:12

Your Answer

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

Browse other questions tagged or ask your own question.