In their book Introduction to Modern Cryptography, chapter 2, authors Katz and Lindell ask the reader to show that perfect secrecy is equivalent to adversarial indistinguishability as an exercise. I am self-studying their book, and I tried tackling the proof on my own.

I succeeded in showing that adversarial indistinguishability implies perfect secrecy by using Lemma 2.4 from the book and constructing a probabilistic adversary with advantage $\neq 1/2$.

I could not figure out how to rigorously prove the other direction, so I googled a solution. This pdf gives a proof of both directions. Rosenberg's proof that adversarial indistinguishability implies perfect secrecy is essentially the same as mine (although he appears to have left out quite some details), but his argument for showing that perfect secrecy implies adversarial indistinguishability is too shallow for me to fully understand it, although it is undoubtedly sound.

Rosenberg says "We can consider the adversary is deterministic, because there is no gain to randomizing its guesses" (sic). Using this assumption, I managed to rigorously show that perfect secrecy implies adversarial indistinguishability, this appears easier than showing the converse like Rosenberg does. But how is this assumption justified? The proof I worked out after reading Rosenberg's notes critically depends on the deterministic behaviour of adversaries, but his justification, "(...) there is no gain to randomizing its guesses," mystifies me.

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Law_of_total_probability ​ ​ $\endgroup$ – user991 Oct 20 '16 at 16:37
  • 1
    $\begingroup$ Let $A(r)$ denote the behavior of a probabilistic adversary $A$ when its random coins are fixed to $r$. So each $A(r)$ is a deterministic adversary. Now if $A$ is a good adversary on average, it means $\Pr_r[A(r) \mbox{ succeeds}] > \epsilon$. But then there must be some fixed $r^*$ for which $A(r^*)$ succeeds with probability at least $\epsilon$. So an adversary might as well just run deterministic strategy $A(r^*)$. $\endgroup$ – Mikero Oct 20 '16 at 17:42
  • $\begingroup$ @Mikero I get it, thank you. Clearly, I should read up on randomized algorithms before I move on. $\endgroup$ – DiscobarMolokai Oct 21 '16 at 9:13

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.