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.