What is adversary's advantage in cryptography and why we use it?

Question

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?

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|$.