1
$\begingroup$

I am reading a pdf on pseudorandom function I found here https://www.cs.utexas.edu/~dwu4/courses/sp21/static/reductions.pdf

My problem/struggle is with the computation of the distinguisher's $B$ advantage.
According to the notes $b=0$ means that $B$ receives a sample from the function of interest, let's call it $F$, whereas $b=1$ means that they receive a sample from a truly random let's call it $f$. Then the advantage is defined as: $$ |\Pr[b'=1|b=0]-\Pr[b'=1|b=1]| $$ The first probabillity $\Pr[b'=1|b=0]$ tells us that $B$ wrongly assumed that sample was from a truly random and the second one tells us that they correctly assumed that the sample was from a truly random.
Now it would make more sense to me if instead we computed the probabillity that they correctly assumed that the sample was from $F$ a.k.a $\Pr[b'=0|b=0]$ .

For example if we look at example 1 in the pdf : $G'(s)= G(s) ||s$ .
Now to my understanding : if $B$ receives $t=G(s)$ , they can think of it as $t= t_1||t_2$ and because they know the length of $s$ and $G(s)$ check if $t_2 = s \wedge G(s) = t_1$ .
So if $b=0$ then $\Pr[b'=0|b=0]=1$.

But in the paper instead $\Pr[b'=1|b=0]=1$ is said to be one. I am confused.

$\endgroup$

1 Answer 1

2
$\begingroup$

The definition of the distinguishing advantage is a (pseudo)metric that captures the performance of some distinguished $D$ in distinguishing two experiments, say $E_0$ and $E_1$. The larger the value, the better $D$ is doing. Said otherwise, we view $D$ as outputting some a bit after an experiment; this bit somehow encodes the behavior of $D$ in the given experiment. $D$ is a good distinguisher if it always outputs different bit values ($b'$) for different experiments. For instance, the output $0$ in $E_0$ and always $1$ in $E_1$.

What about $|\Pr^{DE_0}[b'=0|b=0]-\Pr^{DE_1}[b'=1|b=1]|$? Well, in this case, our perfect $D$ would have the lowest advantage of $1 - 1 = 0$.

There are other characterizations of security encoded as bit-guessing games where the advantage is then defined by $|\Pr[b' = b] - 1/2|$.

$\endgroup$
4
  • $\begingroup$ so you do agree with the paper? $\endgroup$ Commented Jan 13, 2023 at 15:52
  • $\begingroup$ @tonythestark, yes I agree. But beyond that, I wanted to motivate the definition and show what is captured by a distinguishing argument. Something else that can to mind: to take another example, think of a distinguisher that always output 1 in experiment 0 and 0 in exp 1. Is this a good distinguisher? $\endgroup$ Commented Jan 15, 2023 at 20:17
  • $\begingroup$ I think I now got what you mean.. We compute our advantage as the propability that we are right minus the case we are wrong $\endgroup$ Commented Feb 14, 2023 at 16:50
  • $\begingroup$ I'll have to think whether that also captures what we want. But there's likely something to it. More abstractly, I like to think of a distinguisher something that has two defined behaviors (out 1/0, raise or low hands, etc...), And the advantage is how the distinguisher behaves (arbitrarily) differently in each situation. $\endgroup$ Commented Feb 15, 2023 at 17:13

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.