[MA] Universally Composable Verifiable Random Oracles

Hybrid: Geb. 50.34, Raum 252 oder https://i62bbb.tm.kit.edu/b/mic-7xx-rfr

2022-10-18

Tim Scheurer

15:45

Random oracles are frequently used to produce very efficient instantiations of powerful cryptographic primitives. Nevertheless, this practice is not sound in general as the uninstantiability result for random oracles by any local function-family shows.

The random oracle methodology 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 which is reachable at some address over the internet. This server could use one of the usual techniques such as lazy sampling or the evaluation of a pseudorandom function to provide the random oracle.

One obvious drawback of this approach is the 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 resulting 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 correct evaluation of the random function. While this formulation does not inherently force verification to be non-interactive, the introduction of explicit proofs does at least allow for it.

In this thesis, we first formalise 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 ROM and show that they remain sound. To show that our definition is sensitive, 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.