Towards Bringing Cryptographic Idealized Models Closer to Reality

Real-world cryptosystems are complex objects involving a number of components that have to work in unison for their combination to run as intended. This makes assessing their security a challenging task, so much so that a complete analysis of a system as it stands is often out of reach. As a result, to gain confidence in the soundness of an application, it is essential to make abstractions about certain parts of the scheme while studying its security, and leave some of its specifics outside the model.

Idealized and restricted models of computation, like the random-oracle (ROM), the generic-group (GGM), and the algebraic-group (AGM) models, are three examples of such abstractions: They simplify what real-world hash functions and cryptographic groups are and how algorithms can interact with them. As abstractions, they have been exceptionally successful in justifying the security of many classical and modern cryptosystems that otherwise resist analysis under well-known and widely accepted assumptions. However, these models also come with standard-model uninstantiability results, raising the question of whether the schemes analyzed under them can be based on firmer standard-model footing. In this work, we tackle this question from two different angles.

In the first part of this thesis, we study a cryptographic scheme whose security is justified in the ROM yet whose security proof uses a distinctive feature of random oracles (programmability) that no real-world hash function provides. This, in turn, puts the meaning of the proof itself into question, as it cannot be replicated once the abstraction provided by the ROM is dispensed with. To make matters worse, we prove that this state of affairs is inherent, i.e., that a ROM-proof for the scheme that does not rely on this artificial property is unlikely to exist. We then go on to show that one can modify the scheme in such a way that a reduction that does not require programming the random oracle becomes possible. This serves as an example of how one can sometimes tweak schemes so that they are backed by "better" heuristic evidence of security and should, therefore, be preferred as they are arguably "closer to reality."

In the second and third parts of this thesis, we propose new standard-model assumptions for cryptographic groups. We validate these assumptions in appropriate idealized models and then show how they can be used to instantiate a range of existing, practical schemes previously proven secure only in the GGM or the AGM. These results facilitate a modular approach to security in the GGM and AGM since our definitions form an intermediate "layer" between the models themselves and the final applications. Our novel assumptions combine standard-model analyses with the ease of use offered by the corresponding idealized model and, in some cases, even allow reusing existing proofs. Importantly, our assumptions enable basing the security of our target applications in the standard model, thus placing them outside the class of uninstantiable schemes.

Praktische Kryptosysteme sind vielschichtig und bestehen aus einer Reihe von Komponenten, die ineinandergreifen müssen, damit die Endanwendung wie vorgesehen funktioniert. Dies erschwert die Bewertung ihrer Sicherheit so sehr, dass die vollständige Analyse eines Systems in seiner Gesamtheit oft nicht machbar ist. Um Vertrauen in die Funktionssicherheit einer Anwendung zu gewinnen, ist es daher unerlässlich, bei der Untersuchung von deren Sicherheit bestimmte Teile des Systems zu abstrahieren und einige Details außerhalb des Modells zu belassen.

Idealisierte und eingeschränkte Berechnungsmodelle, wie das Zufallsorakelmodell (ROM), das generische Gruppenmodell (GGM) und das algebraische Gruppenmodell (AGM), sind drei Beispiele für solche Abstraktionen: Sie vereinfachen viele Details von realen Hash-Funktionen und kryptografischen Gruppen, und wie Algorithmen mit diesen Primitiven interagieren können. Als Abstraktionen haben sie sich als außerordentlich erfolgreich bei der Rechtfertigung der Sicherheit vieler klassischer und moderner Kryptosysteme erwiesen, die sich ansonsten einer Analyse unter bekannten und weithin akzeptierten Annahmen entziehen. Allerdings sind diese Modelle auch mit Uninstanziierbarkeitsresultaten behaftet, was die Frage aufwirft, ob die unter ihnen analysierten Verfahren auf eine solidere Basis im Standardmodell gegründet werden können. In dieser Arbeit gehen wir dieser Frage aus zwei verschiedenen Blickwinkeln nach.

Im ersten Teil dieser Arbeit untersuchen wir ein kryptografisches Verfahren, dessen Sicherheit im ROM gerechtfertigt ist, dessen Sicherheitsbeweis jedoch auf einer besonderen Eigenschaft von Zufallsorakeln (Programmierbarkeit) beruht, die keine reale Hash-Funktion bietet. Dies wiederum stellt die Bedeutung des Beweises selbst infrage, da er nicht reproduziert werden kann, sobald auf die Abstraktion des ROMs verzichtet wird. Mehr noch: Wir beweisen, dass dieser Umstand inhärent ist, also dass ein ROM-Beweis für dieses Verfahren, der nicht auf diese künstliche Eigenschaft zurückgreift, wahrscheinlich nicht existiert. Wir zeigen anschließend, dass man das Verfahren so abändern kann, dass eine Reduktion möglich wird, die keine Programmierung des Zufallsorakels erfordert. Dies ist ein Beispiel dafür, wie man manchmal Systeme so anpassen kann, dass sie durch "bessere" heuristische Sicherheitsbeweise untermauert werden können und daher bevorzugt werden sollten, da sie "näher an der Realität" sind.

Im zweiten und dritten Teil dieser Arbeit führen wir neuartige Standardmodellannahmen für kryptografische Gruppen ein. Wir validieren diese Annahmen in geeigneten idealisierten Modellen und zeigen dann, wie sie verwendet werden können, um eine Reihe bestehender, praktischer Verfahren zu instanziieren, die zuvor nur im GGM oder im AGM als sicher bewiesen wurden. Diese Ergebnisse ermöglichen einen modularen Ansatz zu Sicherheitsbeweisen im GGM und im AGM, da unsere Definitionen eine zusätzliche "Ebene" zwischen den Modellen selbst und den Endanwendungen bilden. Unsere neu eingeführten Annahmen kombinieren Standardmodellanalysen mit der Anwendungsfreundlichkeit des entsprechenden idealisierten Modells, und machen in einigen Fällen sogar die Wiederverwendung bestehender Beweise möglich. Vor allem aber erlauben es die genannten Annahmen, die Sicherheit unserer Zielanwendungen im Standardmodell zu beweisen und sie damit von der Klasse der instanziierbaren Verfahren zu trennen.