CROSSING Research Seminar: A Random Oracle for All of Us

Organizer: Jacqueline Brendel, CROSSING

Abstract

We introduce the notion of a universal random oracle. Analogously to a classical random oracle it idealizes hash functions as random functions.

However, as opposed to a classical random oracle which is created freshly and independently for each adversary, the universal random oracle should provide security of a cryptographic protocol against all adversaries simultaneously. This should even hold if the adversary now depends on the random function. This reflects better the idea that the strong hash functions like SHA-2 and SHA-3 are fixed before the adversary decides upon the attack strategy.

Besides formalizing the notion of the universal random oracle model we show that the model is asymptotically equivalent to Unruh's auxiliary-input random oracle model (Crypto 2007). In Unruh's model the adversary receives some inefficiently computed information about the random oracle as extra input. Noteworthy, while security in the universal random oracle model implies security in the auxiliary-input random oracle model tightly, the converse implication introduces an inevitable security loss. This implies that the universal random oracle model provides stronger guarantees in terms of concrete security.

Validating the model we finally show, via a direct proof with concrete security, that a universal random oracle is one-way.

Speaker Bio

Felix Rohrbach is a PhD Student at the Cryptography and Complexity Theory Group at TU Darmstadt under the supervision of Prof. Marc Fischlin. His research interests focus on the necessary assumptions for different cryptographic primitives, including one-way functions and non-interactive zero-knowledge proofs.