Beweisbare Sicherheit kryptographischer Konstruktionen bezieht sich auf die Möglichkeit, einen rigorosen mathematischen Sicherheitsbeweis zu führen; in gewisser Hinsicht eine der bestmöglichen erreichbaren Sicherheitsgarantien. Diese Beweise sind meist sogenannte Reduktionen auf eine einfachere Konstruktion oder auf eine gut verstandene zahlentheoretische Annahme. In dieser Dissertation studieren wir zwei Aspekte solcher Reduktionen.

Als ersten Aspekt behandeln wir sogenannte Idealisierungen. Vielen Reduktionen für weit verbreitete Signatur- und Verschlüsselungsverfahren liegt ein Modell zugrunde, das Teile der vom Verfahren verwendeten Bausteine idealisiert, beispielsweise in Form einer echt zufälligen Funktion anstelle einer Hashfunktion. Bei derartigen Reduktionen in idealisierten Modellen ist es dann schwierig, Konstruktionen sinnvoll bezüglich ihrer Anforderungen zu vergleichen, weil die idealisierten Bausteine einen Vergleich "verfälschen". Diese Verfälschung entsteht dadurch, dass die Idealisierung sämtliche Sicherheitseigenschaften auf einmal einbringt und nicht unmittelbar klar ist, welche davon genutzt werden und in welchem Umfang.

Diese Dissertation präsentiert ein Reduktionsparadigma, welches sinnvolle Vergleiche von Konstruktionen in idealisierten Modellen bezüglich der idealisierten Bausteine erlaubt. Zu den hier betrachteten Konstruktionen gehören insbesondere die Kompressionsfunktionen aus Blockciphern nach Preneel, Govaerts und Vandewalle (PGV; CRYPTO, 1993) und das "twin ElGamal"-Verschlüsselungsverfahren von Cash, Kiltz und Shoup (Journal of Cryptology, 2009). Unsere Resultate zeigen, dass sich das Random-Oracle des "twin ElGamal"-Verschlüsselungsverfahrens auf das Random-Oracle des regulären ElGamal-Verschlüsselungsverfahrens reduzieren lässt, die PGV-Funktionen in zwei Gruppen fallen und diverse Kompressionsfunktionen mit doppelter Blocklänge auf eine der PGV-Funktionen bezüglich des Ideal-Ciphers reduzierbar sind.

Folglich lässt sich feststellen, dass die PGV-Konstruktionen im Wesentlichen äquivalent innerhalb der jeweiligen Gruppe sind und dass Konstruktionen mit doppelter Blocklänge tatsächlich mehr Sicherheit bieten -- nicht nur wegen der erhöhten Blocklänge. Ebenso kann anstelle des regulären ElGamal-Verschlüsselungsverfahrens das "twin ElGamal"-Verschlüsselungsverfahren verwendet werden (unter Beachtung der Straffheit der Reduktion), obwohl die jeweiligen Beweise in einem idealisierten Modell geführt werden. Diese Resultate helfen Entwicklern praktischer kryptographischer Lösungen, unter mehreren scheinbar äquivalenten Optionen eine gut informierte Auswahl zu treffen. Reduzierbarkeit in idealisierten Modellen findet darüber hinaus grundsätzlich dort Anwendung, wo zwei Konstruktionen, deren Beweis in einem idealisierten Modell erfolgt, miteinander verglichen werden sollen.

Der zweite in dieser Dissertation beleuchtete Aspekt von Reduktionen bezieht sich auf nicht vorhandene Reduktionen. Manchmal ist es nicht möglich, einen Reduktionsbeweis zu führen, sondern zu zeigen, dass eine bestimmte Art von Reduktion gar nicht existieren kann. In solchen Fällen ist es wichtig, die Art der nichtexistenten Reduktionen genau zu verstehen, da möglicherweise leicht abgeänderte Varianten doch existieren könnten.

Wir entwickeln Hilfsmittel, die uns ein besseres Verständnis von in der Literatur existierenden Reduktionen geben. Diese Dissertation präsentiert ein Framework, ähnlich zu dem von Reingold, Trevisan und Vadhan (TCC, 2004), um Reduktionen feingranularer und systematischer zu klassifizieren.

Das neue Framework verbessert unser Verständnis über die Einordnung von Effizienz bei Angreifern und Primitiven innerhalb von Reduktionen, deckt Meta-Reduktionen ab und liefert neue Erkenntnisse über relativierende Reduktionen. Konsequenterweise zeigt eine Klassifikation einer Reduktion in dem vorgestellten Framework neue Richtungen auf, negative Resultate zu umgehen und ermöglicht es, die relative Stärke solcher negativer Resultate besser zu beurteilen. Die Allgemeinheit des Frameworks erlaubt die Erfassung einer Vielzahl existierender Reduktionen; gleichzeitig ist es jedoch auch aufgrund des systematischen Aufbaus einfach erweiterbar.