From Indifferentiability to Constructive Cryptography (and Back)
The concept of indifferentiability of systems, a generalized form of indistinguishability, was proposed in 2004 to provide a simplified and generalized explanation of impossibility results like the non-instantiability of random oracles by hash functions d
- PDF / 321,670 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 191 Views
Department of Computer Science, ETH Zurich, Zurich, Switzerland [email protected] 2 Department of Physics, ETH Zurich, Zurich, Switzerland [email protected]
Abstract. The concept of indifferentiability of systems, a generalized form of indistinguishability, was proposed in 2004 to provide a simplified and generalized explanation of impossibility results like the noninstantiability of random oracles by hash functions due to Canetti, Goldreich, and Halevi (STOC 1998). But indifferentiability is actually a constructive notion, leading to possibility results. For example, Coron et al. (Crypto 2005) argued that the soundness of the construction C(f ) of a hash function from a compression function f can be demonstrated by proving that C(R) is indifferentiable from a random oracle if R is an ideal random compression function. The purpose of this short paper is to describe how the indifferentiability notion was a precursor to the theory of constructive cryptography and thereby to provide a simplified and generalized treatment of indifferentiability as a special type of constructive statement.
1
Introduction
An important abstraction in cryptography, introduced by Bellare et al. [4], is the so-called random oracle model (ROM). A random oracle is an idealized resource or system available to all involved parties, with parameters m and n, which behaves as if it contained a uniformly chosen function table F : {0, 1}m → {0, 1}n and, for every query x ∈ {0, 1}m from any party, provides the function value F (x) to that party. Other parties do not see the query x nor the reply F (x). A random oracle can also be defined for the countably infinite domain {0, 1}∗ of all finite-length input strings, the resource usually meant in cryptography by the term “random oracle”. The idea behind the ROM is a natural decomposition idea often arising in cryptographic reasoning. On one hand one tries to construct, at least approximately, a random oracle from weaker resources (e.g. a shared random string), and on the other hand one uses the idealized resource of a random oracle to design secure protocols. The rationale is that if a well-designed hash function can be assumed to behave like a random oracle, then a cryptographic protocol proved secure in the ROM remains secure when the random oracle is replaced c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part I, LNCS 9985, pp. 3–24, 2016. DOI: 10.1007/978-3-662-53641-4 1
4
U. Maurer and R. Renner
by a hash function, thus composing two steps of reasoning. Analogous reasoning is, for example, applied if one proves a scheme secure assuming it has access to a uniformly random value (e.g., a shared secret key), and then argues that the random value can be replaced by a pseudo-random value without compromising security. Two questions arise. 1. What exactly do we mean by composition of steps in the above reasoning and how can we make it mathematically sound? It turns out, as discussed in this paper, that the random oracle example requires a different and
Data Loading...
