Beweisarchiv: Kryptografie: Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit

Äquivalente Definitionen informationstheoretischer Sicherheit

Definitionen

Informell: Der Schlüsseltext eines informationstheoretisch sicher verschlüsselten Klartextes liefert einem Angreifer keine Informationen über die Wahrscheinlichkeit eines bestimmten Klartextes. Bei ungleichmäßiger Verteilung der Klartexte, aber gleichmäßiger Verteilung der Schlüssel ist also auch eine gleichmäßige Verteilung der Schlüsseltexte garantiert.

Es sei $X$ die Menge aller möglichen Klartexte, $S$ die Menge aller Schlüsseltexte und $K$ die Menge aller Schlüssel.

Definition 1:

$(1)\mathrm{\forall }s\in S\mathrm{\forall }x\in X:W(x)=W(x|s)$

Definition 2:

$(2)\mathrm{\forall }s\in S\mathrm{\forall }x\in X\mathrm{\exists }c\in \mathbb{N}:\left|\{k\in K|k(x)=s\}\right|=c$

Behauptung

Beide Definitionen sind äquivalent, also ist zu zeigen, dass:

$\mathrm{\forall }s\in S\mathrm{\forall }x\in X:W(x)=W(x|s)$

$\iff \mathrm{\forall }s\in S\mathrm{\forall }x\in X\mathrm{\exists }c\in \mathbb{N}:\left|\{k\in K|k(x)=s\}\right|=c$

Beweis

$W(a|b)=\frac{W(a)\cdot W(b|a)}{W(b)}$ (Satz von Bayes)

Daraus folgt:

$(3)\mathrm{\forall }s\in S\mathrm{\forall }x\in X:W(x)=W(x|s)$

$\iff \mathrm{\forall }s\in S\mathrm{\forall }x\in X:W(s)=W(s|x)$

Nun zeigt man, dass dies äquivalent ist zu:

$(4)\mathrm{\forall }s\in S\mathrm{\forall }x\in X\mathrm{\exists }{c}^{\prime }\in ℝ:W(s|x)=c^{\prime }$

Dazu zeigt man beide Richtungen der Äquivalenz getrennt.

$(3)\Rightarrow (4)$:

Da alle Schlüsseltexte gleich verteilt sind, sei $c^{\prime }:=W(s)$.

$(3)\Leftarrow (4)$:

$W(x)\cdot W(s|x)$ ist die Wahrscheinlichkeit, dass ein bestimmter Klartext in einen bestimmten Schlüsseltext verschlüsselt wird.

$\begin{array}{cc}W(s)& =\sum _{x}W(x)\cdot W(s|x)\\ & =\sum _{x}W(x)\cdot c^{\prime }\\ & =c^{\prime }\cdot \sum _{x}W(x)\\ & =c^{\prime }\end{array}$

Nun muss man noch zeigen, dass $(4)$ äquivalent zu $(2)$ ist:

$\begin{array}{cc}W(s|x)& =W(k\in K:k(x)=s)\\ & =\frac{\left|\{k\in K|k(x)=s\}\right|}{\left|K\right|}\\ c^{\prime }& =\frac{\left|\{k\in K|k(x)=s\}\right|}{\left|K\right|}\\ c^{\prime }\cdot \left|K\right|& =\left|\{k\in K|k(x)=s\}\right|\\ \end{array}$

Mit $c=c^{\prime }\cdot |K|$ gilt nun:

$W(s|x)=c=\left|\{k\in K|k(x)=s\}\right|$

Und damit ist:

$\mathrm{\forall }s\in S\mathrm{\forall }x\in X\mathrm{\exists }{c}^{\prime }\in ℝ:W(s|x)=c^{\prime }$

$\iff \mathrm{\forall }s\in S\mathrm{\forall }x\in X\mathrm{\exists }c\in \mathbb{N}:\left|\{k\in K|k(x)=s\}\right|=c$

---