Crpytography 2 -- Probability Theory
Previous chapter: Historical Ciphers & Cryptanalysis
This is a learning note of a course in CISPA, UdS. Taught by Nico Döttling
This chapter is a basic probability concept recap and clarify the syntax when writing them, useful if your memory start fading. Remember,
$$\textbf{Cryptography is impossible without randomness!}$$
Probability Spaces
| Components | Definition | Remarks |
|---|---|---|
| $\Omega$ | Sample Space | A finite set |
| $\omega\in\Omega$ | Elementary Events / Outcomes | |
| $Pr:\omega\rightarrow\mathbb{R}$ | Probability Function | $\forall\omega\in\Omega. 0\leq Pr[\omega]\leq1, \underset{\omega\in\Omega}{\sum}Pr[\omega] = 1$ |
| $E\subseteq\Omega$ | Event | $\Pr[E] = \underset{\omega\in\Omega}{\sum}Pr[\omega], \text{ where } Pr[\varepsilon] = 0$ |
Examples
- Fair coin: $\Omega = {0,1}, Pr[0]=Pr[1]=1/2$
- Biased coin: $\Omega = {0,1}, Pr[1]=p, Pr[0]=1-p$
- Fair dice: $\Omega = {1,2,3,4,5,6}, Pr[1]=Pr[2]=\dots=Pr[6]=1/6$
- Uniform Randomness: $\Omega = {1.\dots,N}, Pr[1]=Pr[2]=\dots=Pr[N]=1/N$
Set Operations on events
| Operations | Definition |
|---|---|
| $Pr[E_1\cap E_2] := Pr[E_1\wedge E_2] := Pr[E_1 \textbf{ AND } E_2] := Pr[E_1, E_2]$ | Intersection, Logical ‘AND’ |
| $Pr[E_1\cup E_2] := Pr[E_1\vee E_2] := Pr[E_1 \textbf{ OR } E_2]$ | Intersection, Logical ‘OR’ |
| $Pr[\overline{E}] := Pr[\neg E] := Pr[\textbf{NOT }E] \text{ where }\overline{E}=\Omega\setminus E$ | Complement, Logical ‘Negation’ |
| $A\subseteq B$, $A\Rightarrow B$ | The event A implies the event B |
