I am working on Victor Shoup’s tutorial on game-based security proof and want to figure out some notions from the perspective of probability theory.
Consider the following PRF advantage defined on Page 11:
$$
bigl|,Pr[s leftarrow S: A^{F_s}() = 1] – Pr[f leftarrow Gamma_{ell_1, ell_2}: A^f() = 1],bigr|
$$
where ${ F_s }_{s in S}$ is a family of keyed functions with key space $S$, domain ${ 0,1 }^{ell_1}$ and range ${ 0,1 }^{ell_2}$, and $Gamma_{ell_1, ell_2}$ denotes the set of all functions from ${ 0,1 }^{ell_1}$ to ${ 0,1 }^{ell_2}$.
I have the following questions:
-
Does the probability notion $Pr[s leftarrow S: cdot]$ (or, $Pr[cdot | s leftarrow S]$ ) has the same meaning as the notion $Pr_{s leftarrow S}[cdot]$ that is also commonly used in crypto contexts (e.g., this)?
For me, $Pr[s leftarrow S: cdot]$ and $Pr[cdot | s leftarrow S]$ seem to be two conditional probabilities, and $Pr_{s leftarrow S}[cdot]$ is like a conditional probability measure. -
How do we interpret a probability $Pr[s leftarrow S: A^{F_s}() = 1]$?
Literally, I know that this captures the probability that the distinguisher $A$ outputs $1$ if it is given oracle access to a function $F_s$ keyed by $s in S$, and the probability is taken over the random choice of $s$.
However, from probability theory, what is the probability space $(Omega, mathcal{F}, Pr)$ where the "event" that "the distinguisher $A$ with oracle access to $F_s$ outputs $1$" is defined? Does the sample space $Omega$ contains all outcomes of $s leftarrow S$ (so that we can say "the probability is taken over the random choice of $s$")?
If so, does this implies that the two probabilities in the PRF advantage comes from two different probability spaces?
