Einwegfunktion

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist. In einem erweiterten Sinn werden auch Funktionen so bezeichnet, zu denen bisher keine in angemessener Zeit praktisch ausführbare Umkehrung bekannt ist.

Ein anschauliches Beispiel wäre ein klassisches Papier-Telefonbuch einer größeren Stadt: Kennt man den Namen, dann findet man sehr schnell die dazugehörige Telefonnummer. Kennt man jedoch nur die Telefonnummer, so ist es sehr aufwändig, den zugehörigen Namen zu finden.

Einwegfunktionen bilden die Grundlage asymmetrischer Kryptosysteme.