Seminar Cryptocomplexity
(Wintersemester 2013/14)
Termin:
- Mi., 16-18 in C-221
- und nach Absprache! (Bitte den Veranstalter kontaktieren (heitmann@inf...))
Kommentare/Inhalte:
Die Kryptologie (u.a. die Verschlüsselung von Daten für eine sichere
Kommunikation) und die Komplexitätstheorie (u.a. die formale Untersuchung
welche Ressourcen nötig sind, um ein Problem zu lösen) sind vielfach
eng miteinander verbunden. Beispielsweise können die mit Mitteln der
Komplexitätstheorie etablierten unteren Schranken für die Lösung eines
Problems, die Sicherheit geben, dass eine Verschlüsselung nicht mehr mit
vertretbarem Aufwand von einem Angreifer entschlüsselt werden kann.
In diesem Seminar wollen wir uns dem Wechselspiel beider Disziplinen
nähern. Nach einer kurzen Wiederholung der Grundlagen der Komplexitätstheorie
können dann Themen so gewählt werden, dass der Schwerpunkt einzelner Themen
im Bereich der Komplexitätstheorie, der Kryptologie oder auch der Algorithmik
liegt.
Folien:
Hier gibt es die Folien der einzelnen Vorträge zum Download:
- Verschlüsselung (Kapitel 4).
PDF
- Der DES-Algorithmus (Kapitel 6).
PDF und PPT
- Primzahlerzeugung (Kapitel 8).
PDF
- Public-Key Verschlüsselung (Kapitel 9).
PDF
- Probabilistische Polynomialzeitklassen.
PDF
Lernziel:
Erwerb von Kenntnissen aus der Komplexitätstheorie und der Kryptologie
sowie des Wechselspiels der beiden Disziplinen ; Fähigkeiten das Gelernte
präsentieren zu können ; Fähigkeiten eine schriftliche Arbeit entwerfen
und anfertigen zu können.
Vorgehen:
Je nach Gruppengröße Vorträge der TeilnehmerInnen (ggf. in Kleingruppen)
sowie gemeinsames Lesen und Diskutieren einzelner Papiere. In Absprache
mit den TeilnehmerInnen wird ein Teil des Seminars evtl. an einem Wochenende
stattfinden. Am Ende des Semesters Abgabe einer schriftlichen Ausarbeitung.
Genaueres regeln wir dann am ersten Termin. Wer Interesse an der Thematik
hat, aber am Mittwoch voraussichtlich nicht kann, kontaktiert bitte den
Veranstalter (heitmann@inf...).
Literatur:
Wird in der ersten Veranstaltung bekannt gegeben.
Weiteres:
- Zum Vortrag:
Zur Hilfe ist hier ein kleiner Rahmen eines Foliensatzes
in LaTeX, der das Beamerpackage nutzt: talkdraft.zip.
Das kompilierte PDF liegt bei, so dass ihr sehen könnt, zu welchen
Ergebnissen welche Kommandos führen. Außerdem gibt es Kommentare
im LaTeX-Code.
Sucht im Netz auch einfach mal nach dem 'beamer user guide' oder nach
'latex beamer tutorial' und ähnlichem. Wenn ihr Probleme habt, schreibt
mir gerne eine Email.
- Zur Ausarbeitung:
Zur Hilfe ist hier ein kleiner Rahmen einer Ausarbeitung
in LaTeX: seminardraft.zip.
Kompilieren könnt ihr die Datei mittels pdflatex sem-nl-ausarbeitung.tex.
Ggf. müsst ihr das zwei- oder dreimal machen, damit die Referenzen (z.B.
auf Kapitel) stimmen. Im Anschluss müsst ihr dann noch bibtex sem-nl-ausarbeitung
ausführen (ggf. auch zweimal) und dann erneut pdflatex sem-nl-ausarbeitung.tex
(damit die Zitierungen richtig eingepflegt werden).