Komplexitätstheoretische und algorithmische Eigenschaften Boolescher Funktionen mit Bezug zur Kryptographie

• Antragsteller: Professor Dr. Matthias Krause
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5326790

Das Vorhaben zielt auf eine Weiterentwicklung der Komplexitätstheorie Boolescher Funktionen in zentralen Bereichen. Das betrifft erstens die Arbeit an Problemen bezüglich Berechnungskraft und algorithmischen Eigenschaften grundlegender nichtuniformer Berechnungsmodelle. Ein zweiter Schwerpunkt ist durch eine ansatzweise vorhandene Theorie gegeben, die die Schwierigkeit von Untere-Schranken- und Lernbarkeits-Problemen anhand kryptographischer Kriterien klassifiziert. Durch Aufdeckung weiterer allgemeiner Zusammenhänge und die Bestimmung der Komplexität kryptographischer Grundbausteine in verschiedenen Modellen soll diese Theorie verfeinert und ausgedehnt werden. Drittens sollen vor dem Hintergrund des Methodenreservoirs der Booleschen Komplexitätstheorie Beiträge zu Analyse und Design von Kryptosystemen erbracht werden. Das betrifft z.B. hardwareeffiziente Flusschiffren und Sicherheitsbeweise für kryptographische Protokollstrukturen.

• DFG-Verfahren: Sachbeihilfen