Perfect Security

• Σύνολο κλειδιών \(\mathcal{K}\)
• Σύνολο μηνυμάτων \(\mathcal{M}\)
• Σύνολο κρυπτογραφημάτων \(\mathcal{C}\)
• Κρυπτοσύστημα \(\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)\)

Για κάθε \(c\in \mathcal{C}\) και κάθε \(m_0, m_1 \in \mathcal{M}\) ισχύει \( \Pr[E(K, m_0) = c] = \Pr[E(K, m_1) = c]\), όπου η τυχαία μεταβλητή \(K\) είναι ομοιόμορφα κατανεμημένη στο \(\mathcal{K}\).

1. Το \(\mathcal{E}\) έχει τέλεια ασφάλεια
2. Για κάθε \(c\in \mathcal{C}\), υπάρχει ακέραιος \(N_c\) τέτοιος ώστε για κάθε \(m\in\mathcal{M}\) ισχύει \(\left|\left\{k\in \mathcal{K} : E(k, m) = c\right\}\right| = N_c\)
3. Αν η τυχαία μεταβλητή \(K\) είναι ομοιόμορφα κατανεμημένη στο \(\mathcal{K}\), τότε οι τυχαίες μεταβλητές \(E(K, m), m\in\mathcal{M}\) έχουν την ίδια κατανομή.
4. Για κάθε συνάρτηση \(\phi: \mathcal{C}\rightarrow \{0,1\}\) και κάθε \(m_0, m_1\in \mathcal{M}\), ισχύει \(\Pr[\phi(E(K,m_0)) = 1] = \Pr[\phi(E(K,m_1)) = 1]\), όταν το κλειδί \(K\) λαμβάνεται τυχαία και ομοιόμορφα από το \(\mathcal{K}\).

Το one-time-pad έχει τέλεια ασφάλεια!

• Αν το \(\mathcal{E}\) έχει τέλεια ασφάλεια, τότε \(|\mathcal{K}| \geq |\mathcal{M}|\).
• Για παράδειγμα, αν \(\mathcal{K} = \{0,1\}^{L}\) και \(\mathcal{M} = \{0,1\}^{\ell}\), πρέπει \(L\geq \ell\).
• Ποιός χρησιμοποιεί το one-time-pad;
• Ίσως το two-time-pad είναι αρκετά καλό; (Project Venona)