Direkt zum Inhalt
Komplexität und Kryptographie

Komplexität und Kryptografie

Document Actions

Seminar: Komplexität und Kryptologie

Termin: SE Mi 13-15 (RUD 25, 4.112) Prof. J. Köbler, S. Kuhnert

Zuordnung:
 Hauptstudium, Seminar
Der Seminarbeginn ist der Mi., 24.10.2007 (Einführung und Themenvergabe).

Inhalte und Lernziele

In diesem Seminar werden aktuelle Themen der Theoretischen Informatik, insbesondere der Komplexitätstheorie und der Kryptologie behandelt. Hierbei gehen wir auch gern auf Teilnehmerwünsche ein.

In diesem Semester wollen wir uns schwerpunktmäßig den Themen Pseudozufallsgeneratoren und Derandomisierung widmen. Die Erzeugung von Bitfolgen mit "zufälligen" Eigenschaften besitzt zahlreiche Anwendungen in der Kryptografie. Darüber hinaus sind Pseudozufallsgeneratoren ein zentrales Konzept der modernen Komplexitätstheorie, welches u.a. für die Derandomisierung probabilistischer Komplexitätsklassen genutzt werden kann.


Vorkenntnisse aus der Komplexitätstheorie sind zum Besuch dieses Seminars nützlich, jedoch nicht unabdingbar.
Im Seminar sind Vorträge einführenden und vertiefenden Charakters zu folgenden Themenbereichen geplant:
  • Einwegfunktionen
  • Pseudozufallsgeneratoren
  • Derandomisierung
  • Nisan-Wigderson-Generatoren
  • Arthur-Merlin-Klassen
  • Hitting-Set-Generatoren
  • Extraktoren

In den Vorträgen behandelte Themenbereiche

(Die angegebenen Daten haben vorläufigen Charakter.)
  1. Einführung und Themenvergabe am 24. Oktober 2007
    Johannes Köbler
  2. 07.11. und 14.11.: Äquivalenz der Existenz von schwachen und starken Einwegfkt.
     Mark Kibanov
  3. 21.11.: Äquivalenz der Definitionen von sicheren PZG von Blum-Micali und Yao
     Sebastian Kuhnert
  4. 28.11.: Visuelle Kryptographie
     Martin Apel
  5. 05.12.: Derandomisierung von probabilistischen Komplexitätsklassen
     Nils Alberti
  6. 12.12. und 19.12.: Weitere Anwendungen: Multiparty Computations
    Sarah Hauser
  7. 09.01.08 und 16.01.: Äquivalenz der Existenz von Einwegfkt. und PZG
     Martin Stigge
  8. 30.01.
     Nils Alberti


Empfohlene Literatur


Neben neueren Originalarbeiten ist folgende Literatur für dieses Seminar nützlich:
  • S. Arora, B. Barak. Computational Complexity: A Modern Approach. Kapitel 10. Cryptography und Kapitel 16. Derandomization, Expanders and Extractors. Erscheint 2008. Online unter http://www.cs.princeton.edu/theory/complexity
  • O. Goldreich: Foundations of Cryptography, Cambridge University Press, 2001. (Siehe auch: http://www.wisdom.weizmann.ac.il/~oded/ln00.html )
  • D. Gutfreund, R. Shaltiel A. Ta-Shma: If NP languages are hard on the worst-case then it is easy to find their hard instances, Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity, 2005.
  • D.E. Knuth: The Art of Computer Programming, Band 2, Addison-Wesley, 1982.
  • D.E. Knuth und A.C. Yao: The Complexity of Nonuniform Random Number Generation. In: Algorithms and Complexity, J.F Traub (Ed.), Academic Press, 1976.
  • J.C. Lagarias: Pseudorandom Number Generators in Cryptography and Number Theory. In: Cryptology and Computational Number Theory, C. Pomerance(Ed.), American Mathematical Society, 1990.
  • M. Luby: Pseudorandomness and Cryptographic Applications, Princeton University Press, 1996.
  • R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
  • D.R. Stinson: Cryptography, CRC Press, 1995.
  • M. Tompa: Lecture Notes on Probabilistic Algorithms and Pseudorandom Generators, 1991.
  • L.Trevisan: Lecture Notes from IAS Summer School on Computational Complexity, 2000.
  • R. Shaltiel, C. Umans: Pseudorandomness for Approximate Counting and Sampling, Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity, 2005.
zuletzt geändert: 25.01.08 SV
Persönliche Werkzeuge