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?

$\endgroup$
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}$.

$\endgroup$
  • $\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 Jul 14 '16 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 Jul 14 '16 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 Jul 14 '16 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 Jul 14 '16 at 10:54

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.