#### Ψευδοτυχαiες Γεννhτριες Αριθμων (Pseudorandom Νumber Generators -- PRG) Ένας αποτελεσματικός αλγόριθμος $\ G\ $ που υπολογίζει τη συνάρτηση $$G : \mathcal{S} \longrightarrow \mathcal{R}$$ (π.χ. $\mathcal{S} = \\{0,1\\}^{\ell}$ και $\mathcal{R} = \\{0,1\\}^L$)

#### Attack Games: Οι δυο κοσμοι *Game 0* ------ |$\it{Challenger}$| |$\mathcal{A}$| |---|---|---| $s\stackrel{R}{\longleftarrow} \mathcal{S}$| | | |$r \longleftarrow G(s)$|$\stackrel{r}{\longrightarrow}$ | | | |$\stackrel{\hat{b}}{\longleftarrow}$| | ------ *Game 1* ------ |$\it{Challenger}$| |$\mathcal{A}$| |---|---|---| |$r\stackrel{R}{\longleftarrow} \mathcal{R}$|$\stackrel{r}{\longrightarrow}$| | | |$\stackrel{\hat{b}}{\longleftarrow}$| | ------

#### Attack Games: Οι δυο κοσμοι - Ορίζουμε $W_b$ να είναι το ενδεχόμενο $\hat{b} = 1$ στο παιχνίδι $b$. - Το πλεονέκτημα του επιτηθέμενου, $\mathcal{A}$ είναι $$\mathrm{Adv_{PRG}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[W_0] - \Pr[W_1] \right| $$

#### Attack Games: Bit guessing game ------ |$\it{Challenger}$| |$\mathcal{A}$| |---|---|---| |$b \stackrel{R}{\longleftarrow} \\{0,1\\}$| | | |Αν $b = 0\ $ : $\ s \stackrel{R}{\longleftarrow}\mathcal{S}, \ \ r \longleftarrow G(s)$| | | |Αν $b = 1\ $ : $\ r\stackrel{R}{\longleftarrow}\mathcal{R}$| | | | |$\stackrel{r}{\longrightarrow}$| | | |$\stackrel{\hat{b}}{\longleftarrow}$| | ------

#### Attack Games: Bit guessing game $$\mathrm{Adv_{PRG}^{*}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| $$ Ισχύει $\mathrm{Adv_{PRG}}[\mathcal{A}, \mathcal{E}] = 2\cdot \mathrm{Adv_{PRG}^{*}}[\mathcal{A}, \mathcal{E}]$

#### Stream Cipher - $\mathcal{E} = (E, D)$ με - Σύνολο κλειδιών: $\ \ \mathcal{K} = \\{0,1\\}^{\ell}$, - Σύνολα μηνυμάτων/κρυπτογραφημάτων: $\ \ \mathcal{M} = \mathcal{C} = \\{0,1\\}^L$ $$G : \\{0,1\\}^{\ell} \longrightarrow \\{0,1\\}^L$$ $$E(k, m) = G(k) \oplus m$$ $$D(k, c) = G(k) \oplus c$$

#### Ασφαλεια _Θεώρημα_: Αν η $G$ είναι ασφαλής PRG τότε το σύστημα $\mathcal{E}$ είναι σημασιολογικά ασφαλές κρυπτοσύστημα. Απόδειξη (ιδέα): Αν η $G$ είναι ασφαλής PRG τότε κανένας αποτελεσματικός αντίπαλος δε μπορεί να ξεχωρίσει το $G(k)$ από μία πραγματικά τυχαία τιμή του $\mathcal{R}$. Οπότε δεν μπορεί να ξεχωρήσει το $\mathcal{E}$ από το one-time-pad, το οποίο είναι σημασιολογικά ασφαλές.

#### Παραδειγματα 1. Ad hoc κατασκευές - RC4 (Ron Rivest, 1987) $40\leq \ell \leq 2048$ - Salsa20 (Daniel Bernstein, 2005) $\ell \in \{128, 256\}$ - ChaCha20 (Daniel Bernstein, 2008) $\ell \in \{128, 256\}$ 2. Κατασκευές που στηρίζονται σε υπολογιστικά δύσκολα προβλήματα - Blum-Michali, 1984 (Discrete logarithm problem) Seed = $x_0$, $x_{n+1} = g^{x_n} \mod{p}$ - Blum-Blum-Shub, 1986 (Quadratic residuosity problem, Integer factorization) Seed = $x_0$, $x_{n+1} = x_n^2 \mod{N},\ \ \ N = p q$

#### Αντι-παραδειγματα - Linear Congruencial Generator (LCG) Seed = $x_0$, $x_{n+1} = a x_n + b \mod{N}$ - Linear-feedback Shift Register (LFSR) Seed = $x_0,\ldots,x_{\ell-1}$, $x_{n+\ell} = a_0 x_{n+\ell-1} + \cdots + a_{\ell-1} x_{n}$ Οι υπολογισμοί γίνονται σε κάποιο πεπερασμένο σώμα, συνήθως το $\mathbb{F}_2$.

#### Κατασκευες _Παράλληλη σύνθεση_ $G : \mathcal{S} \longrightarrow \mathcal{R}$ $G' : \mathcal{S}^k \longrightarrow \mathcal{R}^k\ $, με $\ G'(s_1,\ldots,s_k) = (G(s_1),\ldots, G(s_k))$. <br> _Σειριακή σύνθεση_ $G : \mathcal{S} \longrightarrow \mathcal{S} \times \mathcal{R}$ $G'' : \mathcal{S} \longrightarrow \mathcal{S} \times \mathcal{R}^k\ $, με $\ G''(s) = (s_k, r_1, \ldots, r_k)$ όπου $\ s_0 = s$ και $(s_i, r_i) = G(s_{i-1})$.