Der Turing-Test, unknackbare Verschlüsselung und der ungefähre Beweis

Christoph Pöppe

Es sieht nicht so aus, als hätten diese drei Dinge irgendetwas miteinander zu tun. Aber einem Zaubermeister namens Avi Wigderson gelingt es, eine überraschende Verbindung zwischen ihnen herzustellen.

Wie war das mit dem Turing-Test? Ein Mensch (der „Gutachter“ oder auch die „Gutachterin“) sitzt an einem Computer und tauscht sich schriftlich mit einem unbekannten Gegenüber aus. In der Originalversion war es noch ein Fernschreiber; heute dürfen wir annehmen, dass der Computer der Gutachterin über das Internet mit einer Adresse verbunden ist, die physikalisch überall auf der Welt sein kann und von der man nicht weiß, ob ein Mensch oder ein Computer dahinter steckt. Die Gutachterin darf mit dem unbekannten Wesen einen Dialog führen und soll hinterher entscheiden, ob sie es mit einem echten Menschen oder einem Computer zu tun hatte.

Als Alan Turing 1950 dieses Szenario beschrieb, hatte er keineswegs im Sinn, einen solchen Test tatsächlich durchzuführen. Die Computer seiner Zeit wären kläglich gescheitert. Vielmehr diente es ihm als Aufhänger für eine weiterreichende Überlegung. Nehmen wir an, eine Maschine besteht den Turing-Test. Würde man ihr dann Denkfähigkeit zuschreiben?

Die Frage ist damals wie heute Gegenstand intensiver und bisweilen heftig geführter Debatten. Natürlich kränkt es das Selbstwertgefühl des Menschen, wenn er fürchten muss, dass ihn eine Maschine in der Fähigkeit, die ihn über alles andere Lebende erhebt, der Denkfähigkeit, einholt oder gar übertrifft. Aber heute neigen zumindest die Leute, die professionell Computerwissenschaft betreiben, dazu, die Frage mit „ja“ zu beantworten. Immerhin bemühen sie sich nach Kräften, ihre Maschinen mit Intelligenz auszustatten. Das ist zwar überaus schwierig; aber prinzipielle Grenzen ihrer Bemühungen sind nicht in Sicht.

Avi Wigderson, Träger des Nevanlinna-Preises für theoretische Informatik und des Abel-Preises für Mathematik, ging bei seinem Vortrag auf dem 9. Heidelberg Laureate Forum noch einen Schritt weiter. Auf eine entsprechende Frage aus dem Publikum erwiderte er: „Ja, ich bin eine Maschine. Eine etwas merkwürdige, aber eine Maschine.“ Will sagen: Einen prinzipiellen Unterschied zwischen Mensch und Maschine gibt es nicht. Die eklatanten Unterschiede in der chemischen Zusammensetzung (Kohlenstoff gegen Silizium) zählen nicht, denn Denkfähigkeit ist nicht von der Beschaffenheit des materiellen Substrats abhängig.

Aber vorrangig ging es Wigderson um einen anderen Aspekt: Wie komme ich dazu, einem Mitmenschen Denkfähigkeit zuzuschreiben? Nicht indem ich tiefgründige Analysen seiner Hirnfunktion vornehme. Vielmehr beobachte ich ihn und komme zu dem Schluss, dass er in wesentlichen Aspekten so tickt wie ich selbst. Und da ich selbst mir meiner Denkfähigkeit gewiss bin …

Das Gegenüber beobachten und aus dessen Aktionen Schlüsse ziehen: Nicht weniger tut die Gutachterin im Turing-Test auch. Dass sie dessen körperliche Eigenschaften nicht wahrnehmen kann, ist unwesentlich, siehe oben. Wenn sie also auf Grund ihrer Beobachtungen zu der Überzeugung kommt, dass ihr Gegenüber denken kann, dann muss sie diesem dieselben Denkfähigkeiten zuschreiben wie jedem Menschen. Wir geben uns schließlich im Alltag mit diesem Beweismittel zufrieden und fahren gut damit.

Na ja, man muss diesen Gedanken schon etwas präziser fassen. Man kann das Urteil „denkfähig“ nicht an der Person eines einzelnen Gutachters festmachen. Der könnte ja in der einen oder anderen Richtung voreingenommen sein oder schlicht zu dämlich, um irgendwelche Unterschiede zu erkennen. Aber wenn viele voneinander unabhängige Gutachter zum selben Ergebnis kommen, kann man das schon ernst nehmen. Das ist wie in der Statistik: Wenn eine Größe schwierig zu messen ist, misst man sie halt sehr oft (und sieht zu, dass die Messungen möglichst voneinander unabhängig sind). Wenn die Messwerte dann eine schöne Gaußkurve ergeben, hält man den Wert, an dem sie maximal wird, für den richtigen.

Aber das ist doch kein mathematischer Beweis für die Richtigkeit? In der Tat nicht. Aber, so argumentiert Avi Wigderson, es kommt einem solchen beliebig nahe.

Da gibt es in der Kryptographie eine Behauptung, die sich bislang einem mathematischen Beweis hartnäckig widersetzt, nämlich, dass die sogenannten Falltürfunktionen eine unknackbare Verschlüsselung erzeugen. Es ist – relativ! – leicht, zwei tausendstellige Primzahlen miteinander zu multiplizieren, aber praktisch unmöglich, aus dem Produkt die beiden Faktoren wieder zu ermitteln. Die Multiplikation ist wie eine Tür, durch die man zwar durchgehen kann, aber nie wieder zurück; daher der Name Falltür.

Man lege nun einer Anzahl von Gutachtern zwei Klartexte und deren Verschlüsselungen vor, verschweige aber, welcher verschlüsselte Text zu welchem Klartext gehört. Wenn die Verschlüsselung mit Hilfe einer Falltürfunktion vorgenommen wurde, dann sind die Gutachter nicht in der Lage, die Klartexte den verschlüsselten Texten richtig zuzuordnen. Natürlich können sie raten, aber sie werden nur mit Wahrscheinlichkeit 1/2 richtig liegen. Wenn also sehr viele Gutachter bei diesem Analysespiel (alle Analysetechniken sind erlaubt) keine nennenswert höhere Trefferquote als 50 Prozent erzielen, beweist das die Sicherheit des Verschlüsselungsverfahrens – wieder nicht so richtig, aber ausreichend für alle praktischen Zwecke. Zum Widerlegen genügt dagegen ein einziger Gutachter, der in deutlich mehr als der Hälfte der Fälle richtig liegt.

Später, im Gespräch, gibt Wigderson für diese Art der Beweisführung ein handfesteres Beispiel. Ein Diamant sei definiert als ein Stein, der jedem Hammerschlag widersteht. Wenn 1000 Experten auf einem Stein herumhauen, und keiner kriegt ihn kaputt, dann ist das ein „probabilistischer Beweis“ dafür, dass es sich um einen Diamanten handelt. Was nicht ausschließt, dass der tausenderste ihn mit einem gezielten Schlag zerbröselt und damit als Fälschung entlarvt.

Dieser stets vorhandenen Gefahr zum Trotz will Wigderson vom probabilistischen Beweis nicht lassen. Man kann mit seiner Hilfe sehr viele Dinge beweisen, die auf klassischem Wege nicht beweisbar sind. Andererseits ist das probabilistische Verfahren nicht weniger mächtig: Zu jedem klassischen Beweis kann man eine probabilistische Variante konstruieren.

Das öffnet insbesondere die Tür zu dem „Beweis mit null Ahnung“ (zero-knowledge proof). Ich kann beweisen, dass ich ein Geheimnis besitze, ohne irgendetwas von dem Geheimnis preiszugeben. Und das hat sogar praktische Anwendungen. Ich muss am Geldautomaten der Bank beweisen, dass ich meine Geheimzahl kenne. Wenn ich sie aber einfach eintippe, dann kann ein Bösewicht, der den Geldautomaten manipuliert hat, sie mitlesen und sich später der Bank gegenüber für mich ausgeben. Ein zero-knowledge proof würde dagegen das Sicherheitsbedürfnis der Bank ebenso befriedigen wie mein eigenes.

Diese Beweisform läuft auf ein Frage-und-Antwort-Spiel hinaus: Die Bank stellt mir Fragen, und ich gebe die richtigen Antworten. Ein klassischer Beweis dagegen ist ein typischer Fall von one-way communication: Irgendjemand hat ihn aufgeschrieben, und ich kann nichts weiter tun als ihn zur Kennntnis zu nehmen. Womit Wigderson wiederum elegant zu einem Ergebnis der klassischen Informationstheorie springt: Fehler in der Kommunikation von Sender zu Empfänger lassen sich durch Codes mit eingebauter Redundanz vermeiden, unter zusätzlichem Aufwand für die Übermittlung – oder wesentlich effizienter, wenn der Empfänger im Zweifelsfall rückfragen kann.

The post Der Turing-Test, unknackbare Verschlüsselung und der ungefähre Beweis originally appeared on the HLFF SciLogs blog.