#### Κρυπτοσυστημα - Σύνολο κλειδιών $\mathcal{K}$ (π.χ. $\\{0,1\\}^{\ell}$) - Σύνολο μηνυμάτων $\mathcal{M}$ (π.χ. $\\{0,1\\}^{\leq n}$) - Σύνολο κρυπτογραφημάτων $\mathcal{C}$ (π.χ. $\\{0,1\\}^{\leq n}$) - Κρυπτοσύστημα $\mathcal{E} = (E,D)$ με - $E: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{C}$ - $D: \mathcal{K} \times \mathcal{C} \rightarrow \mathcal{M}$ - Αν $c = E(k, m)$ τότε $m = D(k, c)$ - Οι αλγόριθμοι $E, D$ είναι αποτελεσματικοί (πολυωνυμικού χρόνου) αλγόριθμοι (ενδεχομένως στοχαστικοί)

#### Attack Games: Οι δυο κοσμοι *Game b* ------ <table> <tr> <td>$\it{Challenger}$</td> <td></td> <td>$\mathcal{A}$</td> </tr> <tr> <td>$k\stackrel{R}{\longleftarrow} \mathcal{K}$</td> <td></td> <td>Επιλέγει μηνύματα $m_0, m_1 \leftarrow \mathcal{M}$ με $|m_0| = |m_1|$</td> </tr> <tr> <td></td> <td>$\stackrel{m_0, m_1}{\longleftarrow}$</td> <td></td> </tr> <tr> <td>$c \longleftarrow E(k,m_b)$</td> <td></td> <td></td> </tr> <tr> <td></td> <td>$\stackrel{c}{\longrightarrow}$</td> <td></td> </tr> <tr> <td></td> <td>$\stackrel{\hat{b}}{\longleftarrow}$</td> <td></td> </tr> </table> ------

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

#### Attack Games: Bit guessing game ------ | $\it{Challenger}$ | | $\mathcal{A}$ | |-------------------|---|---------------| | $k\stackrel{R}{\longleftarrow} \mathcal{K}$ | | Επιλέγει μηνύματα $m_0, m_1 \leftarrow \mathcal{M}$ με $\lvert m_0\rvert = \lvert m_1\rvert$ | | |$\stackrel{m_0, m_1}{\longleftarrow}$| | | $b \stackrel{R}{\longleftarrow} \{0,1\}$ | | | | $c \longleftarrow E(k,m_b)$ | | | | | $\stackrel{c}{\longrightarrow}$ | | | | $\stackrel{\hat{b}}{\longleftarrow}$| | ------

#### Attack Games: Bit guessing game - Το πλεονέκτημα του $\mathcal{A}$: $\ \ \mathrm{Adv^{*}_{SS}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| $ - Ισχύει: $\ \ \mathrm{Adv_{SS}}[\mathcal{A}, \mathcal{E}] = 2\cdot \mathrm{Adv^{*}_{SS}}[\mathcal{A}, \mathcal{E}]$

#### Σημασιολογικη Ασφαλεια Ένα σύστημα κρυπτογράφησης $\ \mathcal{E}\ $ λέγεται σημεσιολογικά ασφαλές, εάν για κάθε επιτηθέμενο $\mathcal{A}$, ο οποίος είναι αποτελεσματικός αλγόριθμος, το πλεονέκτημα $\ \mathrm{Adv_{SS}}[\mathcal{A}, \mathcal{E}]\ $ είναι αμελητέο.

#### Συνεπειες του ορισμου - Κάθε κρυπτοσύστημα που έχει τέλεια ασφάλεια είναι σημασιολογικά ασφαλές.

#### Συνεπειες του ορισμου - Το κρυπτοσύστημα μονοαλφαβητικής αντικατάστασης *δεν* είναι σημασιολογικά ασφαλές! ------ | $\it{Challenger}$| |$\mathcal{A}$ | |---|---|---| | $k\stackrel{R}{\longleftarrow} \mathcal{K}$ | | Επιλέγω μηνύματα $m_0 = aa, m_1 = ab$ | | |$\stackrel{m_0, m_1}{\longleftarrow}$| | |$b \stackrel{R}{\longleftarrow} \{0,1\}$| | | | $c \longleftarrow E(k,m_b)$| | | | |$\stackrel{c}{\longrightarrow}$| | | | |Έστω ότι $c = xy$. Αν $x=y$ τότε $\hat{b} = 0$, διαφορετικά $\hat{b} = 1$ | | |$\stackrel{\hat{b}}{\longleftarrow}$| | ------ $$ \mathrm{Adv^{*}_{SS}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| = 1/2 $$

#### Συνεπειες του ορισμου - Εάν το κρυπτοσύστημα $\mathcal{E}$ είναι σημασιολογικά ασφαλές, κανένας αποτελεσματικός αντίπαλος δεν μπορεί να υπολογίσει έστω και ένα bit πληροφορίας για το αρχικό μήνυμα! Ας υποθέσουμε ότι υπάρχει αποτελεσματικός αντίπαλος $\mathcal{A}$ που μπορεί να υπολογίσει το πρώτο bit του αρχικού μηνύματος με πιθανότητα σημαντικά καλύτερη από $1/2$. Θα κατασκευάσουμε ένα αποτελεσματικό αντίπαλο $\mathcal{B}$ που κερδίζει το παιχνίδι της σημασιολογικής ασφάλειας με πλεονέκτημα μη αμελητέο.

#### Συνεπειες του ορισμου Attack game for bit guessing adversary ------ | $\it{Challenger}$| |$\mathcal{A}$ | |---|---|---| | $k\stackrel{R}{\longleftarrow} \mathcal{K}$ | | | |$m \stackrel{R}{\longleftarrow} \\{0,1\\}^n$| | | | $c \longleftarrow E(k,m)$ | | | | | $\stackrel{c}{\longrightarrow}$ | | | | $\stackrel{\hat{b}}{\longleftarrow}$ | | ------ $$ \mathrm{Adv^{*}_{BG}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = m[0]] - 1/2 \right| $$

#### Συνεπειες του ορισμου ------ |$\it{Challenger}$ | |$\mathcal{B}$| |$\mathcal{A}$| |------------------|---|-------------|---|-------------| |$k\stackrel{R}{\longleftarrow} \mathcal{K}$| | | | | | | |$m \stackrel{R}{\leftarrow} \\{0,1\\}^{n-1}$| | | | | |$m_0 \leftarrow 0m, m_1 \leftarrow 1m$| | | | |$\stackrel{m_0, m_1}{\longleftarrow}$| | | | |$b \stackrel{R}{\longleftarrow} \{0,1\}$| | | | |$c \longleftarrow E(k,m_b)$| | | | | | |$\stackrel{c}{\longrightarrow}$| |$\stackrel{c}{\longrightarrow}$| | | |$\stackrel{\hat{b}}{\longleftarrow}$| |$\stackrel{\hat{b}}{\longleftarrow}$| | ------

#### Συνεπειες του ορισμου $$\mathrm{Adv^{*}_{SS}}[\mathcal{B}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2\right|$$ $$ = \left|\Pr[\hat{b} = m[0]] - 1/2\right|$$ $$ = \mathrm{Adv^{*}_{BG}}[\mathcal{A}, \mathcal{E}] $$