Interaktive Beweissysteme

Interaktive Beweissysteme stellen auf zwei Arten eine Verallgemeinerung des in der Mathematik verwendeten Begriffs des Beweises dar. Üblicherweise wird ein Beweis für eine Aussage einmal entwickelt und niedergeschrieben, und jeder, der sich von der Korrektheit der bewiesenen Aussage überzeugen will, braucht dann nur noch diesen Beweis nachzuprüfen (verifizieren). Ein interaktiver Beweis hingegen ergibt sich aus einem Gespräch zwischen einem Beweiser und einem Verifizierer. Dabei dürfen beide, Beweiser und Verifizierer, ihre Fragen und Antworten von den Ergebnissen gewisser Zufallsexperimente abhängig machen. Am Ende des Beweises muss der Verifizierer mit hoher Wahrscheinlichkeit von der Richtigkeit der gemachten Aussage überzeugt sein.

Von besonderem Interesse sind dabei die sogenannten informationslosen Beweissysteme (zero-knowledge proof systems). Dies sind interaktive Beweissysteme, bei denen zwar der Verifizierer von der Richtigkeit der gemachten Aussage überzeugt wird, bei denen aber keinerlei zusätzliche Information verraten wird. Beispielsweise überzeugt ein informationsloser Beweis dafür, dass ein gegebener Graph einen Hamiltonschen Zykel enthält, den Verifizierer von dieser Tatsache ohne einen Hinweis darauf zu geben, wie ein solcher Zykel gefunden werden kann. Offensichtlich lassen sich für solche informationslose Beweissysteme viele Anwendungen, beispielsweise in der Kryptographie, finden.

Die Vorlesung wird sich wie folgt gliedern:

  1. Grundlagen aus der Komplexitätstheorie und der Kryptographie
  2. Interaktive Beweissysteme und die von ihnen definierten Sprachen
  3. Informationslose Beweissysteme
  4. Anwendungen in der Kryptographie

Literatur:

J.L. Balcazar, J. Diaz, J. Gabarro:
Structural Complexity II
Springer-Verlag, 1990 (Kapitel 11).
S. Goldwasser, S. Micali, C. Rackoff:
The knowledge complexity of interactive proof systems
SIAM J. on Computing 18 (1989) 186-208.
weitere Originalarbeiten

Voraussetzungen:

Grundkenntnisse in der theoretischen Informatik im Umfang der Vorlesung "Entwurf und Analyse von Algorithmen".