▼ Zielgruppen ▼

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

Themen für Studien- und Diplomarbeiten

Nachfolgend sind einige Themenbereiche aufgeführt, zu denen am Lehrstuhl Komplexität und Kryptografie Studien- und Diplomarbeiten betreut werden. Diese Liste ist keineswegs vollständig, insbesondere sind auch eigene Themenvorschläge gern willkommen. Manche der untenstehenden Themengebiete sind nur recht allgemein beschrieben und erlauben eine thematische Konkretisierung in verschiedener Weise, andere Themen betreffen spezifische Vorhaben. Bei Interesse nehmen Sie bitte zur weiteren Absprache Kontakt zu uns auf.


Schnittstellen in Mehrparteien-Protokollen (Prof. Dr. Johannes Köbler)

In Sicherheitsanwendungen gibt es in der Regel mehrere Teilnehmer (z.B. Nutzer oder Geräte), die in Kooperation einen bestimmten Sicherheitsstatus anstreben. Zum Beispiel möchten sie einen gesicherten Kanal aufbauen oder eine Authentifizierung ausführen. Eine wichtige Frage hierbei ist, wie die Schnittstellen zwischen den Beteiligten definiert werden und welche Sicherheitsanforderungen sie erfüllen müssen. In einem konkreten Szenario könnten die Teilnehmer aus einem Nutzer, einer Chipkarte und einem Verifikationssystem auf einem zentralen Server bestehen. Zu realisieren wären dann zumindest die Schnittstellen Nutzer-Chipkarte und Chipkarte-Verifikationsystem.


Komplexität von Ring- und Graphisomorphieproblemen (Prof. Dr. Johannes Köbler)

Das Graphisomorphieproblem (GI) hat eine Sonderstellung in der Komplexitätstheorie.  Es gehört zu den wenigen verbliebenen natürlichen Berechnungsproblemen in der Klasse NP, für die einerseits kein Algorithmus mit polynomieller Zeitschranke gefunden wurde, und für die andererseits auch nicht der Nachweis gelang, dass sie vollständig für NP sind.  Ähnlich verhält es sich mit den Problemen Graphautomorphie (GA) sowie Ringisomorphie (RI) und Ringautomorphie (RA). Das Primzahlproblem gehörte auch zu diesen Problemen, bis Agraval, Kayal und Saxena durch Derandomisierung eines probabilistischen Algorithmus' zeigen konnten, dass es in P liegt.

Von GI,GA,RI und RA wurden verschiedene Einschränkungen und Modifikationen untersucht. Einige konnten präzise in Komplexitätsklassen eingeordnet werden (d.h. sie sind vollständig für die entsprechenden Klassen), viele Probleme sind aber noch offen.


Pseudozufallsgeneratoren in der Kryptografie (Prof. Dr. Johannes Köbler)

Randomisierte Algorithmen spielen für die Praxis eine immer größere Rolle. Oft sind diese konzeptionell einfacher als ihre deterministischen Gegenstücke, manchmal sind auch gar keine effizienten deterministischen Algorithmen bekannt. Reale Computer sind aber nicht randomisiert sondern deterministisch. Eine kleine Anzahl zufälliger Bits lässt sich meist aus der Systemzeit, zufälligen Mausbewegungen oder ähnlichem gewinnen, echter Zufall bleibt aber eine kostbare Ressource.  Der Grundgedanke bei Pseudozufallsgeneratoren besteht darin, aus einer kleinen Anzahl echter Zufallsbits effizient eine große Anzahl pseudozufälliger Bits zu erzeugen. Pseudozufällig bedeutet hierbei, dass die Bits von echten Zufallsbits nicht effizient unterscheidbar sind.

Pseudozufallsgeneratoren haben vor allem zwei Anwendungsgebiete: zum einen in der Kryptografie, zum anderen bei der Derandomisierung, also der Umgehung des Zufalls, bei probabilistischen Algorithmen. Dabei sind diese beiden Anwendungen eng miteinander verbunden und wurden in den letzten Jahren intensiv untersucht.


Quantenkomplexität und Quantenkryptografie (Prof. Dr. Johannes Köbler)

Quantenrechner bilden ein neues Forschungsgebiet, welches die Informatik in bisher unbekannter Weise mit der Physik verbindet. Der Physiker Richard Feynman stellte 1982 fest, dass klassische Computer nicht in der Lage sind, quantenmechanische Systeme effizient zu simulieren, und erörterte in diesem Zusammenhang erstmals die Möglichkeit, Computer auf der Grundlage quantenmechanischer Prinzipien zu bauen.

1985 führte David Deutsch ein theoretisches Modell für Quantenrechner, die Quanten-Turingmaschine, ein. Deutsch demonstrierte auch, dass es Probleme gibt, die mittels Quanten-Turingmaschinen effizienter lösbar sind als mit klassischen Turingmaschinen. Das wohl wichtigste Resultat zu Quantenalgorithmen ist Shor's Quantenalgorithmus für das Faktorisierungsproblem. Mit diesem Algorithmus lassen sich Zahlen in Polynomialzeit in ihre Primfaktoren zerlegen. Die besten bekannten klassischen Algorithmen  benötigen hingegen fast exponentielle Laufzeit.  Dieses Ergebnis sorgte deswegen für Furore, weil die Sicherheit vielfach eingesetzter kryptografischer Verfahren wie des RSA auf der Härte des Faktorisierungsproblems beruht. Gelänge der Bau von Quantenrechnern, würden nahezu alle derzeit benutzten Public-Key-Verfahren unsicher.

Zum einen ist es also wichtig, für die Kryptografie die Folgen des möglichen Einsatzes von Quantenrechner zu untersuchen. Zum anderen ist die Beziehung klassischer Komplexitätsklassen zu Quantenklassen noch weitgehend ungeklärt.


Automatisierbarkeit von aussagenlogischen Beweissystemen (Prof. Dr. Johannes Köbler)

Aussagenlogik ist ein universelles Werkzeug zum Modellieren von Problemen verschiedenster Anwendungsgebiete. Aussagenlogische Beweissysteme sind algorithmische Verfahren zum Beweisen von aussagenlogischen Tautogien. Aus Sicht der Praxis ergibt sich vor allem die Frage, wie effizient diese Verfahren sind. Für ein konkretes Beweissystem P mündet dies in zwei Problemstellungen:

  1. Untere Schranken: Wie lang müssen P-Beweise für gegebene Tautologien mindestens sein?
  2. Automatisierbarkeit: Wie schwer ist es, P-Beweise für gegebene Tautologien zu generieren?


Bezüglich der ersten Frage konnten für eine Reihe von Beweissystemen wie Resolution exponentielle untere Schranken für konkrete Tautologienfolgen nachgewiesen werden, für viele Beweissysteme ist diese Frage aber offen. Die zweite Frage steht in engem Zusammenhang zur Sicherheit kryptografischer Einwegfunktionen. Unter der Annahme der Sicherheit gewisser Einwegfunktionen misslingt die Automatisierbarkeit vieler Beweissysteme, für eine Reihe wichtiger Beweissysteme wie z.B. Resolution ist die Frage dagegen noch ungeklärt.


Berechnung mehrdimensionaler Wahrscheinlichkeiten (Dr. Kössler)


In vielen statistischen Fragestellungen taucht eine mehrdimensionale Normalverteilung auf, deren Wahrscheinlichkeiten Mehrfachintegrale sind. Es sind verschiedene numerische Algorithmen hinsichtlich ihrer Komplexität zu analysieren und zusätzlich Monte Carlo Algorithmen (klassisch, Importance Sampling) zu implementieren.
Die Verfahren sind auf konkrete Beispiele mit (mehr oder weniger) vorgegebenen Korrelationskoeffizienten anzuwenden.

U-Statistiken (Dr. Kössler)


Eine interessante Klasse von Test- und Schätzstatistiken sind U-Statistiken, bei denen aus den Stichproben jeweils Teilstichproben von bestimmtem (festen) Umfang k gezogen werden.
Der Berechnungsaufwand ist größer als bei gewöhnlichen Statistiken. Der Aufwand ist, in Abhängigkeit von den Stichprobenumfängen und von k abzuschätzen.
Weiterhin sind effiziente Algorithmen zu implementieren, vorzugsweise in der Statistiksprache SAS. Fortran oder Java sind ebenfalls möglich.

Extreme Ereignisse (Dr. Kössler)


Zur Modellierung extremer Ereignisse, wie z.B. schlechter Qualität, verwendet man (auch) die verallgemeinerte Pareto-Verteilung. Die Parameter werden nach der Maximum-Likelihood-Methode geschätzt. Die Schätzungen sind asymptotisch normalverteilt, aber eben nur "asymptotisch". Für kleine und mittlere Stichprobenumfänge müssen andere Verteilungen an die Parameterschätzung angepasst werden, z.B. die lognormal-Verteilung.

Folgende Fragestellungen sind experimentell zu lösen:
  1. Welche (bivariaten) Verteilungen approximieren die Verteilung der Parameterschätzungen besser als die Normalverteilung.
  2. Welche Verteilung hat der geschätzte Ausschussanteil?
  3. Maximum-Likelihood-Schätzungen sind globale Maxima von (i.A. nichtlinearen) Funktionen mit evtl. mehreren lokalen Maxima. Evtl. lassen sich Optimierungsprogramme erstellen, die auf die spezielle Likelihood-Funktion der verallgemeinerten Pareto-Verteilung zugeschnitten sind.

Robuste Kontrollkarten (Dr. Kössler)


In der statistischen Qualitätskontrolle verwendet man zur Überwachung des (Produktions-) Prozesses sogenannte Kontrollkarten (z.B. Shewart, Cusum, EWMA), die jedoch stark von der angenommenen Normalverteilung des Prozesses abhängen. Es stellt sich hier die Frage, ob und wie hier robustere Methoden angewendet werden können.



Abgeschlossene Studien- und Diplomarbeiten


2008

Reduzierung von Interaktion in kryptographischen Protokollen
Autor: Martin Stigge

Gitter in der Kryptographie
Autor: Kay Schönberger

Quantenalgorithmen zum Auffinden versteckter Untergruppen
Autor: Philipp Schneider

2007

Visuelle Kryptografie
Autor: Martin Apel

Faktorisierungsverfahren
Autor: Kay Schönberger

2006

Pseudozufallsgeneratoren in der Kryptografie
Autor: Heiko Brandenburg

2005

Undeniable Signatures
Autor: Carsten Schwarz

2004

Untersuchung der Sicherheit von Block-Chiffren
Autor: C. Adams

Einsatz elektronischer Signaturen und Zeitstempel für die Sicherung digitaler Dokumente
Autor: D. Ohst

2003

Entwicklung und Analyse eines biometrischen Authentifikations-Protokolls
Autor: Ben Bässler

2000

Signaturverfahren mit Elliptischen Kurven und dem RSA Algorithmus
Autor: Matthias Schwan


Ältere Diplomarbeiten:


Orakelturingmaschinen und Zufallsorakel

Autor: Werner Ebinger

Einweg-Funktionen und ihre Anwendung in der Public-Key Kryptographie
Autor: Angela Rabini

Effizient prüfbare Beweise für NP-Probleme ( dparb-scheifele.ps.gz)
Autor: Martin Scheifele

Die Bedeutung kryptographischer Falltürfunktionen für Algorithmisches Lernen
Autor: Guido Kehrle

Zero-Knowledge Beweise: Theorie und Anwendungen ( dparb-wutzke.ps.gz)
Autor: Andreas Wutzke

Beziehungen zwischen parallelen Komplexitätsklassen
Autor: Martin Burgbacher

Digitale Signaturen - Theorie und Praxis -
Autor: Silke Bergmaier

Sicherheitsverwaltung in einer Umgebung heterogener Datenbanken im Intranet
Autor: Jochen Rütschlin