Universally Composable Verifiable Random Oracles

Random Oracles werden häufig in der Kryptographie eingesetzt um sehr effiziente Instanziierungen mächtiger kryptographischer Primitive zu konstruieren. Jedoch ist diese Praxis im Allgemeinen nicht zulässig wie verschiedene Nicht-Instanziierungs-Ergebnisse für Random Oracles mittels lokal berechenbarer Familien von Funktionen durch Halevi et al. (JACM ’04) zeigt.

Die Random Oracle Modell kann sicher eingesetzt werden, indem Random Oracles nicht mit einer lokal berechenbaren Hashfunktion, sondern stattdessen mit einem interaktiven Protokoll instanziiert werden. In der realen Welt könnte solch ein interaktives Protokoll beispielsweise aus einem vertrauenswürdigen Server, welcher über das Internet erreichbar ist, bestehen. ... mehrDieser Server würde sodann eine der bekannten Techniken wie lazy sampling oder das Auswerten einer Pseudo-Zufälligen Funktion verwenden, um die Funktionalität eines Random Oracle bereitzustellen.

Ein klarer Nachteil dieses Ansatzes ist die große Menge an Interaktion, die bei jeder Berechnung, die eine Auswertung des Random Oracle beinhaltet, nötig ist. Wir wollen diese Interaktion auf ein Minimum reduzieren. Um obiges Unmöglichkeitsresultat zu umgehen, muss die Auswertung des Random Oracle auf einer frischen Eingabe Interaktion der auswertenden Partei mit einer anderen Partei beinhalten. Dies ist jedoch nicht der einzige Verwendungszweck von Random Oracles, der häufig in kryptographischen Protokollen auftritt. Bei einem weiteren solchen Zweck wertet zunächst eine Partei A das Orakel auf einer Eingabe aus und erhält einen Hashwert. Im Anschluss sendet A Eingabe und Ausgabe (im Kontext eines Protokolls) an eine zweite Partei B und möchte B davon überzeugen, dass das Random Oracle korrekt ausgewertet wurde. Eine einfache Möglichkeit dies zu prüfen besteht darin, dass B selbst eine Auswertung des Random Oracle auf der erhaltenen Eingabe tätigt und die beiden Ausgaben vergleicht. In unserem Kontext benötigt dies jedoch erneut Interaktion.

Der Wunsch diesen zweiten Verwendungszweck nicht-interaktiv zu machen führt uns zum Begriff eines Verifiable Random Oracle (VRO) als Erweiterung eines Random Oracle. Abstrakt besteht ein VRO aus zwei Orakeln. Das erste Orakel verhält sich wie ein Random Oracle dessen Ausgabe um einen Korrektheitsbeweis erweitert wurde. Mit Hilfe dieses Beweises kann das zweite Orakel dazu verwendet werden öffentlich die korrekte Auswertung des Random Oracle zu verifizieren. Obwohl diese Orakel-basierte Formulierung nicht notwendigerweise nicht-interaktive Verifikation besitzt, so erlaubt jedoch die Einführung expliziter Korrektheitsbeweise dies.

In dieser Masterarbeit formalisieren wir zunächst den Begriff eines VRO im Universal Composability Framework von Canetti (FOCS ’01). Danach wenden wir VROs auf zwei kryptographische Anwendungen an, die in ihrer ursprünglichen Formulierung das Random Oracle Modell verwenden, und zeigen, das deren Sicherheitseigenschaften erhalten bleiben. Um zu zeigen, dass unsere Definition realisierbar ist, konstruieren wir mehrere Protokolle, die die ideale VRO Funktionalität realisieren. Diese reichen von Protokollen für eine einzelne vertrauenswürdige Partei bis hin zu verteilten Protokollen, die eine gewisse Menge an böswilliger Korruption erlauben. Wir vergleichen weiterhin VROs mit ähnlichen existierenden Primitiven.

Random Oracles are frequently used in cryptography to construct very efficient instantiations of powerful cryptographic primitives. Nevertheless, this practice is not sound in general as the uninstantiability result by Halevi et al. (JACM ’04) for random oracles by any function family shows.

The Random Oracle Model can be made sound by instantiating the random oracle not with a locally computable hash-function, but by using an interactive protocol. In reality, such an interactive protocol may involve a trusted server that is reachable at some address over the internet. ... mehrThis server could use one of the usual techniques such as lazy sampling or the evaluation of a pseudo-random function to provide the random oracle.

One obvious drawback of this approach is a large amount of interaction each time a random oracle output is involved in some computation. We want to reduce this interaction to a minimum. First, it is clear that to circumvent the impossibility result from above, a party holding some input and wishing to know the corresponding random oracle output has to interact with another party in some way. This is, however, not the only way in which random oracles are commonly used within cryptographic protocols. Another use case first has a party A query the oracle on some input, thereby receiving a hash. A subsequently sends both input and hash (all in the context of some protocol) to a second party B and wants to convince B of the fact that the oracle has been queried correctly. A simple way for B to check correctness is to simply recompute the hash, but in our setting, this entails interaction.

The wish to allow this second use case to be non-interactive leads to the notion of a Verifiable Random Oracle (VRO) as an augmentation of a random oracle. Abstractly, a VRO consists of two oracles. The first part behaves like a random oracle whose output is augmented with a proof of correct evaluation. Using this proof, the second oracle can be used to publicly verify the correct evaluation of the random function. While this formulation does not inherently force verification to be non-interactive, the introductionof explicit proofs does at least allow for it.

In this thesis, we first formalize the notion of a VRO in the Universal-Composability framework of Canetti (FOCS ’01). We then apply VROs to two cryptographic applications formulated in the Random Oracle Model and show that they remain sound. To show that our definition is sensible, we give several protocols realizing the ideal VRO functionality ranging from protocols for a single trusted party to distributed protocols allowing for some malicious corruption. We also compare VROs to existing primitives.