Probability conventions in cryptography

Question

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:

1. 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]$, $\Pr[\cdot | s \leftarrow S]$, and $\Pr_{s \leftarrow S}[\cdot]$ seem to refer to the same conditional probability measure.

2. 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 come from two different probability spaces?

Answer 1

I completely understand your thoughts, I also had a similar question here.

I will answer your question based on my understanding, I would like to hear any thoughts or disagreements, because I haven't completely figured out the situtation yet.

Let's consider the Kolmogorov's definition of probability and forget about Random variables (these are used just to help us by converting a probability space to one that can be more efficiently handled).

A Probability Space is just $(Ω, \mathcal{F}, Pr)$ where:

• $Ω$ : is the set of the events
• $\mathcal{F}$ : is a σ-algebra defined on $Ω$, it is the event space.
• $Pr$ : is a set function $P : \mathcal{F} \rightarrow \mathbb{R}$

2. 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?

There are multiple level of approaches you can take, depending on the time have.

Consider the algorithm $B() = s \leftarrow S; A^{F_s}()$ that outputs whatever $A$ outputs. Now we can rewrite the above as $Pr[B() = 1]$. The $Ω=\{0,1\}$ since $A$ is a distinguisher, see here. The $\mathcal{F} = \{\emptyset, \{1\}, \{0\},\{0,1\}\} = \mathcal{P}(Ω)$. Also let $Pr$ be a probability measure. Now I think it is clear.

But let's try to rewrite this. Consider a uniform distribution on $S$. That is $Ω=S$, $\forall s \in S, Pr(s) = 1/|S|$, this is the probability measure, you can check that it satisfies the definition. Also $\mathcal{F}=\{\emptyset, s_1, s_1^c, s_2, s_2^c, \dots, Ω\}$. In my opinion the $\mathcal{F}$ here is an overkill because we are only interested in single events, it is a way to model a simple random algorithm that outputs a single element. Now consider $B(s) = A^{F_s}()$. Now we have two probability spaces and we want to create a conditional probability. So we have

$$Pr(B(s)|s)=\dfrac{Pr(B(s),s)}{Pr(s)}$$

We can again create a σ-algebra $\mathcal{F}$ and repeat the process as above, but it will require a lot of time.

1. 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][2])? 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.

From my experience I think they refer to the same conditional probability measure. If someone has another view he can leave a comment to discuss it or update the answer.

My opinion: At the end of the day all of this is just notation to express the same thing. You can either consider the higher level approach I gave first, where you consider a random process that has embedded some other random processes, or you can analyze every random process itself and consider their relations. In cryptography we are not really interested in the low level mathematical mechanisms, this is why you find so many different notations. It is about the subject we want to describe and authors will always the higher level approach as soon as it is can be understood by the reader for the purpose of the specific matter.

Answer 2

My understanding

Please correct me if there is something wrong with my understanding.

Without loss of generality, we first assume that the distinguisher $A$ is deterministic (since a probabilistic distinguisher can be seen as a deterministic one taking an explicit random tape as input). Now, consider the probability $\Pr[s \leftarrow S: A^{F_s}() = 1]$. The only randomness during the interaction between $A$ and the oracle $F_s(\cdot)$ is the key $s$, given that (i) $A$ is deterministic, and (ii) $F_s$ is a deterministic function for any fixed $s \in S$.

It is natural to consider a probability space $(\Omega, \mathcal{F}, \Pr)$ where the sample space $\Omega$ contains all possible outcomes of $s$ (i.e., $\Omega = S$), the $\sigma$-algebra $\mathcal{F} \subseteq 2^\Omega$ contains all possible compound events from elementary events (i.e., single elements in $\Omega$), and the probability measure $\Pr: \mathcal{F} \rightarrow \mathbb{R}$ assigns probability values to events. In this probability space, we are interested in the event $S_0 \subseteq \Omega$ (i.e., the collection of $s$'s) where each $s \in S_0$ leads to the deterministic output $A^{F_s}() = 1$. Thus, I think the three notations in my first question are equivalent such that $$ \begin{align*} &\Pr[s \leftarrow S: A^{F_s}() = 1] \equiv \Pr[A^{F_s}() = 1 \ |\ s \leftarrow S] \equiv \Pr_{s \leftarrow S}[A^{F_s}() = 1] \\ =\ &\Pr[\{ s \in \Omega \ |\ X(s) = 1 \}] \qquad \text{($X: \Omega \rightarrow \{ 0,1 \}$ is a random variable for the output $A^{F_s}()$)} \\ =\ &\frac{| S_0 |}{| S |} \qquad \text{(by the definition of $S_0$ and that $s \leftarrow S$ is a uniform sampling)} \end{align*} $$ The other probability can be understood likewise, except that the sample space $\Omega = \Gamma_{\ell_1, \ell_2}$, and the other two components in the probability space are defined accordingly.

Technically, we can regard the part "$s \leftarrow S$" in the three probability notations as a "reminder" of the underlying sample space $\Omega = S$. This "reminder" does not participate in the probability calculation (e.g., probability inequalities) except that it (i) defines the sample space $\Omega$ and (ii) assigns even probability values to the elementary events in $\Omega$. This immediately resolves my second question. In particular, the two probabilities are from two different probability spaces with different sample spaces.

I would like to additionally note that the security should hold for any PPT $A$, and this requirement prevents us from directly compute $S_0$ (and thus the concerned probability). We usually turn to bound the advantage (aka the absolute difference between the two probabilities) using statistical distance (upper bound) or another assumption of computational indistinguishability. However, I think that the infeasibility to compute $S_0$ does not prevent this probability from being well-defined on the probability space for any fixed PPT distinguisher $A$.