Ein Schlüsselaustausch ermöglicht zwei Parteien, sich über einen unsicheren Kanal auf einen gemeinsamen, geheimen Schlüssel zu einigen. Diffie und Hellman [DH76] entwickelten 1976 das erste Schlüsselaustauschprotokoll und legten damit den Grundstein für ein fruchtbares Forschungsgebiet. Eine der wichtigsten Arbeiten auf diesem Gebiet ist das spielebasierte Sicherheitsmodell von Bellare und Rogaway [BR93] aus dem Jahre 1993, welches heutzutage als "goldener Standard" fur die Sicherheit von Schlüsselaustauschprotokollen gilt.

Ein Schlüsselaustausch wird gemeinsam mit einem anderen Protokoll ausgeführt, welches die abgeleiteten Schlüssel verwendet. Idealerweise hoffte man, daß ein BR-sicherer Schlüsselaustausch und ein sicheres Anwendungsprotokoll auch bei gemeinsamer Ausführung sicher bleiben. Diese Aussage ist für simulationsbasierte Sicherheitsmodelle bekannt [Can01, KT11, BPW03], für spielebasierte Modelle verfügen wir allerdings oft über kein einziges Kompositionstheorem. Das ist insofern ungünstig, als daß spielebasierte Modelle für praktische Protokolle wie TLS besser geeignet sind.

Unsere ersten zwei Kompositionstheoreme befassen sich mit der Komposition von BR-sicheren Protokollen mit Anwendungsprotokollen, die auf symmetrischen Schlüsseln basieren. Wir stellen dabei durch einen formalen Beweis fest, daß es notwendig ist, daß der Schlüsselaustausch einen Public Session Matching Algorithmus besitzt.

Überraschenderweise sind einige bedeutende Schlüsselaustauschverfahren nicht BR-sicher, da sie sogenannte Key Confirmation verwenden. Wir entwickeln daher ein zugleich flexibleres und starkes Modell für diese Klasse von Protokollen und zeigen, daß das Modell unter Reduktionen abgeschlossen ist. Insgesamt bieten unsere Kompositionsresultate eine Technik zur modularen Analyse praktischer Protokolle, was wir anhand einer abstrahierten Version von TLS aufzeigen.

Da praktische Kryptographie und Schlüsselaustausch insbesondere keine informationstheoretische Sicherheit bieten kann, basieren Protokolle wie TLS auf komplexitätstheoretischen Annahmen wie z.B. der Diffie-Hellman Annahme. Da die Sicherheit eines Protokolls auf dem Schwierigkeitsgrad des zugrundeliegenden Problems beruht, ist die Studie schwächerer, einfacher Annahmen eine wichtige Forschungsrichtung. Das größte offene Problem auf diesem Gebiet ist es, Schlüsselaustausch, One-Way-Funktionen oder andere Primitive darauf zu reduzieren, daß NP ungleich P ist [FF93, BT03, AGGM06]. Kürzlich konnten Unmöglichkeitsresultate zeigen, dass z.B. Primitive wie Hash-Funktionen nicht auf NP-schwierige Probleme reduziert werden können, sofern coAM nicht in NP liegt [HMX10, PTV11].

In dieser Arbeit zeigen wir mittels zweier Orakelseparierungen, dass es nicht möglich ist, die vorgenannten Unmöglichkeitsresultate mithilfe von relativierenden Reduktionen auf Schlüsselaustausch und reguläre One-Way-Funktionen zu übertragen. Relativ zu unserem ersten Orakel sind Sprachen in der Schnittmenge von NP und coNP einfach, während unendlich häufig sicherer Schlüsselaustausch existiert. Unser zweites Orakel erreicht, dass die Schnittmenge von AM und coAM in P enthalten ist, während zugleich eine Familie regulärer Funktionen unendlich oft one-way ist.