TU Darmstadt / ULB / TUbiblio

Cryptographic Reductions: Classification and Applications to Ideal Models

Baecher, Paul (2014)
Cryptographic Reductions: Classification and Applications to Ideal Models.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Provable security refers to the ability to give rigorous mathematical proofs towards the security of a cryptographic construction; in some sense one of the best possible security guarantees one can attain. These proofs are most often given through so-called reductions to a simpler construction or to some well-studied number-theoretic assumption. This thesis deals with two aspects of such reductions.

First, since a reduction may be difficult to obtain, many reductions for widely-used signature and encryption schemes are conducted in a model that idealizes some underlying building block of the scheme, for example by replacing a hash function with a truly random function. With these reductions in idealized models, it is difficult to compare requirements of cryptographic schemes because the idealization introduces all desired properties simultaneously and it is inexplicit which ones are used and to what extent. This complicates practical considerations when choosing from multiple candidate constructions for the same task.

We develop a novel mechanism to relate schemes proven in idealized models. In this thesis, we present a reductionist paradigm that allows meaningful comparisons of constructions in idealized models with respect to the idealized part. Some of the idealized constructions considered here are the well-known compression-function constructions from blockciphers by Preneel, Govaerts, and Vandewalle (PGV; CRYPTO, 1993), and the twin ElGamal encryption scheme by Cash, Kiltz, and Shoup (Journal of Cryptology, 2009). Our main results show that the random oracle of the twin ElGamal encryption scheme reduces to the random oracle of the regular ElGamal encryption scheme, the PGV constructions fall into two groups, and the so-called double-block-length constructions reduce to one of the PGV constructions with respect to their ideal cipher.

We can thus conclude that the PGV constructions are essentially equivalent within their respective groups and that double-block-length constructions are strictly superior, not only because of their increased key length. Similarly, the regular ElGamal scheme can be replaced by the twin ElGamal scheme (keeping in mind the reduction's tightness), even though the proofs are in an idealized model. These latter results greatly help designers and implementers of practical cryptographic constructions to select the better of two (or more) seemingly equivalent options. Ideal-model reducibility as a comparison tool is applicable to any two constructions whose proof is in an idealized model.

The second aspect of reductions we study in this thesis relates to the absence of reductions. Sometimes, insurmountable obstacles in finding a reduction result in a proof that reductions of some kind cannot exists at all. In that case, it is particularly important to carefully understand what the non-existent reductions look like---since, perhaps, a slightly different reduction is feasible.

We develop means that allow us to better understand existing reductions in the literature. This thesis presents a new framework, akin to the one by Reingold, Trevisan, and Vadhan (TCC, 2004), for classifying reductions in a more fine-grained and more systematic way.

The new framework clarifies the role of efficiency of adversaries and primitives within reductions, covers meta-reduction separations, and provides new insights on the power of relativizing reductions. Consequently, a classification within the new framework clearly points out avenues to circumvent existing impossibility results and enables an assessment of their strength. The generality of the framework permits classification of a large body of existing reductions, but it is easily extensible to include further properties.

Typ des Eintrags: Dissertation
Erschienen: 2014
Autor(en): Baecher, Paul
Art des Eintrags: Erstveröffentlichung
Titel: Cryptographic Reductions: Classification and Applications to Ideal Models
Sprache: Englisch
Referenten: Fischlin, Prof. Dr. Marc ; Shrimpton, Prof. Dr. Thomas
Publikationsjahr: 7 Oktober 2014
Datum der mündlichen Prüfung: 2 Oktober 2014
URL / URN: http://tuprints.ulb.tu-darmstadt.de/4000
Kurzbeschreibung (Abstract):

Provable security refers to the ability to give rigorous mathematical proofs towards the security of a cryptographic construction; in some sense one of the best possible security guarantees one can attain. These proofs are most often given through so-called reductions to a simpler construction or to some well-studied number-theoretic assumption. This thesis deals with two aspects of such reductions.

First, since a reduction may be difficult to obtain, many reductions for widely-used signature and encryption schemes are conducted in a model that idealizes some underlying building block of the scheme, for example by replacing a hash function with a truly random function. With these reductions in idealized models, it is difficult to compare requirements of cryptographic schemes because the idealization introduces all desired properties simultaneously and it is inexplicit which ones are used and to what extent. This complicates practical considerations when choosing from multiple candidate constructions for the same task.

We develop a novel mechanism to relate schemes proven in idealized models. In this thesis, we present a reductionist paradigm that allows meaningful comparisons of constructions in idealized models with respect to the idealized part. Some of the idealized constructions considered here are the well-known compression-function constructions from blockciphers by Preneel, Govaerts, and Vandewalle (PGV; CRYPTO, 1993), and the twin ElGamal encryption scheme by Cash, Kiltz, and Shoup (Journal of Cryptology, 2009). Our main results show that the random oracle of the twin ElGamal encryption scheme reduces to the random oracle of the regular ElGamal encryption scheme, the PGV constructions fall into two groups, and the so-called double-block-length constructions reduce to one of the PGV constructions with respect to their ideal cipher.

We can thus conclude that the PGV constructions are essentially equivalent within their respective groups and that double-block-length constructions are strictly superior, not only because of their increased key length. Similarly, the regular ElGamal scheme can be replaced by the twin ElGamal scheme (keeping in mind the reduction's tightness), even though the proofs are in an idealized model. These latter results greatly help designers and implementers of practical cryptographic constructions to select the better of two (or more) seemingly equivalent options. Ideal-model reducibility as a comparison tool is applicable to any two constructions whose proof is in an idealized model.

The second aspect of reductions we study in this thesis relates to the absence of reductions. Sometimes, insurmountable obstacles in finding a reduction result in a proof that reductions of some kind cannot exists at all. In that case, it is particularly important to carefully understand what the non-existent reductions look like---since, perhaps, a slightly different reduction is feasible.

We develop means that allow us to better understand existing reductions in the literature. This thesis presents a new framework, akin to the one by Reingold, Trevisan, and Vadhan (TCC, 2004), for classifying reductions in a more fine-grained and more systematic way.

The new framework clarifies the role of efficiency of adversaries and primitives within reductions, covers meta-reduction separations, and provides new insights on the power of relativizing reductions. Consequently, a classification within the new framework clearly points out avenues to circumvent existing impossibility results and enables an assessment of their strength. The generality of the framework permits classification of a large body of existing reductions, but it is easily extensible to include further properties.
Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
URN: urn:nbn:de:tuda-tuprints-40003
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Kryptographie und Komplexitätstheorie
Hinterlegungsdatum: 12 Okt 2014 19:55
Letzte Änderung: 12 Okt 2014 19:55
PPN:
Referenten: Fischlin, Prof. Dr. Marc ; Shrimpton, Prof. Dr. Thomas
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 2 Oktober 2014
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen
OAI 2.0-Basis-URL: https://tubiblio.ulb.tu-darmstadt.de/cgi/oai2 TUbiblio verwendet EPrints 3.
Drucken | Impressum | Datenschutzerklärung