Eine Einwegfunktion ist eine mathematische Funktion, die schwer umzukehren ist.
Eine solche Funktion muss folgende Eigenschaften aufweisen:
- Die Berechnung des Funktionswerts ist "einfach", d.h. es existiert ein Algorithmus, der ihn in Polynomialzeit berechnen kann.
- Die Berechnung des Inversen zu einem bekannten Funktionswert , d.h. einem , so dass , ist allerdings "schwer", d.h es existiert kein "schneller" Algorithmus für dieses Problem.
Es ist nicht bekannt, ob es Funktionen gibt, die diese Bedingungen erfüllen. Tatsächlich würde der Beweis ihrer Existenz P≠NP beinhalten. Es ist dagegen auch nicht sicher, ob P≠NP die Existenz von Einwegfunktionen bedingt.
In der Praxis gibt es allerdings Funktionen, die die Anforderungen an eine Einwegfunktion ausreichend erfüllen. Es ist lediglich unbewiesen, 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 darstelle. Eine weitere stellt die modulare Exponentiation mit ihrem Inversem, dem diskreten Logarithmus dar.
Eine Abart der Einwegfunktionen sind Trapdoor-Einwegfunktionen (auch Falltürfunktion genannt), diese lassen sich leicht umkehren, wenn man nur eine gewisse Zusatzinformation (eine Geheimtür, engl. trapdoor) kennt. Trapdoor wird in deutschen Texten oft unpasssend mit "Falltür" übersetzt. Trapdoor-Einwegfunktionen werden in asymmetrischen Verschlüsselungsverfahren verwendet, wie zum Beispiel RSA.