Proving Upper and Lower Bounds in Cryptography via Oracles

Provable security is a cornerstone of modern cryptography: Due to ubiquitous and diverse applications of cryptography, a proof of security gives us the necessary confidence to deploy a cryptographic protocol. In most cases, such a security proof comes in the form of a black-box reduction, which bases the security of a potentially complex protocol on a small set of simple and abstract assumptions that are much easier to analyse.

However, proving a black-box reduction can be quite complicated, and we do not have proofs for every protocol used in practice. Here, analysing the protocols relative to oracles, a technique from computational complexity theory, can provide insights: Oracles provide the ability to compute functionalities in one computational step that otherwise might not be efficiently computable, e.g., provide access to a truly random function or solve any NP-complete problem. These oracles now allow us to replace some parts in the protocol with abstract, idealized primitives that are easier to analyse, e.g., to replace a one-way function with a truly random function. In this thesis, we utilize oracles in two different ways.

In the first part, we use oracles to prove lower bounds for cryptographic primitives, i.e., showing that certain assumptions are not sufficient to build this primitive securely. The essential idea here, going back to Impagliazzo and Rudich, is to replace the assumption with an oracle, i.e., replacing a one-way function with a truly random function, and then showing that relative to this oracle, it is impossible to build the primitive. From this impossibility result relative to the oracle, we can now conclude that the primitive cannot be built from the assumption in a black-box way. We use this technique to prove a lower bound on the efficiency of constructing strong from weak one-way functions, to show that we cannot construct collision-resistant hash functions from distributional collision-resistant hash functions in a fully black-box way, and to prove that extremely lossy functions cannot be built from a large class of symmetric primitives in a black-box way.

In the second part of this thesis, we use oracles as idealized models that can be used to provide heuristic security arguments for protocols.These idealized models, starting with the random oracle model (short ROM) introduced and defined by Fiat and Shamir as well as Bellare and Rogaway, were motivated by the existence of very efficient cryptographic protocols used in practice, but for which no proof of security existed. Using idealized models, it was now possible to give at least a heuristic security argument for them. In this thesis, we first focus on the common random string model, an idealized model introduced to circumvent impossibility results for non-interactive zero-knowledge proofs. We show how to reuse a single common random string for polynomially many non-interactive statistical zero-knowledge arguments, as well as analyze the relation between different soundness definitions used in literature. In a second result, we introduce an alternative notion for the ROM, the universal random oracle model, which brings this idealized model closer to reality.

Beweisbare Sicherheit ist ein Grundpfeiler moderner Kryptographie: Wegen der allgegenwärtigen und vielseitigen Verwendung von Kryptographie ist ein Sicherheitsbeweis essentiell, um das notwendige Vertrauen in ein kryptografisches Protokoll herzustellen. In den meisten Fällen hat ein solcher Beweis die Form einer Black-Box-Reduktion, in der die Sicherheit des potenziell komplexen Verfahrens auf eine kleine Menge von einfacheren Annahmen reduziert wird, welche dann ihrerseits besser zu untersuchen sind.

Eine solche Reduktion zu beweisen kann jedoch kompliziert sein, und nicht für jedes Protokoll, welches in der Praxis eingesetzt wird, kennen wir einen Beweis. Daher kann es aufschlussreich sein, die Protokolle relativ zu einem Orakel zu analysieren: Ein Orakel erlaubt es, bestimmte Funktionalitäten in einem logischen Schritt zu berechnen, die ansonsten potenziell nicht effizient berechenbar wären, wie zum Beispiel der Zugriff auf eine echt zufällige Funktion oder die Lösung eines jeden NP-Problems. Diese Orakel ermöglichen es, bestimmte Teile des Protokolls mit abstrakten, idealisierten Primitiven zu ersetzen, die einfacher zu analysieren sind, beispielsweise könnte man eine One-Way-Funktion mit einer echt zufälligen Funktion ersetzen. In dieser Thesis verwenden wir Orakel auf zwei verschiedene Weisen:

In ersten Teil der Thesis verwenden wir Orakel, um untere Schranken für die Konstruktion von kryptografischen Primitiven zu beweisen, das heißt, wir zeigen, dass bestimmte Annahmen nicht ausreichend sind, um dieses Primitiv sicher zu konstruieren. Die grundlegende Idee hierfür geht auf Impagliazzo und Rudich zurück, die die Annahme durch ein Orakel ersetzt haben, also beispielsweise eine One-Way-Funktion durch eine echt zufällige Funktion, um dann im nächsten Schritt zu zeigen, dass es unmöglich ist, das kryptografische Primitiv relativ zu dem Orakel zu bauen. Basierend auf dieser unteren Schranke relativ zum Orakel kann man nun schließen, dass es keine Black-Box-Konstruktion des Primitives von den ersetzten Annahmen geben kann. Wir verwenden diese Technik in drei Resultaten: Wir zeigen eine untere Schranke für die Effizienz von Konstruktionen von starken One-Way-Funktionen basierend auf schwachen One-Way-Funktionen; wir beweisen, dass es keine Fully-Black-Box-Konstruktionen von Collision-Resistant Hash Functions basierend auf Distributional Collision-Resistant Hash Functions geben kann; und wir zeigen, dass es keine Black-Box-Konstruktion von Lossy Functions basierend auf einer großen Menge von symmetrischen Primitiven geben kann.

Im zweiten Teil der Thesis nutzen wir Orakel als idealisierte Modelle, welche verwendet werden, um heuristische Sicherheitsargumente für kryptografische Protokolle zu erstellen. Beginnend mit dem Random Oracle Model, eingeführt von Fiat und Shamir sowie Bellare und Rogaway, wurden diese idealisierten Modelle durch die Existenz von Protokollen motiviert, welche effizient waren und in der Praxis eingesetzt wurden, für die jedoch kein Sicherheitsbeweis existierte. Mit Hilfe der Modelle war es jetzt möglich, zumindest ein heuristisches Sicherheitsargument für diese Protokolle zu erstellen. In dieser Thesis betrachten wir zunächst das Common Random String Model, ein Modell, welches das Umgehen von Unmöglichkeitsresultaten bei nicht-interaktiven Zero-Knowledge-Beweisen ermöglicht. Weiterhin untersuchen wir in diesem Resultat verschiedene Korrektheitsdefinitionen, die in der Literatur existieren. In einem zweiten Resultat führen wir eine Alternative zum Random Oracle Model ein, das Universal Random Oracle Model, welches im Vergleich die Realität besser abbildet.