Security Definitions for Hash Functions: Combining UCE and Indifferentiability

Abstract

Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression function. However, it is well known that no hash function realizes a random oracle and no real compression function realizes an ideal one.

As an alternative to the ROM, Bellare et al. recently proposed the notion of universal computational extractors (UCE). This notion formalizes that a family of functions “behaves like a random oracle” for “real-world” protocols while avoiding the general impossibility results. However, in contrast to the indifferentiability framework, UCE is formalized as a multi-stage game without clear composition guarantees.

As a first contribution, we introduce context-restricted indifferentiability (CRI), a generalization of indifferentiability that allows us to model that the random oracle does not compose generally but can only be used within a well-specified set of protocols run by the honest parties, thereby making the provided composition guarantees explicit. We then show that UCE and its variants can be phrased as a special case of CRI. Moreover, we show how our notion of CRI leads to generalizations of UCE. As a second contribution, we prove that the hash function constructed by Merkle-Damgåd satisfies one of the well-known UCE variants, if we assume that the compression function satisfies one of our generalizations of UCE, basing the overall security on a plausible assumption. This result further validates the Merkle-Damgård construction and shows that UCE-like assumptions can serve both as a valid reference point for modular protocol analyses, as well as for the design of hash functions, linking those two aspects in a framework with explicit composition guarantees.

1 Introduction

1.1 Motivation and Background

The random oracle model (ROM) [3] is an important tool towards establishing confidence in the security of real-world cryptographic constructions. The paradigm can be described in two steps: first, to design a protocol and prove it secure in the ROM, thus using a random oracle instead of a hash function; second, to instantiate the random oracle with a cryptographic hash function. However, it is well known [10] that no hash function realizes a random oracle; hence, once the random oracle is instantiated the security proof degenerates to a heuristic security argument.

The ROM is not only used as a model to prove protocols in, but it also serves as a reference point for the designers of hash functions. The indifferentiability framework [16], while being a general framework, is most famously used to phrase the security obligation of a hash function construction: the hash function is proven indifferentiable from a random oracle when using an ideal compression function (e.g. a fixed input-length random oracle), thereby excluding attacks exploiting the construction. Since indifferentiability is equipped with a composition theorem, this guarantee holds moreover irrespective of the context the hash function is used in. However, just as no hash function can instantiate a random oracle, no real compression function can instantiate the idealized version assumed in the proof.

More recently, Bellare et al. [2] proposed the notion of universal computational extractors (UCE). This notion is based on the observation that for most “real-world” protocols proven secure in the random oracle model, instantiating the random oracle with a concrete hash function is not known to be insecure. The UCE framework revisits the question of what it means for a hash functions to “behave like a random oracle” and formalizes families of security notions aimed at bridging the gap between the general impossibility result and the apparent security of concrete protocols. So far, the research on the UCE framework has mainly been focused on two aspects: first, studying in which applications the ROM can be safely replaced by one of the UCE assumptions and, second, studying which ones of the UCE assumptions are generally uninstantiable and which one might actually be. Little attention, however, has been paid analyzing common hash function constructions within the UCE framework. Moreover, UCE is formalized as a multi-stage game without clear composition guarantees, which makes it therefore hard to directly apply as a modular step in an analysis of a complex protocol.

1.2 Contributions

Our contributions are three-fold. First, we introduce a generalization of indifferentiability called context-restricted indifferentiability (CRI). This generalization allows us to model that a resource cannot be instantiated in every context but only within a well-specified set of contexts. We then mainly apply the general context-restricted indifferentiability framework to the random oracle, called random-oracle context-restricted indifferentiability (RO-CRI) security.

Secondly, we show that every UCE-class, i.e., every variant of the original UCE framework introduced by Bellare et al., can be expressed as a set of non-interactive contexts in which the random oracle can be instantiated. Hence, we prove that the UCE framework can be translated to RO-CRI and, thus, is essentially a special case of it. Thereby we propose an alternative interpretation of the UCE framework in a traditional single-stage adversary model with well-defined composition guarantees and provide a direct relation between the UCE and the indifferentiability frameworks. In the full version [14] we furthermore show how two of the generalizations of UCE can be expressed within RO-CRI as well. Viewing UCE as a special case of CRI then allows us to generalize the split-source UCE-class to non-interactive contexts and we propose in particular a generalization that we call strong-split security.

Finally, we propose to consider CRI to analyze the security of common hash-function constructions. In contrast to indifferentiability, CRI allows us to consider more fine-grained versions of both the assumption on the compression function as well as the guarantee of the constructed hash function. As an example, we investigate the split-security of the Merkle-Damgård scheme using RO-CRI and we prove that the constructed hash function is split-secure if the underlying compression function is strong-split secure (as opposed to the usual much stronger assumption of the compression function being a random function) if the hashed message has a sufficient min-entropy density from the distinguisher’s point of view. We thereby generalize a lemma on min-entropy splitting by Damgård et al., which we believe might be of independent interest.

1.3 Related Work

We discuss the relation between context-restricted indifferentiability and some related notions, including variants of indifferentiability and UCE.

Variants of Indifferentiability. Several variants of indifferentiability have been proposed in the past. The reset indifferentiability notion has been introduced by Ristenpart, Shacham, and Shrimpton in [20] as a workaround to the composition problems in multi-stage settings they highlighted. In [12], Demay et al. gave an alternative interpretation of those shortcomings. They prove that reset indifferentiability is equivalent to indifferentiability with stateless simulators. Moreover, they introduce the notion of resource-restricted indifferentiability, which makes the memory used in the simulator explicit in contrast to the original definition which only requires this memory to be polynomially bounded. In contrast to our CRI notion that weakens indifferentiability, those two variants are a strengthening, i.e., any statement in those frameworks implies the traditional indifferentiability statement, but not vice-versa.

In [19], Mittelbach presents a condition called unsplittability on multi-stage games, that allows to show that the composition theorem of indifferentiability can be salvaged for iterative hash function constructions. They formalize a condition that specifies certain multi-stage games, in which the random oracle can be safely instantiated by an iterated hash function based on an idealized compression function. In contrast, CRI formalizes in which single-stage settings a hash function might be instantiable by an actual hash function, without having to assume an unrealistically ideal compression function. Moreover, CRI is a general paradigm that not only applies to iterative hash function constructions.

Universal Computation Extractors and Variants Thereof. The UCE framework was introduced by Bellare et al. [1] as a tool to provide a family of notions of security for keyed hash functions, refining the predominant random oracle methodology. Since then, the impossibility of various UCE-classes has been shown by Brzuska et al. [6, 8] and Bellare et al. [4], and the possibility of a specific UCE-class in the standard model has been shown by Brzuska and Mittelbach [7]. Bellare et al. [2] have also suggested to use the UCE framework to study the domain extension of a finite input-length random oracle to a UCE secure variable input-length random oracle. Their motivation is based on finding more efficient constructions if they only require the UCE-security of the variable input-length random oracle. In contrast, we consider the domain extension in a setting where we also assume the compression function to be only UCE secure.

In [13], Farshim and Mittelbach introduced a generalization of UCE called interactive computational extractors (ICE). Generalizing UCE to interactive scenarios is also one of our contributions. The generalization they propose and the one we propose, however, differ on a very fundamental level and pursue different directions. ICE makes the two stages of the original UCE definition symmetrical where the two stages jointly form the queries, requiring that neither one of them can predict the query. In contrast, we exactly use the asymmetry of UCE to embed it in the traditional indifferentiability setting with one dishonest and one honest party, where naturally the honest party knows the position where it queries the hash function.

In [21], Soni and Tessaro introduce the notion of public-seed pseudorandom permutations (psPRP) that are inspired by UCE. In fact, they introduce a generalization of UCE, called public-seed pseudorandomness, of which both psPRP and UCE are instantiations. For their psPRP notion they introduce the unpredictability and reset-security notions analogous to UCE, and moreover they study the relations between psPRP and UCE. In contrast to CRI, their definition is still purely game-based. In the full version [14], we show that CRI is a strict generalization of their notion as well.

2 Preliminaries

2.1 The (Traditional) UCE Framework

To circumvent the well-known impossibility result that no hash function family is indifferentiable from a random oracle, Bellare, Hoang, and Keelveedhi [2] introduced the UCE framework to formalize a weaker version of what it means for a family of keyed hash functions to behave like a random oracle. The UCE framework defines a two-stage adversary, where only the first stage—the source S—has access to the oracle (either the hash function or the random oracle) and only the second stage—the distinguisher D—has access to the hash key hk. The source provides some leakage L to the distinguisher that then decides with which system the source interacted. The definition of the security game is presented in Algorithm 1. Here, $\mathrm {H.Kg}$ denotes the key-generation algorithm, $\mathrm {H.Ev}$ the deterministic evaluation algorithm, and l the output length associated with the family of hash functions H.

Without any further restriction, this game is trivial to win: the source queries some point x, obtains the result y, and then provides the tuple (x, y) as leakage to the distinguisher which then decides whether y matches with the hash of x. Therefore, in order for this definition to be meaningful, the leakage has to be restricted in some sense, which gives rise to various UCE-classes depending on the kind of restriction. The basic restriction proposed was that the queries of the source S must be unpredictable given the leakage L. Both statistical unpredictability as well as computational unpredictability have been proposed; however, the latter has been shown to be impossible assuming iO exists [6].

2.2 Resources and Converters

The indifferentiability framework by Maurer, Renner, and Holenstein [16] is a widely adopted framework to analyze and prove the security of hash function constructions. The indifferentiability framework is a simulation-based framework that uses the so-called “real world – ideal world” paradigm and formalizes security guarantees as resources (analogous to functionalities in the Universal Composability framework [9]). A resource $\mathsf {S}$ captures the idea of a module which provides some well-defined functionality to the different parties–both the honest and the dishonest ones–which can then be used in a higher level protocol. A resource can either be something physically available, such as an insecure communication network, or can be constructed from another resource $\mathsf {R}$ using a cryptographic protocol $\pi$. In fact, the goal of the protocol $\pi$ can be seen as constructing the ideal resource $\mathsf {S}$ from the real one $\mathsf {R}$ assumed to be available. The protocol is modeled as a converter that connects to the system $\mathsf {R}$.

The indifferentiability framework formalizes this concept in a setting with a single honest and a single dishonest party. In the following we give a brief description of the system algebra used in this work. We basically follow the contemporary notation of indifferentiability presented in [18], while sticking to the original reducibility notion.

Formal Definitions. A resource is a system with two interfaces via which the resource interacts with its environment. The (private) interface $\mathtt {A}$ and the (public) interface $\mathtt {E}$ can be thought as being assigned to an honest and a dishonest party, respectively. Let $\varPhi$ denote the set of resources. All resources in $\varPhi$ are outbound (as in the original version of indifferentiability) meaning that interaction at one interface does not influence the other interface. If two resources $\mathsf {V}$ and $\mathsf {W}$ are used in parallel, this is again a resource, denoted $[\mathsf {V, W}]$, where each of the interfaces allows to access the corresponding interfaces of both subsystems. Moreover, we assume the existence of a resource $\square \in \varPhi$ such that $[\mathsf {R, \square }] = \mathsf {R}$ for any $\mathsf {R}$.

Converters are systems that can be connected to an interface of a resource to translate the inputs and outputs. A converter has two interfaces: the outer interface $\mathtt {out}$ that becomes the new interface of the resource, and the inner interface $\mathtt {in}$ that is connected to the interface of the existing resource. Attaching a converter $\pi$ to a specific interface of a resource $\mathsf {R}$ yields another resource. We understand the left and the right side of the symbol $\mathsf {R}$ as the interface $\mathtt {A}$ and $\mathtt {E}$, respectively; thus, attaching $\pi$ at interface $\mathtt {A}$ is denoted $\pi \mathsf {R}$ and attaching it at interface $\mathtt {E}$ is denoted $\mathsf {R} \pi$. Let $\varSigma$ denote the set of converters. Two converters $\phi$ and $\psi$ can be composed sequentially and in parallel: sequential composition is denoted as $\phi \circ \psi$ such that $(\phi \circ \psi ) \mathsf {R} = \phi (\psi \mathsf {R})$ and parallel composition as $[\phi , \psi ]$, where $[\phi , \psi ] [\mathsf {R, S}] = [\mathsf {\phi R, \psi S}]$. Moreover, we assume the existence of an identity converter $\mathsf {id}_{\mathsf {}}$ such that $\mathsf {id}_{\mathsf {}} \mathsf {R} = \mathsf {R}\, \mathsf {id}_{\mathsf {}} = \mathsf {R}$.

Conventions for Describing Systems and Algorithms. We describe our systems using pseudocode. The following conventions are used: We write $x \leftarrow y$ for assigning the value y to the variable x. For a finite set $\mathcal {X}$, $x \overset{\$}{\leftarrow }\mathcal {X}$ denotes assigning x uniformly at random a value in $\mathcal {X}$. Furthermore, $x \overset{\mathsf {P}_{X}}{\leftarrow } \mathcal {X}$ denotes sampling x according to the indicated probability distribution $\mathsf {P}_{X}$ over $\mathcal {X}$.

Queries (also called inputs) to systems consist of a list of arguments, of which the first one is a suggestive keyword. If the input consists only of the keyword we omit the parenthesis, i.e., we write $\texttt {retrieve}$ or $(\texttt {hash, x})$. When specifying the domain of the inputs, we ignore the keyword and write $(\texttt {hash, x}) \in \mathcal {X}$ to indicate $x \in \mathcal {X}$. If a system outputs a value x at the interface named ${\mathtt {int}}$, we denote this “ at ${\mathtt {int}}$”. We generally assume that all resources reply at the same interfaces they have been queried before processing any additional queries. Therefore, if a converter outputs a query at its inside interface, we write “let var denote the result” meaning that we wait for the value returned from the connected system and then store it in the variable var.

2.3 Indifferentiability

In contrast to game-based security definitions, indifferentiability gives composable security guarantees, i.e., the security guarantees obtained are not only with respect to specific attack scenarios but with respect to all possible attacks. The fundamental idea of composition is then to prove the construction of $\mathsf {S}$ from $\mathsf {R}$ in isolation and be assured that in any higher level protocol $\phi$ making use of $\mathsf {S}$, the resource $\mathsf {S}$ can be replaced with $\mathsf {R}$ with the protocol applied, without degrading the security of $\phi$. The system $\mathsf {S}$, while not existing in the real world, therefore serves as an abstraction boundary for the design of cryptographic schemes (Fig. 1).

Indifferentiability formalizes this by demanding that there exists an efficient simulator $\sigma$, such that the real setting $\pi \mathsf {R}$ and the ideal setting $\mathsf {S} \sigma$ are indistinguishable according to the following definitions.

Definition 1

The advantage of D in distinguishing $\mathsf {R}$ and $\mathsf {S}$ is defined as

where $\mathsf {D} \mathsf {S}$ denotes the output of the distinguisher $\mathsf {D}$ when connected to the resource $\mathsf {S}$. The distinguisher thereby gets access to both interfaces of the resource $\mathsf {S}$. Moreover, let $\mathsf {R} \approx \mathsf {S}$ denote that $\varDelta ^{\mathsf {D}}(\mathsf {R},\mathsf {S})$ is negligible for every efficient $\mathsf {D}$.

Definition 2

(Indifferentiability). Let $\mathsf {R}$ and $\mathsf {S}$ be 2-interface resources. $\mathsf {S}$ is reducible to $\mathsf {R}$ by $\pi \in \varSigma$ in the sense of indifferentiability (denoted ), if

where we refer to $\pi$ and $\sigma$ as the protocol and the simulator, respectively.

Fig. 1.

The real (left) and the ideal (right) setting considered in indifferentiability. We depict resources using rectangular boxes and converters using rounded boxes. The honest party’s interface is depicted on the left, and the dishonest’s on the right side.

The formalism of indifferentiability composes in the natural way under some standard closure assumptions¹ on the sets $\varSigma$ and $\mathcal {D}$ of converters and distinguishers considered. First, if $\mathsf {T}$ is reducible to $\mathsf {S}$ and $\mathsf {S}$ is reducible to $\mathsf {R}$, then $\mathsf {T}$ is reducible to $\mathsf {R}$ by the composed protocol. Secondly, if $\mathsf {S}$ is reducible to $\mathsf {R}$, then for any resource $\mathsf {U}$, $[\mathsf {S,U}]$ is reducible to $[\mathsf {R,U}]$. More formally, for any resources $\mathsf {R}$, $\mathsf {S}$, $\mathsf {T}$, and $\mathsf {U}$ we have the following two conditions:

3 Context-Restricted Indifferentiability

In this section we first revisit the motivation behind composable frameworks such as the indifferentiability framework. To handle cases where fully composable security is unachievable, we then introduce the notion of context-restricted indifferentiability, a single-stage security definition inspired by the original motivation behind the UCE-framework. In fact, in the next section we then prove that UCE can be seen as a special case of context-restricted indifferentiability.

3.1 The Limitations of General Composability

At the heart of every composable cryptographic framework, such as indifferentiability, lies the concept of a resource (called functionality in the UC framework). A resource $\mathsf {S}$ captures the idea of a module which provides some well-defined functionality to the different parties–both the honest and the dishonest ones–which can then be used in a higher level protocol. The goal of a protocol $\pi$ is then phrased as constructing the resource $\mathsf {S}$ from an assumed resource $\mathsf {R}$ and the fundamental idea of composition is to prove the construction of $\mathsf {S}$ from $\mathsf {R}$ in isolation and be assured that in any environment, the resource $\mathsf {S}$ can be replaced with $\pi \mathsf {R}$, without degrading the security. This allows for a modular approach, since the construction of the resource $\mathsf {S}$ can be considered entirely independent of its use.

The modular approach of indifferentiability, however, fails if we use a resource $\mathsf {S}$ which cannot be reduced to any $\mathsf {R}$ available in the physical world, such as the random oracle. Let $\mathsf {PO}$ denote a public random oracle resource, and $\mathsf {HK}$ a public hash key resource. Then, the famous impossibility result [10] implies, that there exists no deterministic and stateless protocol $\mathsf {h}_{\mathsf {}}$, implementing a hash function, such that , i.e., such that the hash function reduces the random oracle to the public hash key.

Traditionally, such an impossibility result is circumvented by weakening the guarantees $\mathsf {S}$, and instead consider a restricted variant $\mathsf {S'}$. However, for the random oracle, and many other examples, no such natural weakened version exists. As a second approach, one can restrict the class of distinguishers allowed. The UCE framework is such an approach. Unless there is an application scenario where one can justify such a restricted attacker, this approach leads, however, to security definitions without evident semantics. The original motivation of the UCE framework, though, has not been to consider restricted adversaries but to phrase that, in contrast to the impossibility results, real-world protocols use the random oracle in “sensible” ways. In the following, we turn this motivation into a third approach: We restrict composition in a well-defined way. If there is a resource $\mathsf {S}$ that cannot be reduced to a resource $\mathsf {R}$ in all contexts, we propose to make explicit in which contexts one can do it.

3.2 Context-Restriction

In this section we formally define the idea of restricting composition. In order to do so, we define a context in which we allow the resource $\mathsf {S}$ to be used. A context consists of an auxiliary parallel resource $\mathsf {P}$ and some converter $\mathsf {f}_{\mathsf {}}$ applied by the honest party. We usually call this converter $\mathsf {f}_{\mathsf {}}$ a filter to indicate that its goal is to restrict the access to the resource $\mathsf {S}$. To obtain general statements, we consider a set of contexts instead of a single one. This set should be general enough to capture many application scenarios but avoid those for which the impossibility is known.

Definition 3

A context set $\mathcal {C}$ is a subset of $\varSigma \times \varPhi$, where $\varSigma$ denotes the set of all converters and $\varPhi$ denotes the set of all resources.

Recall that our goal is to make a modular statement: reducing $\mathsf {S}$ to another resource $\mathsf {R}$ in each of these contexts in $\mathcal {C}$, i.e., finding a single resource $\mathsf {R}$ and protocol $\pi$ such that $\pi \mathsf {R}$ can instantiate $\mathsf {S}$ in each of these contexts in $\mathcal {C}$. Therefore, the same context appears in both the real and the ideal setting. See Fig. 2 for an illustration of the distinction problem when fixing a specific context. Quantifying over all contexts of a set leads to the following definition of context-restricted indifferentiability.

Fig. 2.

The real (left) and the ideal (right) setting considered in context-restricted indifferentiability for a specific context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$ consisting of the filter $\mathsf {f}_{\mathsf {}}$ and the auxiliary parallel resource $\mathsf {P}$.

Definition 4

Let $\mathcal {C} \subseteq \varSigma \times \varPhi$ be a given set of contexts, and let $\mathsf {R}$ and $\mathsf {S}$ be 2-interface resources. We define $\mathsf {S}$ to be $\mathcal {C}$-restricted reducible to $\mathsf {R}$ by $\pi \in \varSigma$ in the sense of indifferentiability (denoted ), as

and refer to the converters $\pi$ and $\sigma$ as the protocol and the simulator, respectively.

3.3 Composition

Composability generally refers to the property of a framework that from one, or multiple, given statements, new ones can be automatically deduced in a sound way without having to reprove them. More concretely, in CRI we are interested in deducing new reducibility statements from given ones. Using the abstract algebraic approach of constructive cryptography [15, 17], such composition properties are usually consequences of composition-order invariance, a natural associativity property stating that the order in which we connect systems is irrelevant.

Before stating the composition theorem, we first observe that when a resource $\mathsf {S}$ is reduced to $\mathsf {R}$ in a context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$, the overall environment of $\mathsf {S}$ actually consists of both $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$ and the distinguisher. Especially, if $\mathsf {S}$ can be reduced to $\mathsf {R}$ within $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$, so can it within $(\mathsf {f}_{\mathsf {}}' \circ \mathsf {f}_{\mathsf {}}, [\mathsf {P}, \mathsf {P}'])$, as $\mathsf {f}_{\mathsf {}}'$ and $\mathsf {P}'$ can be absorbed into the distinguisher. This leads to the following closure operation on context sets.

Definition 5

Let $\mathcal {C} \subseteq \varSigma \times \varPhi$ be a given set of contexts. We denote by the following set of contexts:

The following proposition is proven in the full version of this work [14].

Proposition 1

Let $\mathsf {R}, \mathsf {S} \in \varPhi$ denote resources, $\pi \in \varSigma$ denote a converter, and let $\mathcal {C}$ denote a set of contexts. We then have .

Finally, the composition theorem of CRI can be stated.

Theorem 1

Let $\mathsf {R}$, $\mathsf {S}$, $\mathsf {T}$, and $\mathsf {U}$ denote resources, let $\pi _1$ and $\pi _2$ denote protocols, and $\mathcal {C}_1$ and $\mathcal {C}_2$ contexts sets. We have

iff for all $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \mathcal {C}_2$ it holds that . Moreover, we have

iff for all $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \mathcal {C}_2$ it holds that .

The proof can be found in the full version [14]. Note that the additional conditions compared to the composition theorem of classical indifferentiability (cf. Sect. 2.3) are a direct consequence of the context restrictions. For instance, if in the sequential case we reduce $\mathsf {T}$ to $\mathsf {S}$ in one of the given contexts, we have to ensure that now we are again in a valid context for reducing $\mathsf {S}$ to $\mathsf {R}$. This highlights that in order for context-restricted indifferentiability to be useful, the context sets have to be defined in a form that containment can be easily verified.

3.4 Relation to Indifferentiability

Let $\mathsf {id}_{\mathsf {}}$ denote the identity converter, such that $\mathsf {id}_{\mathsf {}} \mathsf {R} = \mathsf {R}$ and $\square$ the neutral resource, such that $[\mathsf {R}, \square ] = \mathsf {R}$, for any resource $\mathsf {R}$. It is then easy to see that regular indifferentiability, which guarantees full composition, is a special case of context-restricted indifferentiability with the context set , since , i.e., the closure equals to the set of all resources and converters. One can, however, also take the opposite point of view and consider context-restricted indifferentiability to be a special case of plain indifferentiability. From this perspective, CRI reducibility is just a set of normal reducibility statements where the context is part of the considered resources and protocols, respectively. This can be summarized in the following proposition.

Proposition 2

Let . For all resources $\mathsf {R}$, $\mathsf {S}$, protocol $\pi$, and context sets $\mathcal {C} \subseteq \varSigma \times \varPhi$, we have

Using , it is also easy to see that the composition theorem of regular indifferentiability is just a special case of Theorem 1.

4 Generalizing UCE Using CRI

In the following section we consider the ROM in context-restricted indifferentiability, i.e., consider the special case of CRI where the ideal-world resource $\mathsf {S}$ that we reduce is a random oracle. In the first subsection we prove that the UCE framework is actually a special case of CRI with a random oracle, and in the second subsection we propose a generalization of the split-security UCE-class based on CRI.

4.1 Modeling UCE in CRI

In the following, let $H :H.\mathcal {K} \times H.\mathcal {X} \rightarrow H.\mathcal {Y}$ denote a keyed hash function, let $\mathsf {HK_H}$ denote the public hash-key resource that chooses a key for H and outputs it at both interfaces, let $\mathsf {hash}_{\mathsf {H}}$ denote the converter that implements an oracle for H at the outside interface when connected to $\mathsf {HK_H}$ at the inside interface, and let as a shorthand. Finally, let $\mathsf {RO_H}$ denote the private random oracle resource with the same input and output domains as H, where by private we mean that this resource only accepts queries at interface $\mathtt {A}$.²

We now present an alternative formalization of UCE based on context-restricted indifferentiability, more concretely that every possible UCE-class $\mathcal {S}^x$, where $x \in \{\text {sup}, \text {cup}, \text {srs}, \text {crs}, \text {splt},\ldots \}$, can be mapped to a set of contexts $\mathcal {C}^x$ for which the UCE statement implies the context-restricted indifferentiability statement , and moreover, if the CRI statement were restricted to a specific simulator, the reverse direction would hold as well.

In order to map every UCE-class to an equivalent set of contexts, we first introduce the set of non-interactive contexts, i.e., the communication between the source and the distinguisher being unidirectional. This restricted set of contexts faithfully encodes the structural restrictions of the traditional UCE game (cf. p. 5), where the communication between the source and the distinguisher is unidirectional. Recall that we are in the same general setting as the classical indifferentiability framework, where one only considers out-bound resources for which communication at one interface does not affect the other interface.

Definition 6

A non-interactive resource $\mathsf {P}$ is a resource that at the interface $\mathtt {E}$ accepts at most a single trigger query (usually called $\mathtt {retrieve}$), and a non-interactive filter is a converter that at the outer interface just accepts a single trigger query (usually called $\mathtt {retrieve}$). Let $\varPhi ^{\mathsf {ni}}_{}$ denote the set of all non-interactive resources, and $\varSigma ^{\mathsf {ni}}_{}$ denote the set of all non-interactive filters, respectively.

Each UCE-source naturally corresponds to a set of non-interactive contexts. This is formally stated in the following lemma by providing a surjective mapping from the set of non-interactive contexts to the set of UCE sources $\mathcal {S}$.

Lemma 1

The function $\phi :\varSigma ^{\mathsf {ni}}_{} \times \varPhi ^{\mathsf {ni}}_{} \rightarrow \mathcal {S}^{\mathsf {}}$ that maps every context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$ to the following UCE source S, that internally emulates $\mathsf {f}_{\mathsf {}}$ and $\mathsf {P}$, is surjective.

• 1. S queries the interface $\mathtt {E}$ of $\mathsf {P}$ to obtain z.

• 2. S queries the outside interface of the filter $\mathsf {f}_{\mathsf {}}$ to obtain y. The queries at the inside interface of $\mathsf {f}_{\mathsf {}}$ are forwarded to the resource $\mathsf {P}$ or output as queries to the hash oracle, respectively.

• 3. S outputs $L = (y,z)$.

We now show, that for the specific simulator $\sigma _{\mathtt {H}}$ that chooses the hash key uniformly at random, the distinguishing problem of context-restricted indifferentiability for a fixed context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$ is as hard as the UCE game with the source $\phi (\mathsf {f}_{\mathsf {}}, \mathsf {P})$. In order to relate more directly to the traditional UCE definition, we first introduce the RO-CRI advantage, which is depicted in Fig. 3 for a specific context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \mathcal {C}$.

Definition 7

We define the random-oracle context-restricted indifferentiability (RO-CRI) advantage of a distinguisher $\mathsf {D}$ on a hash function $\mathsf {H}$ in a context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})$ as

for a simulator $\sigma$. If there exists a simulator $\sigma$ such that for all efficient distinguishers and all contexts $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \mathcal {C}$, the RO-CRI advantage is negligible, we say that $\mathsf {H}$ is $\mathcal {C}$ random-oracle context-restricted indifferentiable.

Fig. 3.

The real (left) and the ideal (right) setting of context-restricted indifferentiability when applied to UCE.

The following lemma implies that for non-interactive contexts this definition is equivalent to the game-based definition of UCE-security, if we fix the simulator to $\sigma _{\mathtt {H}}$. The proof can be found in the full version of this work [14].

Lemma 2

Let $\mathcal {S}^{\mathsf {}}$ denote the set of all UCE-sources and $\phi :\varSigma ^{\mathsf {ni}}_{} \times \varPhi ^{\mathsf {ni}}_{} \rightarrow \mathcal {S}^{\mathsf {}}$ the surjective function from Lemma 1. For every distinguisher $\mathsf {D}$, there is a distinguisher $\mathsf {D'}$ (with essentially the same efficiency) with

where denotes the uce-advantage of (S, D) on H. Conversely, for every distinguisher $\mathsf {D'}$ there is an equally efficient distinguisher $\mathsf {D}$ such that for all $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \varSigma ^{\mathsf {ni}}_{} \times \varPhi ^{\mathsf {ni}}_{}$ we have .

We now state the main result of this section, relating the UCE game to context-restricted indifferentiability. It implies that instead of viewing the source as the first stage of an adversary, one can view it as the set of contexts in which the hash function can safely be used.

Theorem 2

Let $\mathcal {D}$ denote the set of all efficient distinguishers. For every class $\mathcal {S}^x$ of UCE sources, there exists a set of contexts is negligible for every $D \in \mathcal {D}$ and every context $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \mathcal {C}^x$ if and only if is negligible for all $(S,D) \in \mathcal {S}^x \times \mathcal {D}$.

Proof

Using the surjectivity of $\phi$ (Lemma 1), we have that for any UCE-class $\mathcal {S}^x$ we can define such that $\phi (\mathcal {C}^x) = \mathcal {S}^x$. Hence, by Lemma 2 we have that is negligible for all efficient distinguishers $\mathsf {D} \in \mathcal {D}$ and all contexts $(\mathsf {f}_{\mathsf {}}, \mathsf {P})\in \mathcal {C}^x$ iff is negligible for all $(S,D) \in \mathcal {S}^x \times \mathcal {D}$.

The following corollary establishes the unidirectional implication from UCE-security to context-restricted indifferentiability. The reverse direction does not necessarily hold, since the context-restricted indifferentiability notion allows for different simulators than the natural one $\sigma _{\mathtt {H}}$.

Corollary 1

Let $\mathcal {D}$ denote the set of all efficient distinguishers. For every class $\mathcal {S}^x$ of UCE sources, there exists a set of contexts $\mathcal {C}^x$ such that if is negligible for all $(S,D) \in \mathcal {S}^x \times \mathcal {D}$, then .

Proof

This follows directly from Definitions 4 and 7 and Theorem 2.

4.2 Generalizing Split Security

In this section, we present a generalization of the split-source UCE-class, that cannot be formalized in plain UCE, based on CRI. The split-source UCE-class has been proposed by Bellare et al. after it has been shown that computational-unpredictable UCE-security and computational-reset-secure UCE-security is infeasible if indistinguishability obfuscation exists. Note that split-security is not a stand-alone UCE-class in the sense that it is designed to be combined with either computational unpredictability or reset-security, respectively.

The general idea of split-security is, that the source must not be able to compute $\mathrm {Obfs}(H(\,\cdot \,, x) = y)$. To achieve this, the source must be dividable into two parts $(S_0, S_1)$, where $S_0$ chooses a vector $(x_1, \ldots , x_n)$ of query points, without having access to the hash oracle, and $S_1$ then just gets the evaluations , without having access to the hash oracle either.

Strong-Split Security. Split sources have several limitations. First, the distinguisher cannot influence the queries at all and, thus, all queries must be solely determined by the honest parties. This prevents, for example, queries like $H(hk, x \!\parallel \! a)$ where a is a value which can be chosen by the distinguisher (e.g. a is transmitted over an insecure channel) even if x is unpredictable. In the following section, we introduce a generalization of split-security, called strong-split security, to address this limitation. Second, split-security does not allow nested queries like H(hk, H(hk, x)). In the full version [14] we present a further generalization to address this issue as well.

Remark 1

Note that the first limitation is not specific to split-security, but is inherent to the traditional UCE-game. In their work [13] on Interactive Computational Extractors (ICEs), Farshim and Mittelbach have proposed an alternative relaxation of this issue. In the full version [14], we show that ICE security implies strong-split context-restricted indifferentiability for statistical unpredictability.

In order to allow the distinguisher to influence the queries while ensuring that the overall query is still unpredictable from the viewpoint of the distinguisher, we allow him to apply any injective function on the preliminary inputs x specified by the first part of the source $S_0$, which will then be evaluated and passed on to $S_1$. That is, we use the simple fact that for any injective function f guessing $f(x_i)$ is at least as hard as guessing $x_i$. To formally model this as a context set for RO-CRI, we use a specific filter $\mathsf {f}^{\mathsf {s-splt}}_{p}$. This filter expects the resource $\mathsf {P}$ to output a sequence of pairs $(x_i,a_i)$, where $x_i$ is intended to be unpredictable. We will call such a resource $\mathsf {P}$ seed in the following. For each of them the distinguisher can then input p functions $f_i^1, \ldots , f_i^p$ that are injective in the first arguments, upon which the filter will output $(f_i^1(x_i,a_i), \ldots , f_i^p(x_i,a_i))$ to the hash oracle and forwards the results to the distinguisher. A formal definition of is depicted in Fig. 4. The filter $\mathsf {f}^{\mathsf {s-splt}}_{p}$ can then be combined with an arbitrary non-interactive resource to obtain a strong-split RO-CRI context.

Fig. 4.

The strong-split filter $\mathsf {f}^{\mathsf {s-splt}}_{p}$ for RO-CRI, where $\mathcal {I}_{\mathcal {X} \times \mathcal {A} \rightarrow H.\mathcal {X}}$ denotes the set of all efficiently computable functions from $\mathcal {X} \times \mathcal {A}$ to $H.\mathcal {X}$ that are injective in the first argument. Note that it was pointed out in [7] that the queries of a split-source must be distinct; otherwise arbitrary information can be communicated to the second stage.

Definition 8

The strong-split RO-CRI context set is the set of filters and non-interactive resource pairs of which the filter can be factorized into $\mathsf {f}^{\mathsf {s-splt}}_{p}$ followed by an arbitrary filter. Formally,

Analogous to split-security, strong-split security is not a sufficient restriction to avoid trivial impossibility results. Rather, these notions are meant to be combined with a notion of unpredictability or reset-security. However, for strong-split security, requiring the seed to output distinct unpredictable values is still insufficient to guarantee the security: for instance, if the resource $\mathsf {P}$ outputs $(x, a_1)$ and $(x+1, a_2)$, then the distinguisher can easily choose f and g such that $f(x,a_1) = g(x+1,a_2)$. Therefore, we introduce suitable notion of unpredictability in the next subsection, which when combined with strong-split security presents a plausible assumption for a hash function family.

Strict Min-Entropy Seeds. We now define an information-theoretic restriction on the seed called strict min-entropy seeds. Similar to Farshim and Mittelbach [13] we choose to focus on statistical rather than computational unpredictability to ensure that our notion excludes interactive version of the attack highlighted in [6].³ More concretely, we consider seeds whose outputs at interface $\mathtt {A}$ consist of pairs $(X_i, A_i)$, with $A_i$ being an auxiliary value, such that $X_i$ has high average conditional min-entropy given the leakage Z and all previous queries.

Definition 9

A strict min-entropy k-bit seed with n outputs is a resource that initially draws random values $X_1, \ldots , X_n$, $A_1, \ldots , A_n$, and Z according to some joint distribution, such that

Then, it accepts at the interface $\mathtt {E}$ a single trigger query (usually called $\mathtt {retrieve}$) that is answered with Z, and at the interface $\mathtt {A}$ n trigger queries answered with $(X_1, A_1)$ to $(X_n, A_n)$. Let $\varPhi ^{\mathsf {s-me}}_{n,k} \subset \varPhi ^{\mathsf {ni}}_{}$ denote the set of all strict min-entropy k-bit seed with n outputs. Moreover, let denote the set of all strict min-entropy k-bit contexts.

When combining stong-split security with strict min-entropy seeds, the security of strong-split sources does not depend on the maximal number n of values produced by the seed. The following lemma is proven in the full version [14], using a simple hybrid-argument.

Lemma 3

Let n be polynomially bounded. If H is a $\mathcal {C}^{\mathsf {s-splt}}_{p} \cap \mathcal {C}^{\mathsf {s-me}}_{1,k}$ indifferentiable hash function, then H is also $\mathcal {C}^{\mathsf {s-splt}}_{p} \cap \mathcal {C}^{\mathsf {s-me}}_{n,k}$ indifferentiable.

5 Split Security of the Merkle-Damgård Construction

Indifferentiability is widely used to prove the security of hash function constructions. Since CRI is essentially a refined version of indifferentiability, it is hence natural to consider the RO-CRI security as well. It is easy to show that any indifferentiable hash function construction is reset-UCE secure if the underlying compression function is reset-UCE secure. On the other hand, for split security no corresponding result has been proven so far. In the following we investigate the split-security of the Merkle-Damgård construction using the RO-CRI framework. While ideally one could prove that the Merkle-Damgård construction is split secure if the compression function is so, or that the Merkle-Damgård construction is strong-split secure if the compression function is so, we will prove a slightly weaker result:

Consider the Merkle-Damgård construction that splits the message into blocks of length m . We show that the Merkle-Damgård construction is split-secure for inputs having at least one block with k bits of min-entropy, if the compression function is strong-split secure for inputs with $\min (k,m)$ bits of min-entropy.

In contrast to the definition of strict min-entropy seeds (c.f. Definition 9) we require that at least one of the blocks has high min-entropy and not just the overall message has. Moreover, in order for the proof to actually work, we require that this block has k bits of min-entropy given all subsequent blocks. In Lemma 4 we then show that having a high min-entropy density, i.e., the fraction between the min-entropy and the message length, is a sufficient criteria for this. First, however, let us formally introduce this CRI context set.

Definition 10

For a block length , let $\text {Pad}_\ell$ denote the usual padding scheme of the Merkle-Damgård scheme, that is $\text {Pad}_\ell :\{0,1\}^* \rightarrow (\{0,1\}^\ell )^+$ that pads a message x by first appending zeros up to a multiple of the block length $\ell$, and then appending an encoding of the number of zeros appended as a last block. Moreover, for $X \in \{0,1\}^*$, we denote by $X^i$ the i-th block of $\text {Pad}_\ell (X)$.

Definition 11

A non-interactive resource is said to be a k out of $\ell$-bit strict min-entropy block, denoted $\mathsf {P}\in \varPhi ^{\mathsf {me-blk}}_{k,\ell ,b,n}$, if $\mathsf {P}\in \varPhi ^{\mathsf {s-me}}_{k,n}$ with $\bigcup _{i \le (b-1) \ell } \{0,1\}^i \times \mathcal {A}$ as the output domain of interface $\mathtt {A}$, and there exist random variables $C_1, \ldots , C_n$ such that $C_i \in \{1,\ldots ,\frac{|{\text {Pad}_\ell (X_i)}|}{\ell }\}$ and

Moreover, let .

Note, that contrary to the classical indifferentiability of the Merkle-Damgård construction, we do not require $\text {Pad}$ to be prefix-free: when combined with the strict min-entropy condition H(X) cannot be extended to $H(\text {Pad}(X) || Y)$, as for $\text {Pad}(X) || Y$ having high min-entropy given X, Y must have so, and thereby the well-known length-extension attack is excluded. Whether a more advanced construction with a finalization function, e.g. HMAC, could be proven secure for a more relaxed context set remains an interesting open problem. We now phrase our main result of this section; the proof can be found in the full version [14].

Theorem 3

Let $h :\{0,1\}^{m + \ell } \rightarrow \{0,1\}^m$ denote a fixed input-length compression function, $H :\{0,1\}^* \rightarrow \{0,1\}^m$ denote the hash function obtained by first padding the message using $\text {Pad}_\ell$ and then applying the Merkle-Damgård scheme using h, and let . Then, if h is $\mathcal {C}^{\mathsf {s-splt}}_{1} \cap \mathcal {C}^{\mathsf {s-me}}_{1,k'}$ RO-CRI secure, then H is $\mathcal {C}^{\mathsf {splt}}_{} \cap \mathcal {C}^{\mathsf {me-blk}}_{k,\ell ,b,n}$ RO-CRI secure for any polynomial b and n.

To conclude this section, we now present a sufficient condition for a seed to satisfy Definition 11 based on the length of the message and its overall min-entropy. More concretely, we prove that if a message is split into b blocks of size n, and has overall min-entropy of k bits, then there exists a block with $\frac{k}{b} - \log _2(b)$ bits of min-entropy, given all succeeding blocks. In order to more closely resembles the chain rule of Shannon entropy, the proposition is stated with conditioning on all preceding message $X_1 \ldots X_{C-1}$ instead of all succeeding ones. The converse result can easily be obtained by simply relabeling the blocks. The proof can be found in the full version of this work [14].

Lemma 4

Let $X_1, \ldots , X_b$ and Z be random variables (over possibly different alphabets) with $\tilde{H}_{\infty }({X_1 \ldots X_b \mid Z}) \ge k$. Then, there exists a random variable C over the set $\{1, \ldots , b\}$ such that $\tilde{H}_{\infty }({X_C \mid X_1 \ldots X_{C-1} C Z}) \ge k/b - \log _2(b)$.

This lemma is a generalization of the randomized chain rule proven by the authors of [11] (similar variants exists also in [5, 22]) stating that there exists a binary random variable C such that $H_{\infty }(X_{1-C} C) \ge H_{\infty }(X_0 X_1)/2$. Note that the main difference of our result is, that it conditions on all previous blocks, i.e., it essentially represents the min-entropy equivalence of the strong chain rule $H(X_0) + H(X_1 \mid X_0) = H(X_0 X_1)$ instead of $H(X_0) + H(X_1) \ge H(X_0 X_1)$.