Einwegfunktion

aus Wikipedia, der freien Enzyklopädie

Eine Einwegfunktion ist eine mathematische Funktion, die im Sinne der Komplexitätstheorie "schwer" umzukehren ist.

Eine solche Funktion muss folgende Eigenschaften aufweisen:

• Die Berechnung des Funktionswerts y = f(x) ist "einfach", d.h. es existiert ein Algorithmus, der ihn in Polynomialzeit berechnen kann.

• Die Berechnung des Inversen zu einem bekannten Funktionswert y, d.h. einem x, so dass f(x) = y, ist allerdings "schwer", d.h es existiert kein "schneller" Algorithmus für dieses Problem. "Schnell" meint hier einen probabilistischen Algorithmus, der in Polynomialzeit läuft.

Es ist nicht bekannt, ob es Funktionen gibt, die die Einweg-Bedingungen erfüllen. Tatsächlich würde der Beweis ihrer Existenz gleichzeitig den Beweis für P≠NP zur Folge haben. Umgekehrt reicht dies nicht aus, denn zur Umkehrung der Funktion darf auch ein probabilistischer Algorithmus eingesetzt werden. Damit die Umkehrung also ausreichend ineffizient ist, darf zusätzlich NP nicht (echt oder unecht) in der Komplexitätsklasse BPP enthalten sein. Für einen Einsatz von Einwegfunktionen in der Kryptologie ist komplexitätstheoretisch noch eine weitere Forderung nötig: Die bisher genannten Komplexitätsklassen betrachten ausnahmslos den sogenannten "worst-case" - die längste Laufzeit eines Algorithmus. Nötig wäre aber eine bewiesene ineffiziente Laufzeit auch im "average case".

In der Praxis gibt es Funktionen, die die Anforderungen an eine Einwegfunktion bislang ausreichend erfüllen. Es konnte jedoch bisher nicht der Beweis erbracht werden, ob es wirklich "schwierig" ist, sie zu invertieren. Ein Beispiel für eine solche Funktion ist die Multiplikation von zwei großen Primzahlen, da man annimmt, dass eine Primfaktorzerlegung ein "schwieriges" Problem darstellt. Eine weiteres Beispiel ist die modulare Exponentiation mit ihrer Inversen, dem diskreten Logarithmus. Die Wirkung einer Einwegfunktion wird gerne mit dem Prinzip eines Telefonbuchs verglichen: Kennt man den Namen, findet man sehr schnell die dazugehörige Telefonnummer. Wenn man aber nur die Nummer ohne den dazugehörigen Namen kennt, ist es fast unmöglich, diesen alleine mit Hilfe des Telefonbuches zu finden.

Eine Variante der Einwegfunktionen sind Trapdoor-Einwegfunktionen (auch Falltürfunktionen genannt). Diese lassen sich effizient umkehren, wenn man nur eine gewisse Zusatzinformation (eine Geheimtür, engl. trap door) kennt. Trap door wird in deutschen Texten oft unpassend mit "Falltür" übersetzt. Trap door-Einwegfunktionen werden in asymmetrischen Verschlüsselungsverfahren verwendet, wie zum Beispiel RSA.