Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 :) ). –  owlstead Oct 6 '13 at 11:42
    
Probabilistic Polynomial Time adversary... sorry i misspelled it –  dorafmon Oct 6 '13 at 11:53
    
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? –  LateralFractal Oct 6 '13 at 12:16
    
very impressive about the google thing –  dorafmon Oct 6 '13 at 12:48
    
@LateralFractal I'd guess having a site-index (which tells google what has changed) and being popular are the most important factors. –  CodesInChaos Oct 6 '13 at 13:09
add comment

migrated from security.stackexchange.com Oct 6 '13 at 11:29

This question came from our site for Information security professionals.

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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? –  dorafmon Oct 6 '13 at 12:50
    
Yes, that's it. –  K.G. Oct 6 '13 at 12:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.