Proving Upper and Lower Bounds in Cryptography via Oracles

Abstract

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.