Verifiable Random Oracles

Ziel dieser Arbeit ist es, Random Oracle zu instanziieren, ohne dabei Sicherheit zu verlieren,
die im Random Oracle Modell bewiesen wurde. Das dies mit Funktionsfamilien nicht geht
ist eine wohl bekannte Aussage, die zuerst von Halevi et al. (IACR’1998) gezeigt wurde. Wir
werden aus diesem Grund auf Interaktion zurückgreifen, aber versuchen, den erzeugten
Overhead möglichst zu reduzieren.
Um möglichst wenig zu Interagieren führen wir ein neues ideales Modell mit Namen
Verifiable Random Oracle ein. Dieses Modell bietet zusätzlich zum Random Oracle ein
Verifikations-Orakel, welches bei Eingabe (x, h) 1 ausgibt, falls RO(x) = h und anderenfalls
... mehr
0. Wir stellen danach zwei konkrete Instanziierungen für Verifiable Random Oracle vor,
von denen eine keine vertrauenswürdige Party benötigt. Zusätzlich reduzieren wir den
Netzwerk-Overhead (also die Gesamtgröße der verwendeten Nachrichten).
Wenn wir unsere Instanziierungen zusammen mit der Fiat-Shamir Transformation verwen-
den, bleibt die Simulation-Soundness Extractability Eigenschaft erhalten. Der Beweiser der
Fiat-Shamir Transformation verliert leider seine nicht-Interaktivität. Der Verifizierer bleibt
jedoch Nicht-interaktiv, da die Instanziierungen des Verifikations-Orakels nicht-interaktiv
sind. Die Beweise für diese Behauptungen bilden einen signifikanten Teil dieser Arbeit.

The goal of this thesis is to instantiate random oracles without losing security proven
in the random oracle model. It is well known that this is not possible with any function
family, as first shown by Halevi et al. (IACR’1998). Therefore, we will resort to interaction,
but reduce the overhead created by it as well as we can.
In order to keep the interaction needed to a minimum, we introduce a novel ideal model
called verifiable random oracle model. In addition to a random oracle RO, this model
also includes a verification oracle, which for input (x, h) returns 1 if RO(x) = h and 0
... mehr
otherwise. We then continue to present two concrete instantiations for verifiable random
oracles, one of which does not use trusted parties. Additionally, we reduce the network
overhead (i.e. combined message size needed).
When used with the Fiat-Shamir transformation, these instantiations preserve the simula-
tion-sound extractability property. The prover of the Fiat-Shamir transformation unfortu-
nately loses its non-interactivity. However, the verifier remains non-interactive, as the
instantiations for the verify oracle are non-interactive. The proofs for these claims make
up a significant part of this thesis.