1.3 A Discrete Probability Toolbox

Why probability in cryptography? Because “secure” is a claim about what an attacker can do, and the precise version of that claim is a bound on how often she succeeds: every definition we will use (perfect secrecy, pseudorandomness, unforgeability) bounds the chance of some bad event, such as the attacker guessing the key. This section collects the tools the rest of the tutorial needs: distributions, events, the union bound, random variables, independence, one lemma about XOR, and the birthday paradox.

Throughout, $U$ is a finite set, most often $U=\{0,1{\}}^n$, the set of all $n$-bit strings.

1.3.1 Probability distributions

Think of a probability distribution as a set of weights, one for each outcome. Each weight is between 0 and 1, and together they add up to 1. A fair die gives each face weight 1/6; a loaded die gives one face more. Formally:

Definition (probability distribution)

A probability distribution $P$ over a finite set $U$ is a function $P:U\to [0,1]$ such that

$$\sum _{x\in U}P(x)=1.$$

Two extremes matter:

• Uniform distribution: $P(x)=1/|U|$ for every $x\in U$.
• Point distribution at $x_0$: $P(x_0)=1$ and $P(x)=0$ for all $x\ne x_0$.

Concretely, for $U=\{0,1{\}}^3$ a distribution is exactly the vector

$$(P(000),P(001),P(010),\dots ,P(111))\in [0,1{]}^8$$

whose entries sum to $1$. The uniform distribution on $\{0,1{\}}^3$ assigns $1/8$ to every entry; the point distribution at $101$ is $(0,0,0,0,0,1,0,0)$.

1.3.2 Events and the union bound

An event is a yes/no question about the outcome. “The last two bits are 11” selects some outcomes and excludes the rest; its probability is the total weight of the selected outcomes. Formally, for a subset $A\subseteq U$, define

$$\underset{x\leftarrow P}{Pr}[A]:=\sum _{x\in A}P(x),$$

and call $A$ an event. Necessarily $Pr[U]=1$.

Example: on $U=\{0,1{\}}^8$ with the uniform distribution, the event

$$A=\{x\in U:\text{the last two bits of }x\text{ are }11\}$$

has probability $1/4$ (a quarter of all strings end in 11).

If either of two bad events would sink an experiment, the chance that at least one occurs is no larger than the sum of the two chances, because that sum counts the overlap twice. The one inequality you will use in every security proof:

Theorem (union bound)

For events $A_1$ and $A_2$,

$$Pr[A_1\vee A_2]\le Pr[A_1]+Pr[A_2].$$

The proof is one line: summing over $A_1\cup A_2$ counts each outcome in the overlap once, while $Pr[A_1]+Pr[A_2]$ counts it twice. Induction extends the bound to finitely many events. In cryptography its work is always the same: “the attack fails only if one of the bad events $A_1,\dots ,A_q$ happens; each has probability $\le ϵ$; so the whole experiment fails with probability $\le qϵ$.” Controlling a union of many small events is the standard move in a reduction proof.

Example: on $U=\{0,1{\}}^n$ uniform, let $A_1$ be “the last two bits are 11” and $A_2$ be “the first two bits are 11.” Each has probability $1/4$, so

$$Pr[A_1\vee A_2]\le \frac{1}{4}+\frac{1}{4}=\frac{1}{2}.$$

(Here the true value is $7/16$: the bound costs almost nothing and the slack is fine for proofs.)

1.3.3 Random variables

Think of a random variable as a numerical label attached to each outcome. Toss two coins and let $X$ be the number of heads; then $Pr[X=1]$ is the total probability of the outcomes with exactly one head. Formally:

Definition (random variable)

A random variable $X$ (over $U$, taking values in $V$) is a function $X:U\to V$.

Given a distribution on $U$, $X$ induces a distribution on $V$: the probability that $X$ outputs $v$ is the probability of drawing an outcome $x$ with $X(x)=v$.

$$Pr[X=v]:=Pr[X^{-1}(v)]=\sum _{x:X(x)=v}P(x).$$

Example: $X:\{0,1{\}}^n\to \{0,1\}$ defined by $X(y)=\mathrm{lsb}(y)$, the last bit. Under the uniform distribution on $\{0,1{\}}^n$, exactly half the strings end in $0$ and half in $1$, so

$$Pr[X=0]=Pr[X=1]=\frac{1}{2}.$$

The mental picture: $U$ is the sample space with its distribution $P$; $X$ groups outcomes by the value they map to, and the probability that $X=v$ is the total weight of the group for $v$ (its fiber).

Quiz: Let $r$ be uniform on $\{0,1{\}}^2=\{00,01,10,11\}$ and define $X$ to be the number of 1-bits of $r$. Find $Pr[X=2]$.

$X=2$ happens only for $r=11$, so $Pr[X=2]=Pr[r=11]=1/4$. Likewise $Pr[X=1]=1/2$ and $Pr[X=0]=1/4$: $X$’s distribution on $V=\{0,1,2\}$ is not uniform even though $r$ is. A random variable reshapes the distribution it inherits, so “uniform on $U$” does not imply “uniform on $V$.”

1.3.4 The uniform random variable and sampling notation

To say “we draw an element of $U$ uniformly at random” we write

$$r\stackrel{\mathrm{R}}{\leftarrow }U,$$

meaning: $r$ is the uniform random variable on $U$, i.e. the random variable satisfying, for all $a\in U$,

$$Pr[r=a]=\frac{1}{|U|}.$$

Formally, $r$ is the identity map on $U$ equipped with the uniform distribution. This notation will do heavy lifting later: $k\stackrel{\mathrm{R}}{\leftarrow }\mathcal{K}$ for picking a key, $c\leftarrow E(k,m)$ for computing a ciphertext, and adversaries sampled like everything else.

1.3.5 Independence

Two events are independent when learning that one happened does not change the chance of the other. For random variables, independence means that no event about $X$ tells us anything about $Y$. Formally:

Definition (independence)

Events $A,B$ are independent if

$$Pr[A\wedge B]=Pr[A]\cdot Pr[B].$$

Random variables $X,Y$ (taking values in $V$) are independent if for all $a,b\in V$,

$$Pr[X=a\wedge Y=b]=Pr[X=a]\cdot Pr[Y=b].$$

Example: $r$ uniform on $\{0,1{\}}^2$; $X=\mathrm{lsb}(r)$, $Y=\mathrm{msb}(r)$. Then

$$Pr[X=0\wedge Y=0]=Pr[r=00]=\frac{1}{4}=\frac{1}{2}\cdot \frac{1}{2}=Pr[X=0]Pr[Y=0],$$

and the same check works for the other three pairs, so $X$ and $Y$ are independent. Independence is not a default. Two functions of the same uniform variable can be perfectly anti-correlated ($\mathrm{lsb}(r)$ and $\mathrm{lsb}(r)\oplus 1$ always differ), so in proofs it must be either checked or assumed, and this tutorial will put “independent” in a hypothesis more than once. The crucial instance arrives with XOR.

1.3.6 Randomized algorithms

A randomized algorithm is allowed to toss fresh coins while it runs, so two runs on the same input may differ. Formally, a deterministic algorithm takes an input $m$ and produces $y\leftarrow A(m)$. A randomized algorithm also reads fresh random coins:

$$y\leftarrow A(m;r),r\stackrel{\mathrm{R}}{\leftarrow }\{0,1{\}}^n,$$

and its output is a random variable. Encryption is the familiar example, $A(m;k)=E(k,m)$, in which the key is the random coins. From Chapter 2 onward, “attacker” will always mean a randomized algorithm, and security definitions quantify over the randomness of both the scheme and the adversary. This is why all of the probability above is needed: a claim that “the attacker wins with probability at most $2^{-100}$” has no meaning until you say over which coins.

1.3.7 XOR and the masking lemma

The bitwise XOR of two strings in $\{0,1{\}}^n$ is their bit-by-bit addition mod 2:

$$\begin{array}{rrrrrrr}0& 1& 1& 0& 1& 1& 1\\ \oplus 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 0& 1\end{array}$$

For every fixed $s$, the map $x\mapsto x\oplus s$ is a bijection of $\{0,1{\}}^n$ onto itself, and its own inverse. That is what makes XOR a mask: XOR with a fresh uniform string leaves no trace of the original value. The single most useful lemma in the first half of this tutorial:

Theorem (masking lemma)

Let $Y$ be any random variable over $\{0,1{\}}^n$, let $X$ be uniformly distributed on $\{0,1{\}}^n$, and let $X$ and $Y$ be independent. Then

$$Z:=Y\oplus X$$

is uniform on $\{0,1{\}}^n$, whatever $Y$ is.

Proof for $n$ bits: fix any $a\in \{0,1{\}}^n$. Partition the event “$Z=a$” according to the value $y$ that $Y$ took:

$$Pr[Z=a]=\sum _{y\in \{0,1{\}}^n}Pr[Y=y\wedge X=a\oplus y]=\sum _{y}Pr[Y=y]\cdot Pr[X=a\oplus y],$$

where the second equality is independence. But $X$ is uniform, so $Pr[X=a\oplus y]=2^{-n}$ for every $y$:

$$Pr[Z=a]=\sum _{y}Pr[Y=y]\cdot 2^{-n}=2^{-n}\sum _{y}Pr[Y=y]=2^{-n}\cdot 1=2^{-n}.$$

Since $a$ was arbitrary, $Z$ is uniform. ∎

Read the theorem as a security statement: with $Y$ a message and $X$ a fresh uniform key, the ciphertext $Y\oplus X$ is uniform, so it is independent of the message, and an eavesdropper sees a string indistinguishable from coin flips. That is the one-time pad, and the lemma is nearly its whole proof; the rest is making “sees nothing” precise. Keep $X$ fixed and reuse it for many messages, and the lemma no longer applies, which is the one-time-pad-versus-Vigenère lesson of Section 1.2 in one line of algebra.

1.3.8 The birthday paradox

The birthday phenomenon is a statement about pairs rather than samples: the chance of a collision grows roughly like $n^2/|U|$, and the theorem makes the threshold precise:

Theorem (birthday bound)

Let $r_1,\dots ,r_n$ be independent, identically distributed random variables, each uniform on a finite set $U$. When

$$n\approx 1.2\cdot |U{|}^{1/2},$$

the probability that some pair collides, $Pr[\mathrm{\exists }i\ne j:r_i=r_j]$, exceeds $\frac{1}{2}$.

Derivation: work with the complement. “No collision” means $r_2\notin \{r_1\}$, $r_3\notin \{r_1,r_2\}$, and so on, so

$$Pr[\text{no collision}]=1\cdot (1-\frac{1}{|U|})\cdot (1-\frac{2}{|U|})\cdots (1-\frac{n-1}{|U|}).$$

Each factor satisfies $1-x\le e^{-x}$, so the product is at most

$$\exp (-\frac{1+2+\cdots +(n-1)}{|U|})=\exp (-\frac{n(n-1)}{2|U|}),$$

and therefore

$$Pr[\text{collision}]\ge 1-e^{-n(n-1)/(2|U|)},$$

which is the familiar $1-e^{-n^2/(2|U|)}$ with $n-1$ replaced by $n$. At $n=1.2|U{|}^{1/2}$ the exponent is $1.44/2=0.72$, and $1-e^{-0.72}\approx 0.51>\frac{1}{2}$. ∎

The proof assumes a uniform distribution; for non-uniform distributions collisions are only more likely, so the guarantee still holds.

The name comes from birthdays: with $U=\{1,\dots ,365\}$ the threshold is $1.2\sqrt{365}\approx 23$, so 23 people in a room are enough to make a shared birthday more likely than not. The reason is that $n$ people contain $(\genfrac{}{}{0ex}{}{n}{2})\approx n^2/2$ pairs, and it is the pairs, not the people, that collide. Collision risk grows like $n^2/|U|$, which means a space of size $|U|$ gives out after about $\sqrt{|U|}$ samples.

A worked table for $|U|={10}^6$ gives:

$n$ (samples)	collision probability $\approx 1-e^{-n^2/2\cdot {10}^{-6}}$
$\mathrm{1,000}$	$0.39$
$\mathrm{1,200}$	$0.51$
$\mathrm{1,600}$	$0.73$
$\mathrm{2,100}$	$0.89$

With $U=\{0,1{\}}^{128}$, about $2^{64}$ samples suffice to produce a collision, so a 128-bit space gives out after about $2^{64}$ samples; the cryptographic use of this bound arrives in Chapter 5.

With the notation in place, Chapter 2 asks what is a secure cipher, and answers it exactly, once: the one-time pad.