Computing the advantage when checking PRF

tonythestark

1/6/24, 9:59 AM

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.

1 + 0

pseudo-random-function

distinguisher

pseudo-random-generator

advantage

Score:2

Crypto

Marc Ilunga

1/11/24, 11:40 PM

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

+ 4

tonythestark

1/13/24, 3:52 PM

so you do agree with the paper?

Marc Ilunga

1/15/24, 8:17 PM

@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?

tonythestark

2/14/24, 4:50 PM

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

Marc Ilunga

2/15/24, 5:13 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Computing the advantage when checking PRF

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.