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

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

  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.