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

Seminar: Komplexität und Kryptologie

Dozenten: Prof. Dr. Johannes Köbler, Dr. Olaf Beyersdorff


Termin: SE Mi 15-17 (RUD 25, 4.112) Prof. J. Köbler, Dr. O. Beyersdorff

Zuordnung: Hauptstudium, Seminar

Inhalte und Lernziele


Im Zentrum dieses Seminars stehen interaktive Beweissysteme. Die Klasse NP enthält alle Sprachen, für die sich die Wortzugehörigkeit durch einen effizient verifizierbaren Beweis zeigen lässt. In einem Schüler-Lehrer-Modell entspricht dies der Situation, dass der (allwissende) Lehrer den (durch Polynomialzeit beschränkten) Schüler durch Vorlage des Beweises überzeugen kann. Dieses Modell kann dadurch erweitert werden, dass der Schüler an Schlüsselstellen des Beweises (unvorhersehbare) Fragen stellen darf. Überraschenderweise existieren solche "interaktiven Beweise" für alle Sprachen in PSPACE (im Falle von zwei Lehrern sogar für alle Sprachen in NEXP).
Eine insbesondere für kryptogafische Anwendungen interessante Variante interaktiver Beweise bilden Zero-Knowledge-Protokolle, bei denen der verifizierende Schüler ausser der Gültigkeit des Beweises keine zusätzliche Information erhällt.


In den Vorträgen behandelte Themenbereiche

  1. Einführung und Themenvergabe am 18. Oktober 2006
    Johannes Köbler
  2. Arthur-Merlin-Spiele
  3. Zero-Knowledge Protokolle
  4. Multi-Prover Beweissysteme
  5. Probabilistically Checkable Proofs und Approximationsalgorithmen



Empfohlene Literatur