Definitionen
- $y := f(x)$ kann in Polynomialzeit berechnet werden
- Für die Berechnung eines Urbildes $x$ aus $y$ existiert kein randomisierter Algorithmus, der in Polynomialzeit läuft.
Was heißt „kleine Wahrscheinlichkeit“? Nach dem Auswerten der Funktion $H$ für $x_1, x_2, \dots x_n$ sollte die Wahrscheinlichkeit nicht signifikant höher sein als $\displaystyle 1-\frac{n!\cdot{{2^k} \choose n}}{{2^k}^n}$ Diese Wahrscheinlichkeit kommt von dem Geburtstagsparadoxon bzw. dem Schubfachprinzip. Wir haben $2^k$ Schubfächer (Funktionswerte) in die wir die $x_i$ (Urbilder) einordnen können.
Satz
Behauptung: Jede kollisionsresistente Hashfunktion ist eine Einwegfunktion. Beweis: durch Widerspruch Sei $f$ eine kollisionsresistente Hashfunktion Annahme: $f$ ist keine Einwegfunktion
Dann existiert ein Angreifer $\mathcal{A}$, der für eine Bild $f(x)$ ein $x'$ findet, sodass $f(x) = f(x')$ gilt.
Der Angreifer $\mathcal{B}$ macht nichts anderes, als zufällig Werte $x \in {0,1}^{2k}$ zu wählen, $f(x)$ zu berechnen, den Angreifer $\mathcal{A}$ auf $f(x)$ anzuwenden und zu überprüfen, ob das von $\mathcal{A}$ gelieferte $x' \neq x$ ist. Sobald das ein mal der Fall ist, hat der Angreifer gewonnen.
Nun wenden wir $f$ auf $x \in {0,1}^{2k}$ an. Es gilt:
$Pr_x[\underbrace{|f^{-1}(f(x))|}_{\substack{\text{Anzahl der Urbilder}\\text{zum Hashwert} f(x)} } = 1] \leq \frac{2^k}{2^{2k}} = \frac{1}{2^k}$.
Die $2^k$ im Zähler stehen für die Funktionswerte und die $2^{2k}$ für die Urbilder.
Nun ist $\frac{1}{2^k}$ eine vernachlässigbare Funktion.
$\Rightarrow$ Die Wahrscheinlichkeit, dass wir keine Kollsion finden ist vernachlässigbar.
$\Rightarrow$ Mit signifikanter Wahrscheinlichkeit hat $f(x)$ $k \geq 2$ Urbilder.
$\Rightarrow$ Die Wahrscheinlichkeit, dass $\mathcal{B}$ Kollisionen findet ist etwa $(1-\frac{1}{k}) \cdot m$, wobei $m$ die Anzahl der Widerholungen ist.