Zero Knowledge Protokolle

Alice will Bob davon überzeugen ein Geheimnis (z.b. die Fähigkeit ein bestimmtes mathematisches Problem zu lösen) zu kennen ohne Bob mehr Informationen über das Geheimnis zu verraten als dieser mit ähnlichem Aufwand selbst herausfinden könnte.

Oft muss sich Bob bei Zero Knowlegde Protokollen an einer Stelle entscheiden ob er die Lösung des Problems (mit bestimmten Parametern) oder einen Teil des Rechenweges erfährt. Um die Wahrscheinlichkeit von Zufallstreffern zu reduzieren, kann die Aufgabe mehrmals mit verschiedenen Parametern gestellt werden.

Eine Zero Knowlegde Protokoll basierend auf Public Key Kryptographie könnte folgendermassen aussehen:

• Aufgabe: Alice will Bob davon überzeugen, daß sie es wirklich ist. Lösung: Alice publiziert einen Public-Key. Z.B. Rsa, diskrete Logarithmen nach Huffman/Duffie/Shamir oder isomorphe Graphen.
  • -Bob verschlüsselt eine Zufallsnachricht mit Alices Public-Key und sendet dies zu Alice. -Alice entschlüsselt diese Nachricht mit ihrem Private-Key und sendet das Ergebnis an Bob. -Bob vergleicht das Ergebnis mit seiner ursprünglichen Nachricht. -Bei Übereinstimmung glaubt er, daß Alice es wirklich ist.

Diese Methode funktioniert, solange Alice ihren Private-Key wirklich geheim hält und die Invertierung des Public-Keys ein NP-Problem ist (bei den genannten 3 Methoden glaubt man dies allgemein, ohne es jedoch beweisen zu können).