Semantic Security Αgainst Chosen Message Attacks
Table of Contents
1. Attack Games
1.1. Οι δύο κόσμοι
Game b
\(\it{Challenger}\) \(\hspace{12cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(\hspace{12cm}\) Επιλέγει μηνύματα \(m_{i,0}, m_{i,1} \leftarrow \mathcal{M}\) για \(i=1,2,\ldots,Q\) \(\hspace{12cm}\) με \(|m_{i,0}| = |m_{i,1}|\)
\(\hspace{7cm}\) \(\stackrel{(m_{i,0}, m_{i,1})}{\longleftarrow}\)
\(c_i \longleftarrow E(k,m_{i,b})\)
\(\hspace{7cm}\) \(\stackrel{c_i}{\longrightarrow}\)
\(\hspace{7cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
- Ορίζουμε \(W_b\) να είναι το ενδεχόμενο \(\hat{b} = 1\) στο παιχνίδι \(b\).
Το πλεονέκτημα του επιτηθέμενου, \(\mathcal{A}\) στο παιχνίδι της σημασιολογικής ασφάλειας είναι
\(\mathrm{Adv_{CPA}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[W_0] - \Pr[W_1] \right| \)
1.2. Bit guessing game
\(\it{Challenger}\) \(\hspace{12cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(b \stackrel{R}{\longleftarrow} \{0,1\}\)
\(\hspace{12cm}\) Επιλέγει μηνύματα \(m_{i,0}, m_{i,1} \leftarrow \mathcal{M}\) για \(i=1,2,\ldots,Q\) \(\hspace{12cm}\) με \(|m_{i,0}| = |m_{i,1}|\)
\(\hspace{7cm}\) \(\stackrel{(m_{i,0}, m_{i,1})}{\longleftarrow}\)
\(c_i \longleftarrow E(k,m_{i,b})\)
\(\hspace{7cm}\) \(\stackrel{c_i}{\longrightarrow}\)
\(\hspace{7cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
Το πλεονέκτημα του επιτηθέμενου, \(\mathcal{A}\) στο παιχνίδι της σημασιολογικής ασφάλειας είναι
\( \mathrm{Adv^{*}_{CPA}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| \)
Λήμμα: \(\mathrm{Adv_{CPA}}[\mathcal{A}, \mathcal{E}] = 2\cdot \mathrm{Adv^{*}_{CPA}}[\mathcal{A}, \mathcal{E}]\)
2. Σημασιολογική Ασφάλεια εναντίον επιθέσεων επιλεγόμενων μηνυμάτων
Για κάθε επιτηθέμενο \(\mathcal{A}\), ο οποίος είναι αποτελεσματικός αλγόριθμος, το πλεονέκτημα \(\mathrm{Adv_{CPA}}[\mathcal{A}, \mathcal{E}]\) είναι αμελητέο.
3. Συνέπειες του ορισμού
3.1. Το one-time-pad
Δεν είναι CPA-ασφαλές!
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(k\stackrel{R}{\longleftarrow} \mathcal{K}\)
\(b \stackrel{R}{\longleftarrow} \{0,1\}\)
\(\hspace{12cm}\) Επιλέγει μηνύματα \(m_{0}, m_{1} \leftarrow \mathcal{M}\) με \(|m_{0}| = |m_{1}|\)
\(\hspace{7cm}\) \(\stackrel{(m_0, m_1)}{\longleftarrow}\)
\(c \longleftarrow E(k,m_{b})\)
\(\hspace{7cm}\) \(\stackrel{c}{\longrightarrow}\)
\(\hspace{7cm}\) \(\stackrel{(m_0, m_0)}{\longleftarrow}\)
\(c' \longleftarrow E(k,m_0)\)
\(\hspace{7cm}\) \(\stackrel{c'}{\longrightarrow}\)
\(\hspace{12cm}\) Αν \(c = c'\) θέτουμε \(\hat{b} = 0\), διαφορετικά θέτουμε \(\hat{b} = 1\)
\(\hspace{7cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
\( \mathrm{Adv^{*}_{CPA}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| = 1/2 \)
3.2. Κάθε ντετερμινιστικό σύστημα κρυπτογράφησης
Δεν είναι CPA-ασφαλές! Γιατί;