Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Seminar: Interaktives Beweisen

Termin: SE Di 9-11 (RUD 25, 4.112) Prof. J. Köbler, S. Kuhnert
Zuordnung:
Hauptstudium, Seminar


Inhalte und Lernziele


Normalerweise versteht man unter einem Beweis etwas statisches: Man kann ihn einmal aufschreiben und er bleibt in dieser Form unverändert gültig. In diesem Seminar betrachten wir eine Erweiterung dieses Prinzips: Zwei Akteure, der Beweiser und der Überprüfer, tauschen Nachrichten aus. Dabei möchte der Beweiser den Überprüfer von der Gültigkeit einer Aussage überzeugen, und der Überprüfer möchte nur Beweise für wahre Aussagen akzeptieren. In der Komplexitätstheorie sind in letzter Zeit zahlreiche Aussagen bewiesen worden, in denen interaktive Beweissysteme eine zentrale Rolle spielen.
Ein interessanter Spezialfall von interaktiven Beweisen sind die zero knowledge proofs, bei denen der Überprüfer durch die Interaktion mit dem Beweiser keine zusätzliche Information über die zu beweisende Aussage bekommt, sondern nur ihre Gültigkeit. Dies ermöglicht interessante Anwendungen in der Kryptographie.

Detaillierte Ankündigung mit Referatsthemen und Literatur


Themen für Referate

(die Termine sind noch vorläufig)
  • 5.5.: IP=PSPACE (Sophia Börner)
  • 12.5.: AM[const]=AM[2] (Arite Lauschke)
  • 19.5.: 3-Coloring in ZK (Roy Lieck)