Semantic Security
Table of Contents
1. Κρυπτοσύστημα
- Σύνολο κλειδιών \(\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\) είναι αποτελεσματικοί (πολυωνυμικού χρόνου) αλγόριθμοι (ενδεχομένως στοχαστικοί)
2. Attack Games
2.1. Οι δύο κόσμοι
Game b
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(\hspace{10cm}\) Επιλέγει μηνύματα \(m_0, m_1 \leftarrow \mathcal{M}\) με \(|m_0| = |m_1|\)
\(\hspace{6cm}\) \(\stackrel{m_0, m_1}{\longleftarrow}\)
\(c \longleftarrow E(k,m_b)\)
\(\hspace{6cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{6cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
- Ορίζουμε \(W_b\) να είναι το ενδεχόμενο \(\hat{b} = 1\) στο παιχνίδι \(b\).
Το πλεονέκτημα του επιτηθέμενου, \(\mathcal{A}\) στο παιχνίδι της σημασιολογικής ασφάλειας είναι
\(\mathrm{Adv_{SS}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[W_0] - \Pr[W_1] \right| \)
2.2. Bit guessing game
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(\hspace{10cm}\) Επιλέγει μηνύματα \(m_0, m_1 \leftarrow \mathcal{M}\) με \(|m_0| = |m_1|\)
\(\hspace{6cm}\) \(\stackrel{m_0, m_1}{\longleftarrow}\)
\(b \stackrel{R}{\longleftarrow} \{0,1\}\)
\(c \longleftarrow E(k,m_b)\)
\(\hspace{6cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{6cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
Το πλεονέκτημα του επιτηθέμενου, \(\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}]\)
3. Σημασιολογική Ασφάλεια
Για κάθε επιτηθέμενο \(\mathcal{A}\), ο οποίος είναι αποτελεσματικός αλγόριθμος, το πλεονέκτημα \(\mathrm{Adv_{SS}}[\mathcal{A}, \mathcal{E}]\) είναι αμελητέο.
4. Συνέπειες του ορισμού
4.1. Το one-time-pad
Κάθε κρυπτοσύστημα που έχει τέλεια ασφάλεια είναι σημασιολογικά ασφαλές.
4.2. Το κρυπτοσύστημα μονοαλφαβητικής αντικατάστασης
Δεν είναι σημασιολογικά ασφαλές!
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
(το \(k\) είναι μία μετάθεση του αλφαβήτου)
\(\hspace{12cm}\) Επιλέγω μηνύματα \(m_0 = aa, m_1 = ab\)
\(\hspace{6cm}\) \(\stackrel{m_0, m_1}{\longleftarrow}\)
\(b \stackrel{R}{\longleftarrow} \{0,1\}\)
\(c \longleftarrow E(k,m_b)\)
\(\hspace{6cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{12cm}\) Έστω ότι \(c = xy\). Αν \(x=y\) θέτω \(\hat{b} = 0\), διαφορετικά θέτω \(\hat{b} = 1\).
\(\hspace{6cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
\( \mathrm{Adv^{*}_{SS}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| = 1/2 \)
4.3. Εάν το κρυπτοσύστημα \(\mathcal{E}\) είναι σημασιολογικά ασφαλές
κανένας αποτελεσματικός αντίπαλος δεν μπορεί να υπολογίσει έστω και ένα bit πληροφορίας για το αρχικό μήνυμα!
Ας υποθέσουμε ότι υπάρχει αποτελεσματικός αντίπαλος \(\mathcal{A}\) που μπορεί να υπολογίσει το πρώτο bit του αρχικού μηνύματος με πιθανότητα σημαντικά καλύτερη από \(1/2\).
Attack game for bit guessing adversary
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(m \stackrel{R}{\leftarrow} \{0,1\}^n\)
\(c \longleftarrow E(k,m)\)
\(\hspace{6cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{6cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
\( \mathrm{Adv^{*}_{BG}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = m[0]] - 1/2 \right| \)
Θα κατασκευάσουμε ένα αποτελεσματικό αντίπαλο \(\mathcal{B}\) που κερδίζει το παιχνίδι της σημασιολογικής ασφάλειας με πλεονέκτημα μη αμελητέο.
\(\it{Challenger}\) \(\hspace{7cm}\) \(\mathcal{B}\) \(\hspace{11cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(\hspace{10cm}\) \(m \stackrel{R}{\leftarrow} \{0,1\}^{n-1}\)
\(\hspace{10cm}\) \(m_0 \leftarrow 0m\)
\(\hspace{10cm}\) \(m_1 \leftarrow 1m\)
\(\hspace{6cm}\) \(\stackrel{m_0, m_1}{\longleftarrow}\)
\(b \stackrel{R}{\longleftarrow} \{0,1\}\)
\(c \longleftarrow E(k,m_b)\)
\(\hspace{6cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{17cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{17cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
\(\hspace{6cm}\) \(\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}]\)