0
$\begingroup$

In CPA secure IBE systems, the advantage of attacker (A) is defined as absolute value of

$$Pr[b=b^{'}]-\frac{1}{2}$$

Can someone please explain this to me in a few words? Where exactly does that absolute value come from? And how common is this advantage in the realms of cryptography; meaning: how often is this attacker advantage to be considered in general?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

Sometimes, to make it easier to understand, the advantage is multiplied by a factor of 2: $Adv = 2|\Pr[b' = b] - 1/2|$.

Note that when the adversary has no advantage in breaking the protocol, the only thing s/he can do is guessing $b'$ at random. In this case, $\Pr[b' = b] = 1/2$ and thus $Adv = 0$.

When the adversary always correctly finds the value of $b'$, we have $\Pr[b'=b] = 1$ and thus $Adv = 1$.

Similarly, when the adversary always incorrectly guesses the value of $b'$, we have $\Pr[b'=b] = 0$ and thus $Adv = 1$. Note that such an adversary is as powerful that an adversary who always guesses the correct the value. It suffices to flip the result to get the same answer.

To sum up, the advantage is a value between 0 and 1 (or 0 and 1/2 with your definition). The higher the value is, the more powerful the adversary is.

In practice, typically, a cryptographic construction is said IND-CPA secure if $Adv < 2^{-128}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @user94293.Thank you very much. Is that advantage concerned with guessing from two alternatives? That is guessing (0 or 1) or guessing (right or wrong). $\endgroup$
    – myat
    Commented Jul 14, 2016 at 6:42
  • $\begingroup$ I am not sure I understand the question. The IND-CPA security notion is defined as a game between a challenger (who chooses a random bit $b$) and an attacker that at the end of the game returns her guess $b'$ for the value of $b$. $\Pr[b' = b]$ denotes the probability that $b' = b$; i.e., the probability that the attacker correctly guesses the value of $b$. $\endgroup$
    – user94293
    Commented Jul 14, 2016 at 6:49
  • $\begingroup$ @user94293.I understand now that advantage of adversary depends on probability for guessing correct answer. If probability for guessing b' randomly is $\frac{1}{2^{128}}$, then advantage of adversary is $Adv = 2|\frac{1}{2^{128}}- \frac{1}{2^{128}}|$. Is it right? $\endgroup$
    – myat
    Commented Jul 14, 2016 at 7:01
  • $\begingroup$ First, $\frac{1}{2^{128}} - \frac{1}{2^{128}} = 0$. But no, you don't replace the $1/2$ in the formula for the advantage. That number is set in stone due to the known and fixed probability distribution of $b$, which is assumed to be a uniform distribution, with both results having probability exactly $1/2$. If the probability to guess b' correctly would be $1/2^{128}$, the advantage would be $2 \cdot(2^{127} - 1) / 2^{128}\approx 1$. As it was said: An attacker who can almost always return the wrong result can easily be adapted into an attacker who almost always returns the correct result. $\endgroup$
    – tylo
    Commented Jul 14, 2016 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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