The definition of adversary's advantage seems a bit odd for me and I am wondering why do we use it to measure the power of an adversary rather than just use the probability of a PPT adversary succeeding in answering an computationally hard question?

  • $\begingroup$ Could you please write out the PPL acronym? Currently looking for "PPL cryoptography" cycles right back to this forum in Google (which is impressive, but not too useful :) ). $\endgroup$
    – Maarten Bodewes
    Oct 6, 2013 at 11:42
  • $\begingroup$ Probabilistic Polynomial Time adversary... sorry i misspelled it $\endgroup$
    – Boyu Fang
    Oct 6, 2013 at 11:53
  • $\begingroup$ Google's cache refresh for Stack Exchange is impressive. I wonder if we're getting special love from Google or our site is simply that popular to warrant a fast cache refresh? $\endgroup$ Oct 6, 2013 at 12:16
  • $\begingroup$ very impressive about the google thing $\endgroup$
    – Boyu Fang
    Oct 6, 2013 at 12:48
  • $\begingroup$ @LateralFractal I'd guess having a site-index (which tells google what has changed) and being popular are the most important factors. $\endgroup$ Oct 6, 2013 at 13:09

1 Answer 1


We begin with the probability $p$ of an adversary answering correctly.

For many problems in cryptography, such as factoring or computing discrete logarithms, finding a secret key or decrypting a plaintext, this is useful measure of how good the adversary is. If we have an adversary that can compute discrete logarithms with significant probability, that is obviously a problem.

But sometimes, we want a stronger statement than simply "the adversary is unable to decrypt". Instead, we want to be able to say something stronger, e.g. that the adversary cannot determine even a single bit of information about the decryption.

Now, I can guess the value of a bit with probability $p = 1/2$, which is significantly larger than $0$. Which means that the probability $p$ of answering correctly is not a useful measure of my power.

We could say that I should be able to guess correctly more often than half the time, in which case $p-1/2$ might be a sensible measure. But if I somehow always end up guessing wrong, so that the probability $p$ of me answering correctly is $0$, then essentially I know what the bit of information is. Reliably answering wrong is essentially as good as always answering correctly.

So we take absolute value, and arrive at the usual definition of advantage being $|p-1/2|$.

  • $\begingroup$ so in some situation we use the advantage rather the success probability of an adversary to argue that it cannot break the scheme with a probability better than flipping a coin. That's how we define security in some case. Is my understanding right? $\endgroup$
    – Boyu Fang
    Oct 6, 2013 at 12:50
  • $\begingroup$ Yes, that's it. $\endgroup$
    – K.G.
    Oct 6, 2013 at 12:51

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.