WIEDER EINMAL stehe ich am Bankautomaten, um Geld zu beziehen. Dass ich Herr Barth bin, glaubt mir der Automat aber nur, wenn ich mich ausweise. Ich tippe also meinen PIN-Code ein und laufe dabei Gefahr, ausspioniert zu werden. Es führt aber kein Weg daran vorbei: Die verifizierende Instanz, in diesem Fall die Bank, kann nur dadurch von meiner Identität überzeugt werden, indem ich das mich identifizierende Geheimnis lüfte.

Welch Fortschritt wäre es doch, wenn ich die Bank davon überzeugen könnte, dass ich die PIN kenne, ohne den PINCode jedes Mal offenlegen zu müssen. Das ist keine Utopie. 1985 stellten die Wissenschafter Goldwasser, Micali und Rackhoff die Idee der Zero-Knowledge- Verfahren vor. Das sind Kommunikations- Verfahren, bei denen ein Teilnehmer, der Beweiser, einen anderen Teilnehmer, den Verifizierer, davon überzeugen kann, ein Geheimnis zu besitzen, ohne dieses Geheimnis je offenbaren zu müssen. Der bestmögliche Weg, ein Geheimnis zu hüten ist ja, es niemals preiszugeben.

Nach 1985 wurde intensiv nach wirklich praktikablen Zero-Knowledge-Verfahren geforscht, und mithilfe bestimmter mathematischer Probleme konnten solche auch realisiert werden. 1991 wurde «Videocrypt » patentiert und war dann in Pay-TV-Systemen im Einsatz. Dabei wurden die Bildsignale so vertauscht, dass nur noch der Besitzer einer Smartcard das normale Programm empfangen konnte. Die Smartcard wiederum musste dem Decoder gegenüber beweisen, dass sie die echte Karte war. Sie tat dies mithilfe eines Zero-Knowledge- Verfahrens, das auf der Mathematik der quadratischen Reste beruht.

Sehr schön illustrieren lassen sich Zero- Knowledge-Verfahren anhand der folgenden Höhlen-Geschichte: Vom Eingang E der Höhle aus führt ein Gang zu einer Verzweigung V, und von dort beschreiben zwei weitere Gänge einen Kreis, der allerdings durch eine Türe unterbrochen ist, die sich nur mit einem PIN-Code öffnen lässt. Will ich dem Bankangestellten Bob gegenüber beweisen, dass ich den PINCode kenne, so spiele ich mit Bob immer wieder folgendes Spiel: Bob wartet bei E, während ich mich in die Höhle zur Türe begebe und dabei zufällig den linken oder rechten Weg wähle. Nun schreitet Bob zur Stelle V, wo er mich nicht sehen kann und wirft eine Münze. Je nach Antwort der Münze befiehlt mir Bob nun, entweder via linken oder via rechten Gang zu ihm zu kommen. In 50% aller Fälle muss ich die Türe öffnen, um diesem Befehl Folge leisten zu können, das heisst, je öfter ich Bobs Befehl korrekt ausführen kann, desto eher wird er überzeugt sein, dass ich den PIN-Code wirklich besitze. Bei dieser Kommunikation wird kein Wissen (zero knowledge) von mir auf Bob übertragen, und trotzdem kann er sehr sicher sein, dass ich das Geheimnis kenne, ohne dass er je zu Gesicht bekommt. Wie oft müssten denn Bob und ich das Spiel spielen, damit die Wahrscheinlichkeit, dass ich immer im richtigen Gang erscheine, ohne den PIN-Code zu kennen, auf 0,001% gesunken sein wird?

Armin P. Barth ist Gymnasiallehrer an der Kantonsschule Baden und Autor.

Die Lösung erscheint mit seiner nächsten Kolumne am 4. Juni 2013.

Lösung vom 2. April 2013: Das fehlende Quadrat hat Fläche 9. Folglich ist x² + 6x + 9 = 20,25. Also (x + 3)² = 20,25. Zieht man die Wurzel, so erhält man (weil x positiv sein muss) x + 3 = 4,5 und somit x = 1,5.