Pooya Farshim
email: pooya.farshim@gmail.com

Arno Mittelbach
email: arno.mittelbach@cased.de

Modeling Random Oracles under Unpredictable Queries

Keywords: Random oracle, Unpredictability, UCE, RKA security, KDM security, Zipper Hash, Indifferentiability, Multi-stage security

introduced a new abstraction called Universal Computational Extractors (UCEs), and showed how they can replace random oracles (ROs) across a wide range of cryptosystems. We formulate a new framework, called Interactive Computational Extractors (ICEs), that extends UCEs by viewing them as models of ROs under unpredictable (aka. high-entropy) queries. We overcome a number of limitations of UCEs in the new framework, and in particular prove the adaptive RKA and semi-adaptive KDM securities of a highly efficient symmetric encryption scheme using ICEs under key offsets.

We show both negative and positive feasibility results for ICEs. On the negative side, we demonstrate ICE attacks on the HMAC and NMAC constructions. On the positive side we show that: 1) ROs are indeed ICE secure, thereby confirming the structural soundness of our definition and enabling a finer layered approach to protocol design in the RO model; and 2) a modified version of Liskov's Zipper Hash is ICE secure with respect to an underlying fixed-input-length RO, for appropriately restricted classes of adversaries. This brings the first result closer to practice by moving away from variable-input-length ROs. Our security proofs employ techniques from indifferentiability in multi-stage settings.

Introduction

Background

Since their formal introduction by Bellare and Rogaway [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF], random oracles (ROs) have found many applications across a wide range of cryptographic protocols. However, due to an uninstantiability result of Canetti, Goldreich, and Halevi [START_REF] Canetti | The random oracle methodology, revisited (preliminary version)[END_REF], which shows that certain (artificial) protocols become insecure as soon as the random oracle is replaced by any concrete hash function, reliance on ROs has also become somewhat debatable.

Two lines of research have been directed at dealing with such uninstantiability results. One is to construct standard-model counterparts of cryptographic primitives designed in the RO model (ROM). This approach comes with the drawback that the resulting cryptosystems often tend to be complex and achieve a lower level of security and/or efficiency. A second, more modular, approach aims to formulate abstractions of the proof-centric properties of random oracles such as extractability, programability, or non-malleability [Can97,CD09,Nie02,CD08,BCFW09]. Assuming that a hash function meets the introduced model, one proceeds to show that it can safely replace the random oracle in a protocol. These formalizations, however, have only been successful to a limited extent, and the question of finding a flexible and general framework that could be applied across a broad range of security goals and protocols remained open until recently.

UCE security

Bellare, Hoang, and Keelveedhi (BHK) [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF] revisit the above questions and present a powerful framework called Universal Computational Extractors (UCEs) that allow to securely instantiate random oracles in an interesting and diverse set of applications. These include, among other things, security under key-dependentmessage (KDM) attacks, security under related-key attacks (RKAs), simultaneous hard-core bits, point function obfuscators, garbling schemes, proofs of storage, deterministic encryption, and message-locked encryption, thereby going far beyond what was previously possible.

Behind UCEs lies a new way to model the indistinguishability of a keyed hash function from a random oracle. Indeed, there are two direct ways to (incorrectly) model the security of a hash function:

(1) Provide the adversary with the hash key and ask it to distinguish an oracle implementing the hash function from one implementing the random oracle. This approach immediately fails as this game can be trivially won with the knowledge of the hash key by computing a hash value and checking the answer against the oracle's answer for the same query.

(2) Adopt the above approach, but now hide the hash key. This leads to PRF security-for which feasibility results are known-but is not useful in the context of hashing as the hash key is typically publicly known.

BHK overcome the above shortcomings by splitting the attacker into two parts and constraining the communication between the two. The first UCE attacker does not get to see the hash key, but has oracle access to either the hash function under a random key or the random oracle according to a random bit. The second attacker, on the other hand, does get to see the hash key, but can no longer access the oracle, and it has to guess the bit; see Figure 1 (left). The two stages of the adversary can communicate only in restricted ways since arbitrary communication would lead to an attack similar to that given above for formulation (1).

More formally, for a keyed hash function H, UCE security is defined via a two-stage game consisting of algorithms S and D, called the source and the distinguisher respectively, as follows. In the first stage, the source is given access to an oracle Hash that depending on a random bit b implements either the random oracle or the concrete hash function H under a random hash key hk. The source terminates by outputting some leakage L, which is then communicated to the second-stage distinguisher D. In addition to leakage L, the distinguisher also gets the hash key hk as input. The distinguisher's task is to guess b, i.e., guess whether the source was talking to the random oracle or the hash function. The UCE advantage of the pair (S, D) is defined as usual to be the probability of correctly guessing the bit b scaled away from one-half. We refer the reader to the original work [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF] for an excellent overview of this approach to modeling hash-function security.

To see that without further restrictions UCE security cannot be achieved, consider a source that leaks one of its oracle queries together with the corresponding oracle answer to the distinguisher. The distinguisher then simply recomputes the hash value on the queried point-the distinguisher knows the hash key-and compares it to the leaked value.

In their original work, BHK [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF] define two restrictions on sources: computational unpredictability and computational reset security. In the computational unpredictability game, it is required that when the source is run with a random oracle its leakage does not computationally reveal any of its queries. This is formalized by requiring that the probability of any efficient predictor P in guessing a query of S when given L is negligible.

The class of computationally unpredictable sources is denoted by S cup , and the resulting UCE security UCE[S cup ] (aka. UCE1) of a hash function is defined by requiring the advantage of any efficient pair (S, D) with an unpredictable S ∈ S cup in the UCE game to be negligible. Reset security imposes a weaker restriction on the source class and leads to the stronger UCE2 notion.

UCE security has been the subject of many recent studies. Brzuska, Farshim, and Mittelbach (BFM) [START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF] show that, under new cryptographic assumptions, these restrictions are insufficient for a feasible definition. More precisely, assuming the existence of indistinguishability obfuscators [BGI + 01,GGH + 13], BFM show that the UCE[S cup ] security of any hash function can be broken in polynomial time. To overcome this attack, BFM [START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF] (and subsequently BHK in an updated version of their paper [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF]) propose a statistical notion of unpredictability whereby the predictor can even run in unbounded time. Following the attack, BHK also refine the UCE notions based on computational unpredictability and introduce the classes of bounded parallel and split sources. 3 BFM show that security against bounded parallel source is also infeasible [START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF], and recently attacks against split sources have also been shown [START_REF] Bellare | Contention in cryptoland: Obfuscation, leakage and UCE[END_REF].

On the positive side, Brzuska and Mittelbach [START_REF] Brzuska | Using indistinguishability obfuscation via UCEs[END_REF][START_REF] Brzuska | Universal computational extractors and the superfluous padding assumption for indistinguishability obfuscation[END_REF] show how to construct UCEs for the class of strongly unpredictable and statistically unpredictable sources for bounded number of queries. Bellare, Hoang, and Keelveedhi [START_REF] Bellare | Cryptography from compression functions: The UCE bridge to the ROM[END_REF] develop domain extenders for UCEs, and Bellare and Hoang [START_REF] Bellare | Resisting randomness subversion: Fast deterministic and hedged publickey encryption in the standard model[END_REF] construct deterministic PKEs from UCEs for statistically unpredictable sources and lossy trapdoor functions. BFM [START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF] have shown that the existence of obfuscation-based attacks against statistically unpredictable sources violates well-known impossibility results. A number of recent works have shown how to use UCEs as RO replacements in other protocols [MH14,BK15,DGG + 15].

Despite the above advances, and irrespective of the restrictions imposed on sources, the UCE framework is intrinsically limited in a number of aspects: it only allows the source to place Hash queries which are independent of the hash key; after leakage is communicated from the source to the distinguisher no further Hash oracle queries can be made, and hence hash queries are inherently non-adaptive; UCEs cannot model unkeyed hash functions nor hash functions with weak keys where the key does not come from the uniform distribution. Motivated by these shortcomings, and the ultimate goal of basing the security of highly efficient and practical protocols on well-defined and feasible properties of random oracles, we set out to formalize an enhanced framework for the study ROM protocols.

Interactive computational extractors

Given the development of UCEs, defining an extended model which meets the above-mentioned specifications is an intricate task. Indeed, well before the emergence of obfuscation-based attacks, BHK [BHK13b, page 9] warned that extending UCEs to an interactive setting is "a dangerous path to tread." As an example, assume that we introduce a bi-directional communication channel between the distinguisher and the source so that our adaptivity targets are met. This extension can be shown to fall prey to somewhat non-trivial attacks that utilize general-purpose multi-party computation (MPC) protocols. Suppose the source S holds a random input x whose hash is y, and D holds hk. The two parties then run an MPC protocol to compute the Boolean value y = H(hk, x). The distinguisher finally returns this value as its guess. This attack would meet any reasonable notion of computational unpredictability since the security of the MPC protocol would ensure that the parties learn no more than what can be deduced from their individual private inputs. 4 Allowing hash queries to depend on the hash key hk is also challenging since similarly to approach (1) above access to both hk and the hash oracle would trivialize the notion. For similar reasons, formulating a UCE-like model for unkeyed hash functions is also non-trivial. As we shall see, other forms of attacks also arise that should be ruled out for a feasible model.

The ICE framework. Let us call an input (hk, x), consisting of the hash key hk and a domain point x, to a hash function a full input. One way to view UCEs is that they adopt the indistinguishability-based approach (1) above, but restrict hash queries so that full inputs remain hidden from the attacker(s). It is clear that such hidden queries are not meaningful in the presence of a single adversary-any adversary knows its own queries-and hence UCEs come with two adversaries. Unpredictability together with denial of oracle access to D ensures that the x components of full inputs remain hidden from D. On the other hand, the hk components of full inputs remain hidden from S as the source is denied access to hk (and no communication from D to S is allowed). As a result, full inputs (hk, x) remain hidden from both parties involved in a UCE attack.

This perspective allows us to build on UCEs and extend them as follows. In our new framework, which we call Interactive Computational Extractors (ICEs),5 a general mechanism for the joint generation of full inputs is enabled and adversarial restrictions that formalize what it means for full hash inputs to have high entropy are imposed.

We let two distinguishers (D 1 , D 2 ) to take part in an attack, and allow them to communicate via a bi-directional channel. Both distinguishers get access to a challenge hash oracle, which depending on a challenge bit implements either the real hash function or a (keyed) random oracle. To enable the two parties to make hidden queries, we introduce a shared write-only tape that both D 1 and D 2 can write onto. When a distinguisher queries the hash oracle, the (real or ideal) hash of the full contents of the tape is returned. In contrast to UCEs, D 1 or D 2 can generate a hash key and perhaps modify it throughout the attack. This attack scenario is symmetric for D 1 and D 2 and, without loss of generality, the game terminates by D 2 outputting with a bit. (Our formal definition, however, comes with a slightly more general return statement.) For a class C of distinguishers, we define ICE[C] security by demanding that the probability of guessing the challenge bit for any D = (D 1 , D 2 ) ∈ C is negligibly close to 1/2. See Figure 1 (right) for a summary of this interaction.

Entropic queries. Similarly to UCEs, the ICE notion cannot be achieved without constraining the way the two distinguishers communicate. The main restriction that we introduce is analogous to statistical unpredictability for UCEs: we demand the statistical unpredictability of full inputs to the hash function, including the hash key hk, from each distinguisher's point of view. We choose a statistical, rather than a computational, notion so that our definitions do not become subject to the interactive versions of the attacks highlighted in [START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF]. 6 More precisely, we require that when the hash oracle implements a keyed random oracle, no (possibly unbounded) predictor can guess a full input (hk, x) used to compute a hash value when it is provided with a distinguisher's view consisting of its inputs, random coins, and all incoming messages and oracle responses.

Since our framework allows oracle access to both parties, unlike UCEs the two distinguishers can implicitly communicate via hash patterns as follows. Suppose D 2 wants to leak a bit d to D 1 . Algorithm D 2 starts by writing a random string onto the second half of the input and hands over the attack to D 1 . Algorithm D 1 writes a random value to the first half of the input, calls Hash to receive a first hash value h 1 , and hands over the attack back to D 2 . Now algorithm D 2 , according to the value of d, either modifies the contents of the second half of the input tape or leaves them unchanged. D 1 can recover d by obtaining a second hash value h 2 and checking if (h 1 = h 2 ). The two distinguishers can also communicate via a bit-fixing attack: D 2 samples many (unpredictable) random values x conditioned on its hash value beginning with bit d, which D 1 can then recover via a hash query.

In our unpredictability definition the predictor gets to see all hash responses, and hence if there are any repetitions they will be seen by the predictor. Unpredictability will therefore ensure that such repetition patterns will not leak any of the queries. Sometimes, however, we need to explicitly disallow any repeat queries to enable a security proof to go through. In such a scenario, we can ensure that there is no leakage via hash patterns either. Repeat-freeness appears in other related settings such as related-key attacks or correlated-input hashing [START_REF] Bellare | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF][START_REF] Goyal | Correlated-input secure hash functions[END_REF].

Applications

BHK [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF] use UCEs to show that the encryption scheme of Black, Rogaway, and Shrimpton (BRS) [START_REF] Black | Encryption-scheme security in the presence of key-dependent messages[END_REF] is secure under related-key attacks (RKAs) and key-dependent-message (KDM) attacks as long as the related keys/key-dependent messages are derived non-adaptively at the onset and without access to the hash key or previous ciphertexts. 7As we shall see, ICE encompasses UCE as a special case, and the BRS scheme can also be instantiated under the above models using ICEs. We can however also obtain feasibility results that are outside the reach of UCEs. A practically relevant and desirable level of RKA security is that corresponding to key offsets (the so-called xor-RKA security [START_REF] Liskov | Tweakable block ciphers[END_REF][START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and[END_REF]). We show that ICEs are sufficient to prove the full xor-RKA security of the BRS scheme. Our formal result is more general and applies to the larger class of split functions that take the form φ(K 1 K 2 ) = φ 1 (K 1 ) φ 2 (K 2 ). (Such functions have been used to build RKA-secure PRFs [START_REF] Bellare | Pseudorandom functions and permutations provably secure against relatedkey attacks[END_REF], and also appear in other related contexts [START_REF] Cheraghchi | Non-malleable coding against bit-wise and split-state tampering[END_REF][START_REF] Liu | Tamper and leakage resilience in the split-state model[END_REF].) In addition to achieving stronger security guarantees, ICEs allow instantiating the BRS scheme using unkeyed hash functions, which is arguably closer to the original formulation of BRS. 8We also strengthen the attainable KDM security guarantees for BRS by showing that adversaries can choose key-dependent messages adaptively based on the hash key and also semi-adaptively depending on previous ciphertexts. We prove that ICEs are adaptively correlated-input secure [START_REF] Goyal | Correlated-input secure hash functions[END_REF] and that they relate well to other standard security properties of random oracles, such as pseudorandomness, randomness extraction, and one-way security (see Appendix B). We leave it as open questions to see if full RKA beyond xor offsets or full KDM security can be established using extractor-like notaions.

Instantiations

BHK show that random oracles fulfill their strongest proposed UCE notion, namely UCE security with respect to computationally unpredictable sources. 9 We prove that random oracles are also ICE secure. The significance of these results are twofold [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF]: (1) there are no generic attacks on ICEs and the model is structurally sound; and (2) a layered approach to security analysis can be enabled, whereby one first proves the security of a scheme under an ICE assumption and then applies the RO model feasibility result. The latter is akin to security analyses carried out in the generic group model.

Practical hash functions, however, are not monolithic objects and often follow an iterative procedure to convert a fixed-input-length random oracle (FIL-RO) into a variable-input-length random oracle (VIL-RO). This, in turn, raises the question whether or not the above result can be brought closer to practice by demonstrating positive feasibility results for VIL-ICEs in the FIL-RO model. A seemingly immediate way to establish this result would be to start with a hash function that is known to be indifferentiable from a VIL RO (e.g., the HMAC or the NMAC construction), and then apply the RO feasibility result above to conclude. This argument, however, fails as the ICE game is multi-staged and indifferentiability does not necessarily guarantee composition in such settings [START_REF] Ristenpart | Careful with composition: Limitations of the indifferentiability framework[END_REF].

Motivated by the above observations, we show both positive and negative feasibility results for ICEs. On the negative side, we show that the indifferentiable HMAC and NMAC constructions are provably ICE insecure in the FIL-RO model. On the positive side, and building on Mittelbach's techniques [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF], we prove that a keyed version of Liskov's Zipper Hash [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF] is ICE secure (as a VIL hash function) under the assumption that the underlying compression function is a FIL-RO. Zipper Hash can be seen as a variant of the classical Merkle-Damgård [START_REF] Damgård | A design principle for hash functions[END_REF][START_REF] Ralph | One way hash functions and DES[END_REF] construction where the message blocks are processed twice in the forward and backward directions. Hence our results strengthen the VIL-RO feasibility result above, and also provide formal evidence for the (intuitive) added security guarantees that multi-pass hash functions seem to offer over their single-pass counterparts. For instance, combined with our RKA and KDM results, we may conclude that Zipper Hash can be safely used within the BRS scheme with no adverse affects on its security.

The above analysis can be further strengthened in at least two directions. First, one can weaken the underlying assumption and assume that the compression function underlying Zipper Hash is only a FIL-ICE (rather than a FIL-RO). To this end, BHK [START_REF] Bellare | Cryptography from compression functions: The UCE bridge to the ROM[END_REF] give domain extenders for UCEs. Second, and motivated by the standard-model realizations of ICEs and UCEs, we ask if these primitives can be based on plausible hardness assumptions. Brzuska and Mittelbach [START_REF] Brzuska | Indistinguishability obfuscation versus multi-bit point obfuscation with auxiliary input[END_REF][START_REF] Brzuska | Universal computational extractors and the superfluous padding assumption for indistinguishability obfuscation[END_REF] have recently shown positive results for UCEs with respect to restricted classes of sources.

Notation

We denote the security parameter by λ ∈ N, which is implicitly given to all algorithms (if not explicitly stated so) in the unary representation 1 λ . By {0, 1} we denote the set of all bit strings of length and {0, 1} * is the set of all finite-length bit strings. For x, y ∈ {0, 1} * we denote their concatenation by x y, the length of x by |x|, the ith bit of x by x[i], and the substring of x formed using bits i to j by x[i..j]. We denote the empty string by ε. For X a finite set, |X| denotes its cardinality, and x ←$ X denotes the action of sampling x uniformly at random from X. If Q is a list and x a string then Q : x denotes the list obtained by appending x to Q. Similarly, If Q 1 and Q 2 are lists, then Q 1 : Q 2 denotes the concatenated list. Unless stated otherwise, algorithms are assumed to be randomized. We call an algorithm efficient or PPT if it runs in time polynomial in the security parameter. By y ← A(x; r) we denote that y was output by algorithm A on input x and randomness r. If A is randomized and no randomness is specified, then we assume that A is run with freshly sampled uniform random coins, and write y ←$ A(x). We use Coins[A] to denote the polynomially long string of random coins r used by a PPT machine A. We say a function negl(λ) is negligible if negl(λ) ∈ λ -ω(1) . Hash functions. In the line with [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF], we consider the following (simplified) formalization of hash functions. A hash function consists of five PPT algorithms H := (H.Kg, H.Ev, H.kl, H.il, H.ol) as follows. The key-generation algorithm H.Kg gets the security parameter 1 λ as input and outputs a key hk ∈ {0, 1} H.kl (λ) , where H.kl(λ) is the key-length function. Algorithm H.il(λ) outputs the length of admissible inputs, which could take the special value * denoting the variable-length input space {0, 1} * . Algorithm H.ol(λ) outputs the length of admissible outputs, which we assumed to be a fixed polynomial function of the security parameter. The deterministic evaluation algorithm H.Ev takes as input the security parameter 1 λ , a key hk, a point x ∈ {0, 1} H.il(λ) , and generates a hash value H.Ev(1 λ , hk, x) ∈ {0, 1} H.ol(λ) . To ease notation, we often suppress the security parameter and simply write H.Ev(hk, x).

The ICE Framework

In this section we precisely define the ICE framework. We refer the reader to the introduction for a high-level overview of the model.

The ICE game. Let H = (H.Kg, H.Ev, H.kl, H.il, H.ol) be a hash function and let D = (D 1 , D 2 ) be a pair of algorithms. We define the ICE advantage of D against H as

Adv ice H,D (λ) := 2 • Pr ICE D H (λ) -1 ,
where game ICE D H (λ) is shown in Figure 2. As mentioned in the introduction, we may assume, without loss of generality, that the game termites by D 2 outputting a bit. However, in order to preserve the symmetry of the definition (which will simplify our adversarial restrictions later on) and for added generality, we let the distinguishers jointly guess the challenge bit by computing b 1 ⊕ b 2 , where b i is D i 's guess. The interaction terminates when both distinguishers return non-⊥ values for b 1 and b 2 . For a class C of distinguishers, we define ICE[C] security by requiring the advantage of any adversary D ∈ C to be negligible in the ICE game.

We require (D 1 , D 2 ) not to leave any superfluous blank spaces on the joint tape. That is, a Write call must ensure that before the Hash oracle is called there do not exist indices i < j such that

x[i] = ε = x[j] or Main ICE D H (λ) 1 : b ←$ {0, 1}; L1 ← 1 λ 2 : while b1 = ⊥ ∨ b2 = ⊥ do 3 : (b1, L2) ←$ D Write,Hash 1 (L1) 4 : (b2, L1) ←$ D Write,Hash 2 (L2) 5 : return (b1 ⊕ b2 = b) Write(j, v) (hk, x)[j..j + |v| -1] ← v Hash() if b = 1 then T [hk, x] ← H.Ev(hk, x) elseif T [hk, x] = ⊥ then T [hk, x] ←$ {0, 1} H.ol(λ) return T [hk, x]
Fig. 2. The ICE game with respect to hash function H and distinguishers D = (D1, D2). We have omitted the initialization of various variables for readability.

hk[i] = ε = hk[j].
We also demand that the full inputs (hk, x) are valid in the sense that prior to a Hash call hk ∈ {0, 1} H.kl(λ) and x ∈ {0, 1} H.il (λ) . Although the distinguishers D 1 and D 2 are in general stateful algorithms, we omit the explicit handling of state values from the inputs and outputs of D i .

Restrictions. As discussed in the introduction, the ICE model is not feasible unless additional restrictions on the distinguishers are imposed. We formulate our restrictions as joint properties of (D 1 , D 2 ). Before presenting our main restrictions corresponding to high-entropy queries, we give a set of basic classes that will be useful in studying ICEs. As an example, for polynomials w, q, and r we define C w,q,r i to be the set of all (D 1 , D 2 ) such that when (D 1 , D 2 ) is run in the ICE game conditioned on b = 0 (i.e., with respect to the random oracle), the distinguisher D i places at most w(λ) queries to Write, at most q(λ) queries to Hash, and terminates after at most r(λ) invocations. We formalize a number of other notions below and omit the preamble "The set of all (D 1 , D 2 ) such that when (D 1 , D 2 ) is run in ICE with b = 0, we have with overwhelming probability that" from their definitions. Note that the classes below depend on i ∈ {1, 2}. For classes

C label i we define C label := C label 1 ∩ C label 2 .
In the following table we present several restrictions that we will be using throughout this paper.

Class Description

C w,q,r i Di places at most w(λ) queries to Write, at most q(λ) queries to Hash, and terminates after at most r(λ) invocations.

C poly i

Di makes polynomially many oracle queries.

C ppt i
Di runs in polynomial time on each invocation and terminates after a polynomial number of rounds.

C 0 i
Di sets bi := 0 in all invocations.

C ε i Di sets L3-i := ε in all invocations.
C 0-hk i Di never writes onto the hk part of the tape.

C 1-hk i
On its first invocation, Di writes a random hk onto the hk-part of the tape. In subsequent invocations, Di never writes onto the hk-part of the tape.

C dist i
Di makes distinct queries to Hash. That is, for lists Q1 and Q2 defined in Figure 3, the combined list Q1 : Q2 is repetition-free. Note that

C dist i = C dist 3-i = C dist . C sup i
The probability that any (possibly unbounded) predictor P can guess a full query of Di is negligible. We call this the class of statistically unpredictable Di. See Figure 3 for the formal definition. Class C cup i is the computational analogue, where P is restricted to be ppt.

Main Pred

P i,D (λ) 1 : L1 ← 1 λ 2 : while b1 = ⊥ ∨ b2 = ⊥ do 3 : k ← 1; (b1, L2) ←$ D Write,Hash 1 (L1) 4 : Lki ← Lki : Li 5 : k ← 2; (b2, L1) ←$ D Write,Hash 2 (L2) 6 : (hk, x) ←$ P (Coins[Di], Ai, Lki) 7 : return (hk, x) ∈ Q1 : Q2 Write(j, v) (hk, x)[j..j + |v| -1] ← v Hash() if T [hk, x] = ⊥ then T [hk, x] ←$ {0, 1} H.ol(λ) Q k ← Q k : (hk, x) A k ← A k : T [hk, x] return T [hk, x]
Fig. 3. The unpredictability game.

An example: UCE within ICE. We describe how UCEs can be captured within the ICE framework. Since ICE is more expressive a framework, we need to (drastically) restrict the distinguishers. In modeling UCEs, we identify the UCE distinguisher with D 1 and the UCE source with D 2 . All parties typically run in polynomial time and hence we restrict to

C ppt := C ppt 1 ∩ C ppt 2 .
In UCEs, the source queries Hash on an unknown hash key. The distinguisher, on the other hand, gets to see the hash key. Thus, we let D 1 (which represents the distinguisher) write a random hk to the joint input and then hand the attack to D 2 on the first invocation, i.e., D ∈ C 1-hk 1 . We further restrict to C ε 1 , as a UCE distinguisher does not leak. Since the UCE game only has a single round, we also restrict to C 1,0,2 1 (one round is used to write the hk). Finally, the source does not take part in decision making and cannot modify the hash key: UCEs are modeled by ICE[C uce ] where

C uce := C ppt ∩ C 1-hk 1 ∩ C ε 1 ∩ C 1,0,2 1 ∩ C 0 2 ∩ C 0-hk 2 .
Note that the above models UCEs without any additional restrictions on the source classes. Such requirements can be added on top by appropriately restricting C uce .

Unpredictability. We now formally define what we mean by a D that has unpredictable (aka. high-entropy) queries. We focus on a statistical notion of unpredictability [START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF][START_REF] Bellare | Contention in cryptoland: Obfuscation, leakage and UCE[END_REF]. 10 We say D = (D 1 , D 2 ) is statistically unpredictable for the distinguisher i, and write D ∈ C sup i , if the advantage of any unbounded predictor P defined by Adv pred i,D,P (λ) := Pr Pred P i,D (λ) , is negligible, where game Pred P i,D (λ) is shown in Figure 3. Note that the predicator only gets to see the hash responses for distinguisher D i -these are within D i 's view-and has to guess a query made by either distinguisher in the concatenated list Q 1 : Q 2 . It is easy to check that UCE security with respect to statistically unpredictable sources is equivalent to ICE[C uce ∩ C sup ] security.

Remark. Since predictor P receives the full view of a distinguisher D i , it can perfectly simulate a run of D i in the ICE game with respect to a random implementation of the hash oracle, without any need to see the view of the partner distinguisher D 3-i . We will rely on this observation in our proofs.

Example Applications

In this section we demonstrate two example use cases of ICEs. Further applications are given in Appendix B and summarized in Table 2 below. These applications serve to demonstrate that many properties of random oracles that are useful in analyses of ROM cryptosystems can be modeled in a unified way within the ICE framework.

Goal/Model

Class Used/Achieved

Split RKA C * ∩ C sup ∩ C 0 2 Split KDM C * ∩ C sup ∩ C 0 1 Split/claw-free CIH C * ∩ C sup ∩ C 0 2 Extractor C * ∩ C sup ∩ C 0 1 ∩ C ε ∩ C 1,1,2 Weak PRF C * ∩ C sup ∩ C 0 1 ∩ C ε ∩ C poly,poly,1 poly-regular OWF C * ∩ C sup ∩ C 0 1 ∩ C 1,1,1 VIL-ROM C ppt ∩ C cup and C poly ∩ C sup ; both contain C * ∩ C sup FIL-ROM C * ∩ C cup , which contains C * ∩ C sup
* := C ppt ∩ C dist ∩ C 1-hk 1 ∩ C 0-hk 2 ∩ C ε 2 .

Split RKA security

We show that the symmetric encryption scheme proposed by Black, Rogaway, and Shrimpton (BRS) [START_REF] Black | Encryption-scheme security in the presence of key-dependent messages[END_REF] is secure against related-key attacks (RKAs) when instantiated with an ICE-secure hash function. The encryption algorithm of the BRS scheme is implemented via

Enc H (K, M ; R) := (R, M ⊕ H(K R))
, for a hash function H, randomness R and key K. Recall that in an RKA, an adversary can obtain encryptions of messages of its choice under correlated keys (e.g., under K and K ⊕ 1). See Appendix A for the formal definition. Split related-key derivation (RKD) functions φ decompose into two sub-RKD functions φ 1 and φ 2 that are applied in parallel to two (fixed) sub-strings of the key:

φ(K 1 K 2 ) = φ 1 (K 1 ) φ 2 (K 2 )
.11 Split functions capture many RKA cases of interest including the case of xoring constants into keys. Without the minimal assumption that φ's have unpredictable outputs (i.e., the guessing probability of the outputs of φ(K) over randomly chosen K is negligible) RKA security is not achievable [START_REF] Bellare | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF]. In our proof, we will require a slightly stronger condition that the sub-RKD functions φ 1 (K 1 ) and φ 2 (K 2 ) are individually unpredictable. (See Appendix A for the formal definition.) Note that offsetting keys via xor enjoys this property as xor induces a permutation over the two halves of the key.

BHK [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF], by interpreting encryption randomness as hash keys, show that BRS is selectively RKA secure using a multi-key extension of UCE[S cup ]. In contrast, the adversary in our model retains its capability to adaptively query RKD functions of its choice depending both on the hash key and the ciphertexts that it has previously seen. For this result, although ICE[C ppt ∩ C sup ] is sufficient, the assumption can be fine-tuned to ICE [C] where

C := C ppt ∩ C sup ∩ C dist ∩ C 1-hk 1 ∩ C 0-hk 2 ∩ C 0 2 ∩ C ε 2 .
We defer the formal proof to Appendix A and give a detailed outline here.

The ICE adversary. Given an RKA adversary A, we construct an ICE adversary (D 1 , D 2 ), where D 1 handles the left components of A's RKA queries and D 2 handles the right components as follows.

D 1 (L 1 ) : On initial invocation, generate a hash key hk, a random K 1 , and a random bit b. Store these values and write hk onto the hk-part of the tape. Run A(hk) to get an RKA query ((φ 1 , φ 2 ), M 0 , M 1 ). Output (b 1 , L 2 ) := (⊥, φ 2 ). Proceed as follows in subsequent invocations. Generate and store a random R and write φ 1 (K 1 ) onto the 1st segment (out of three segments) of the x-part of the tape and R onto its 3rd segment. Query Hash to get H. Recover R and resume

A on (R, H ⊕ M b ) to get a new RKA query ((φ 1 , φ 2 ), M 0 , M 1 ), or a bit b . If A outputs a bit b , return (b 1 , L 2 ) := (b = b , ε) and terminate. Else output (b 1 , L 2 ) := (⊥, φ 2 ).
D 2 (L 2 ) : When initially invoked, generate a random K 2 and store it. In all invocations (including the first), recover φ 2 from L 2 . If φ 2 = ε, return (b 2 , L 1 ) := (0, ε) and terminate. Else write φ 2 (K 2 ) onto the 2nd segment of the x-part of the tape. Output (b 2 , L 1 ) := (0, ε).

Unpredictability. We show that D ∈ C for class C as defined above. To this end, we only prove membership in C sup ∩ C dist as other cases follow via syntactic checks. This follows from the following two observations:

(1) The Hash queries are distinct with overwhelming probability since before each query a fresh random value R is written onto the joint tape.

(2) The functions φ 1 and φ 2 are run on independently chosen substrings of the key. Since they are assumed to be individually statistically unpredictable, D 1 observing independently generated random strings corresponding to hash values never gets to know the contents of the tape written by D 2 , and vice versa, D 2 never gets to know what is written on to the tape by D 1 .

KDM security

When the random oracle in the BRS scheme is instantiated with an ICE-secure hash function, we are able to show that the BRS scheme resists a partially adaptive form of KDM security for split key-dependent-message derivation (KDMD) functions φ. As for RKD functions, such KDMD functions consist of sub-KDMD functions φ 1 and φ 2 of the form φ(K

1 K 2 ) := φ 1 (K 1 ) φ 2 (K 2 ).
The adaptivity level that we can tolerate is as follows.

In an initial phase of the attack, the adversary can fully adaptively query split KDMD functions that do not depend on K 2 . That is, for these functions φ 2 (K 2 ) is constant and independent of K 2 and its value can be predicted. In a second phase of the attack, the adversary can query split KDMD functions of its choice as long as either φ 1 (K 1 ) is constant or φ 1 (K 1 ) was used in the first phase. (We emphasize that these functions are not required to be unpredictable.) This model is strong enough to imply IND-CPA security (without any restrictions), a case that could not be treated using UCEs.

The ICE adversary. Let A be a KDM adversary against the BRS scheme in the model above. Our ICE[C ppt ∩ C sup ∩ C dist ] adversary corresponding to A is as follows, where for simplicity we have assumed the lengths of keys, randomness and messages are all . (The ICE class can be further restricted as is shown in Table 2.) In this reduction, D 1 faithfully runs the first stage of the attack, while D 2 runs its second stage. To answer KDM queries, D 2 relies on the "homomorphic" property that H ⊕(x

1 x 2 ) = H ⊕(x 1 0 |x2| )⊕(0 |x1| x 2 ).
D 1 (L 1 ) : When initially invoked, generate a random hk, K 1 and b and store them. Write hk to the hk-part and K 1 to the 1st (out of three) segments of the x-part of the tape. (The segments are of lengths /2, /2 and corresponding to K 1 , K 2 and R respectively.) Output (⊥, ε). On the second invocation, run A(hk) and answer its KDM queries ((φ 0 1 , φ 0 2 ), (φ 1 1 , φ 1 2 )) as follows. Write a fresh random value R onto the 3rd segment of the x-part of the tape. Call Hash to get H, and resume A on (R, H ⊕(φ 1 (K 1 ) M * 2 )), where M * 2 := φ 2 (0 /2 ) is the right K 2 -independent part of the message. Continue this process until A decides to proceed to its second stage. Let st A denote A's state. Generate sufficiently many copies (R 1 , C 1 ), . . . , (R q , C q ) of each of the KDM queries made in the first phase. Let List 1 denote the corresponding list of queried φ b 1 . Return (0, (b, st A , (R 1 , C 1 ), . . . , (R q , C q ), List 1 )) and terminate. D 2 (L 2 ) : When initially invoked, generate a random K 2 , store it, and write it to the 2nd segment of the x-part of the tape. Hand the attack back to D 1 , by outputting (⊥, ε). On the second invocation, parse L 2 appropriately as above. Resume A on st A and answer its KDM queries ((

φ 0 1 , φ 0 2 ), (φ 1 1 , φ 1 2 )) as follows. If φ b 1 ∈ List 1 pick a fresh ciphertext (R, C ) corresponding to φ b 1 and complete the ciphertext preparation by setting C ← C ⊕ (0 /2 φ b 2 (K 2 )).
Otherwise generate a random R, write it onto the 3rd segment of the x-part of the tape, query Hash to get H, and set

C ← H ⊕ (φ b 1 (0 /2 ) φ b 2 (K 2 )).
Resume A on (R, C; st A ) and continue in this manner until A outputs a bit b . Return (b = b , ε) and terminate.

Unpredictability. D's queries are distinct with overwhelming probability as fresh randomness R is written on the tape before each query. Throughout the attack, and when the hash oracle implements a random function, K 2 remains hidden from D 1 as D 1 only sees distinct random values as hash responses. Key K 1 also remains hidden from D 2 as the (incomplete) ciphertext components received from D 1 are random strings.

Hence D ∈ C ppt ∩ C sup ∩ C dist .

Feasibility

In this section we start by showing that random oracles are ICE secure with respect to interesting distinguisher classes (in particular, with respect to the restrictions needed for the presented applications). We then consider the ICE security of practical hash constructions built from fix-input-length (FIL) ROs. In particular, we look at a keyed variant of Liskov's Zipper Hash [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF] and show that it achieves ICE security in the FIL-RO model. Interestingly, we show that both HMAC and NMAC constructions [START_REF] Bellare | Keying hash functions for message authentication[END_REF], which were recently shown to be UCE secure in FIL-ROM [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF], fail to be ICE secure. This result yields a natural counterexample to the composability of HMAC in multi-stage settings, similarly to that given by Ristenpart, Shacham, and Shrimpton in [START_REF] Ristenpart | Careful with composition: Limitations of the indifferentiability framework[END_REF]. Furthermore, it provides a separation between ICE and UCE. Our results also demonstrate that Zipper Hash can provide a higher level of security compared to HMAC when used in multi-stage settings.

ICEs from random oracles

BHK [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF] show that UCE-secure hash functions can be provably constructed in the RO model. The philosophical justifications of this result are that there are no structural weaknesses in the definitional framework, and more importantly, a layered approach to protocol design in the RO model can be enabled [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF]. We show that ICEs also enjoy RO feasibility.

Let H.kl(•) and H.ol(•) be two arbitrary functions as in the syntax of a hash function. Let R be a family of variable-input-length (VIL) ROs (i.e., with domain {0, 1} * ) and range {0, 1} H.ol(λ) . We construct the required hash function H R by defining the key-generation algorithm H.Kg(1 λ ) to return a random hk ←$ {0, 1} H.kl(λ) and the evaluation algorithm H.Ev R (hk, x) to return R(hk x). Our first feasibility result is as follows.

Theorem 1 (ICE feasibility in ROM). The VIL hash function H R constructed above is ICE[C] secure in the VIL-RO model for R for the following (incomparable) classes of adversaries:

C := C poly ∩ C sup and C := C ppt ∩ C cup .
The proof of this theorem is similar to the proof of [BHK13b, Theorem 6.1] for UCEs, and we give the details in Appendix C. Intuitively, we rely on unpredictability of queries to simulate the random oracles used in the construction and implicit in the ICE game independently. Interestingly, distinctness of queries will not be needed in this proof and we do not restrict the classes to C dist . We note that the above classes include all those needed for the applications, as listed in Table 2. We also note that this theorem generalizes the feasibility of UCEs for unpredictable sources in ROM [START_REF] Bellare | Instantiating random oracles via UCEs[END_REF] as it can be easily verified that

C uce ∩ C cup 2 ⊆ C ppt ∩ C cup and C uce ∩ C sup 2 ⊆ C ppt ∩ C sup .

VIL-ICEs from ideal compression

Practical variable-input-length (VIL) hash functions are not monolithic objects. They often follow iterative modes of chaining that convert a fix-input-length (FIL) compression function to one that accepts variable-length inputs. This design principle has been successfully validated via the indifferentiability framework of Maurer, Renner, and Holenstein [START_REF] Ueli | Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology[END_REF][START_REF] Coron | Merkle-Damgård revisited: How to construct a hash function[END_REF], whereby an indifferentiable hash-function construction is shown to securely compose when used in place of a random oracle. As pointed out in [START_REF] Ristenpart | Careful with composition: Limitations of the indifferentiability framework[END_REF], the indifferentiability framework only guarantees composition in single-stage environments. The ICE and UCE games, however, are inherently multi-staged and lie outside the reach of (plain) indifferentiability. Mittelbach [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] develops new techniques to extend the reach of (plain) indifferentiability to certain classes of multi-stage games. In particular, he shows that the HMAC and NMAC constructions are UCE secure. Interestingly, we show that these results do not carry over to the ICE model: HMAC and NMAC provably fail to be ICE secure. On the other hand, we build on Mittelbach's techniques to prove that a variant of Zipper Hash [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF] is provably ICE secure. Attacks on HMAC and NMAC. The HMAC and NMAC constructions are shown in Figure 4. If we denote the iterated compression function used in HMAC by h, then it is easily seen that key hk is only used on the "outer" h-evaluations. Consider an ICE distinguisher D 1 which holds hk, computes the values

y 1 := h(hk ⊕ ipad,
C := C ppt ∩ C sup ∩ C 1,1,1 ∩ C 1-hk 1 ∩ C 0 1 ∩ C 0-hk 2 ∩ C ε 2 .
Zipper Hash. The above attack raises the question if any iterative hash function can be ICE[C] secure for a meaningful class of distinguishers C. We show that a hybrid construction of a keyed version of Liskov's Zipper Hash construction [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF] and chopped Merkle-Damgård (chop-MD) of Coron et al. [START_REF] Coron | Merkle-Damgård revisited: How to construct a hash function[END_REF] is ICE secure. Zipper Hash can be regarded as a basic Merkle-Damgård scheme where the message is processed twice, the second time in reversed block order. chop-MD refers to the construction where a hash value consists only of the first half of the output bits of the final compression function. Our hybrid construction results from adding the chop step to Zipper Hash. Furthermore, we consider a keyed variant of Zipper Hash by prepending the hash key to the message. We assume that key length matches block length, which means that the first and last evaluations of the compression function operate on the hash key. We denote this keyed variant of Zipper Hash by chop-KZIP. Figure 5 shows a schematic diagram of the construction, and Appendix D.1 gives further details.

Theorem 2 (Zipper Hash's ICE security). The VIL hash function chop-KZIP h constructed above is

ICE[C] secure in the FIL-RO model for h : {0, 1} µ × {0, 1} n -→ {0, 1} n for the class C := C poly ∩ C sup ∩ C dist ∩ C 1-hk 1 ∩ C 0 1 ∩ C 0-hk 2 ∩ C ε 2 .
An analogous result holds for polynomial-time distinguishers that are only computationally unpredictable.

In Appendix D.2 we give the proof, where we also present a self-contained introduction to the unsplittability technique [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF]. Appendix D.3 contains the full security analysis.

Note that class C above contains that class used to attack HMAC and hence chop-KZIP h provably achieves a higher level of security in multi-stage games. We note that the reach of the above feasibility result includes all applications scenarios listed in Table 2. In particular, chop-KZIP h can security replace the random oracle in these applications. For this also note that we can easily drop C 0 1 by requesting that in the last round D 1 This result cannot be strengthened for the (large) adversarial classes that were used in Theorem 1. To see this, consider two distinguishers that engage in a distributed computation of chop-KZIP h hash values as follows. Distinguisher D 1 knows hk and m 1 and D 2 knows m 2 , where message m := m 1 m 2 is being hashed. Distinguisher D 1 computes an intermediate hash digest using (hk, m 1 ) and forwards it to D 2 . Distinguisher D 2 now computes another iteration of the hash using m 2 and forwards the result to D 1 . Distinguisher D 1 can now complete the hash computation using its knowledge of (hk, m 1 ) and the intermediate hash digest that it receives.

A straightforward generalization of this attack also rules out multi-pass variants of chop-KZIP h (where messages are processed multiple times in the forward and backward directions), including those whose number of passes is not fixed a priori and can depend on the number of message blocks. This is due to the fact that the number of rounds in an ICE attack is not fixed. This, in turn, raises the question if ICE[C poly ∩ C sup ] is feasible in the FIL-RO model. We conclude the paper with a candidate construction that we conjecture to reach this level of security.

Mix Hash. Let

h : {0, 1} n × {0, 1} n -→ {0, 1} n be a compression function. Let m := m 1 • • • m ∈ ({0, 1} n )
be a message with blocks of length n each. Let Mix h (m) denote the transformation that maps m to M := i j M i,j where M i,j := h(m i , m j ) for 1 ≤ i < j ≤ . (Therefore M has ( -1)/2 blocks.) Now let hk ∈ {0, 1} n be a hash key and define MixHash h (hk, m) := HMAC h (0 n , Mix h (hk m)) .

Note that MixHash h places Θ( 2 ) calls to its compression function h. 12 The design rationale behind MixHash h is as follows. All intermediate digests values M i,j are needed in order to successfully compute a hash value. These values, however, consist of all pairs (m i , m j ) compressed through h. Since h is a monolithic object, M i,j cannot be computed in a distributed way, a strategy that was used in all previous attacks. In other words, one of the distinguishers has to know (hk, m) in full and hence will violate unpredictability. To see this, suppose D 1 does not know m j in full and D 2 does not know m i in full for some i < j. Then there is no way for these parties to learn M i,j := h(m i , m j ) without one of them explicitly quarrying h on (m i , m j ). This however means that both m i and m j are known to the quarrying party, which leads to a contradiction. We leave a formal analysis of MixHash h in the FIL-RO model for h as future work.

A Split RKA Security Symmetric encryption. A symmetric key encryption scheme consists of six PPT algorithms SE := (SE.kl, SE.il, SE.cl, SE.Kg, SE.Enc, SE.Dec) as follows. Algorithms SE.kl, SE.il, SE.cl are deterministic and on input 1 λ specify the key, message and ciphertexts lengths. The key generation algorithm SE.Kg(1 λ ) generates keys K of length SE.kl(1 λ ). The encryption algorithm SE.Enc takes as input a key K and a message M of length SE.il(1 λ ) and returns a ciphertext C of length SE.cl(1 λ ). The decryption algorithm SE.Dec is deterministic and takes as input a key K and a ciphertext C and returns a message M . Correctness requires that for all K that are output by SE.Kg(1 λ ) and for all messages M of length SE.il(1 λ ), and all ciphertexts C ←$ SE.Enc(K, M ) we have that M = SE.Dec(K, C).

Main RKA A Φ,SE (λ) b ←$ {0, 1} K ←$ {0, 1} SE.kl(λ) b ←$ A LR (1 λ ) return (b = b) LR(φ, M0, M1) K ← φ(K) C ←$ SE.Enc(K , M b ) return C Main SPUP P Φ (λ) (K1, K2, φ1, φ2) ←$ P (1 λ ) (K1, K2) ←$ {0, 1} SE.kl(λ)/2 × {0, 1} SE.kl(λ)/2 return (K1 = φ1(K1) ∨ K2 = φ2(K2))
Fig. 6. The RKA and split unpredictability games. A RKA adversary is legitimate if it calls RKEnc only with functions φ = (φ1, φ2) in Φ = Φ1 × Φ2. A SPUP adversary in is legitimate if it outputs a (φ1, φ2) ∈ Φ1 × Φ2.

Split RKD functions. A related-key derivation (RKD) function is a circuit φ which maps keys to keys in some key space. We denote by a family of RKD function sets parameterized by λ by Φ. (We will suppress the explicit dependency on λ to ease notation.) An RKD family Φ is split if there are RKD families Φ 1 and Φ 2 with half the key size such that for any φ ∈ Φ there is a (φ 1 , φ 2 ) ∈ Φ 1 × Φ 2 such that for all K = K 1 K 2 , where K 1 and K 2 are of length half the key size (which for simplicity we assume to be even), we have

φ(K 1 K 2 ) = φ 1 (K 1 ) φ 2 (K 2 ) .
We assume that given a split RKD function φ its split representation consisting of (φ 1 , φ 2 ) can be efficiently computed. Note it might not necessarily be the case that Φ = Φ 1 × Φ 2 .

RKA security. Let SE be a symmetric encryption scheme, and let Φ be a family of RKD functions with key space identical to that of SE. We define the Φ-RKA advantage of an adversary A against SE by

Adv rka SE,Φ,A (λ) := 2 • Pr RKA A SE,Φ (λ) -1 ,
where game RKA A SE,Φ (λ) is shown in Figure 6. We define Φ-RKA security by requiring this advantage to be negligible for all PPT adversaries A.

Split unpredictability. A family of split RKD functions Φ is called split-unpredictable if the advantage of any (possibly unbounded) predictor P against Φ defined by Adv spup Φ,P (λ) := Pr SPUP P Φ (λ) , is negligible, where game SPUP P Φ (λ) is shown in Figure 6. Standard (thats is, non-split) unpredictability is defined similarly.

Theorem 3 (Split RKA security of the BRS scheme). Let SE denote the BRS symmetric encryption scheme, where the hash oracle is instantiated with H. Let Φ be a split RKD function family. Then for any Φ-RKA adversary A against SE there exists an

ICE adversary D = (D 1 , D 2 ) ∈ C ppt ∩ C sup ∩ C dist such that Adv rka SE,Φ,A (λ) ≤ 2 • Adv ice H,D (λ) + Q(λ) 2 2 SE.rl(λ) .
Furthermore, for any predictor P against adversary D constructed above, there are predictors P i for i ∈ {1, 2} such that

Adv pred i,D,P (λ) ≤ Q(λ) • Adv spup Φ,P i (λ) + Q(λ) 2 2 SE.rl(λ)+1 ,
where Q(λ) denotes the number of LR queries of A. φ 1 ( K1 ) for an independent key K1 . In each case, these modifications do no affect P 's success probability. To see this, note that for each i, the distributions of the inputs of P even in the presence of the list of queries Q 1 : Q 2 in the two cases are identical (as P does not get to see K 3-i ).

P i (1 λ ) L1 ← 1 λ while b1 = ⊥ ∨ b2 = ⊥ do k ← 1; (b1, L2) ←$ D Write,Hash 1 (L1) Lki ← Lki : Li k ← 2; (b2, L1) ←$ D Write 2 (L2) L ← [φ internally generated by D1] (hk, x) ←$ P (Coins[Di], Ai, Lki) (R, K1, K2) ← x φ ←$ L; (φ1, φ2) ← φ return (K1, K2, φ1, φ2) Write(j, x) return ε Hash() T [hk, x] ←$ {0, 1} H.ol(λ) A k ← A k : T [hk, x] return T [hk, x]
We now construct the predictors for i = 1, 2. Algorithm P i runs (D, P ) by simulating its Hash queries forgetfully as above and ignoring its Write queries. It forms a list of all RKD functions that are internally generated. It generates random Coins[D i ], forms A 2 via simulated hash values, and Lk i via the list of quarried RKD functions. When P returns (hk, x), algorithm P i returns (K 1 , K 2 , φ 1 , φ 2 ) for a randomly sampled split RKD function (φ 1 , φ 2 ) from the set of all queried RKD functions, and (K 1 , K 2 ) recovered from x. See Figure 8 for the details.

For each i, when P is successful, it guesses the contents of the tape formed via an RKD function with respect to an independent key K3-i With probability 1/Q(λ) algorithm P i picks the RKD query that resulted in the predicted contents of the tape. It follows that for i = 1, 2 we have Pr SPUP

P i Φ (λ) ≥ 1 Q(λ) • Pr Pred P i,D (λ) - Q(λ) 2 2 SE.rl(λ)+1 .
The second part of the theorem follows.

B Other Applications

In this section we give an overview of how the ICE framework can be applied in a number of other cryptographic settings. Proofs of our results below can be formalized following the approach of Appendix A.

B.1 Correlated-input hashing

In correlated-input hashing, an adversary is able to obtain real or ideal hash values of points φ(x), where functions φ are chosen by the adversary from a pre-specified set, and x is a randomly chosen value which is kept hidden from the adversary. The task of the adversary is to guess if the real or ideal hash is being used. An adversary similar to the one given for the RKA security of the BRS scheme can be used to show that a hash function that meets the ICE definition of security also achieves security under correlated inputs as introduced by Goyal, O'Neill, and Rao [START_REF] Goyal | Correlated-input secure hash functions[END_REF]. As before we require that the corresponding correlated-input derivation (CID) functions to split into two parallel components. In this setting, however, not only do we need the sub-CID functions to be individually output unpredictable, but also require that the (full) outputs of any two CID functions φ and φ collide with negligible probability over a random choice of (common) input x. This property is also known as claw-freeness. The ICE distinguishers interact as follows.

D 1 (L 1 ) : When initially invoked, generate a random hk and write it. Also generate a random x 1 and store it. Run A(hk) to get a first query (φ 1 , φ 2 ). Write φ 1 (x 1 ) and output (0, φ 2 ). In subsequent invocations, query Hash to get H and resume A on H to get a new (φ 1 , φ 2 ) or a bit b . In the latter case return (b , ε) and terminate. In the first case write φ 1 (x 1 ) and output (0, φ 2 ). D 2 (L 2 ) : When initially invoked, generate a random x 2 and store it. In all invocations, if L 2 = ε return (0, ε) and terminate. Else recover φ 2 from L 2 and write φ 2 (x 2 ). Output (0, ε).

The claw-freeness property implies that only with negligible probability the Hash oracle will be called on repeated inputs. Moreover, the split unpredictability condition ensures that the contents of the first segment of the input tape are hidden from D 2 and the contents of the second segment of the input tape are hidden from D 1 when these are run with respect to a random oracle. The argument is similar to the RKA setting, but claw-freeness will be used to forgetfully simulate the Hash oracle. Hence D ∈ C sup ∩ C dist .

B.2 Randomness extraction

In a secure randomness extractor no adversary A should be able to distinguish a uniformly chosen random string from the output of the extractor when applied to a high-entropy input generated by a source S. Given a pair (S, A), we construct an ICE adversary as follows.

D 1 (L 1 ) : When initially invoked, generate a random hk. Write hk to the tape. Output (0, ε). On the second invocation, query Hash to get H. Run A(hk, H) to get a bit b . Return (b , ε) and terminate. D 2 (L 2 ) : Run S(1 λ ) to get x. Write x to the tape. Return (0, ε) and terminate.

Note that there is a single Hash query and hence there are no repeat queries. Observe that the hash key hk is statistically hidden from D 2 . Since S is assumed to generate (statistically) high-entropy values, the single query to Hash also remains statistically hidden from D 1 when Hash implements a random oracle. We conclude that D ∈ C sup ∩ C dist .

B.3 Weak pseudorandomness

A weak pseudorandom function F needs to be indistinguishable from a random function by adversaries that are given input/output samples (x, F K (x)) for a randomly chosen key K and randomly chosen points x. Any ICE-secure hash function is also a weak pseudorandom function.

D 1 (L 1 ) : Generate a random hk and write it. Return (0, ε) and terminate. D 2 (L 2 ) : Run the weak-PRF adversary A(1 λ ). When a sample is requested, pick a random value x and write it, call Hash to get H, and resume A(H). When A outputs a bit b , return (b , ε) and terminate.

Statistical unpredictability follows as hk remains hidden from D 2 with respect to a random Hash, and queries x being random remain hidden from D 1 . Note also that with overwhelming probability there are no repeat queries to Hash. Hence D ∈ C sup ∩ C dist .

B.4 One-way hashing

We show that any ICE-secure hash function with a polynomial upper bound on its regularity (i.e., a polynomial number of pre-images for any given image) is one way. D 1 (L 1 ) : Choose a random hk. Choose a random x 1 . Write hk and x 1 . Return (0, hk) and terminate. D 2 (L 2 ) : Choose a random x 2 and write it. Query Hash to get a value H. Run A(hk, H) to get a candidate pre-image (x 1 x2 ). Return (x 2 = x 2 , ε) and terminate.

The above reduction relies on the fact that due to polynomial regularity, a successful A, when run with respect to the hash function, will recover the pre-image used in challenge generation with high probability. On the other hand, when A is run with respect to the random oracle, it will recover x 2 with only a negligible probability.

There is a single query to Hash, the input x 1 chosen by D 1 remains hidden from D 2 with respect to a random oracle, and the input x 2 chosen by D 2 remains hidden from D 1 . The adversary is in To show that the keyed function chop-KZIP h is ICE[C] secure for the class

C sup ∩ C dist .
C := C poly ∩ C cup ∩ C dist ∩ C 0 1 ∩ C 1-hk 1 ∩ C 0-hk 2 ∩ C ε 2
, and an ideal compression function h, we first look at a more restricted class where the hash key hk remains statistically hidden from distinguisher D 2 . We denote the corresponding class of adversaries C skup . We start with the following proposition.

Proposition 1. The chop-KZIP h construction described above is an ICE[C ∩ C skup ]-secure hash function for C as above and whenever h :

{0, 1} µ × {0, 1} n -→ {0, 1} n is a FIL-RO.
Mittelbach [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] presents a composition theorem for multi-stage games which intuitively says that if a game is unsplittable for an iterative hash construction then security in the random-oracle model implies security for the iterative hash construction where the underlying compression function is ideal and assuming that the hash construction is indifferentiable from a random oracle. Thus, in order to prove the proposition 1 it is sufficient to show that:

(1) chop-KZIP is an iterative hash construction (within the framework of Mittelbach [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF]);

(2) chop-KZIP is indifferentiable from a random oracle;

(3) and the ICE game is unsplittable for chop-KZIPfor class C ∩ C skup . When introducing Zipper Hash, Liskov also gave a proof of indifferentiability [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF]. It is easily seen that the function remains indifferentiable under composition with transformation g (dropping half of the bits). We consider (1) and (3) next. chop-KZIP is iterative. Mittelbach [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] gives a framework for hash functions H h that are built by iterating a fixed-input-length compression function h. We describe a simplified version of the framework here and refer to [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] for details. The idea is that the computation of a hash function can be described by a directed acyclic graph that is independent of the compression function h. In other words, for a given key hk and message M , there is an algorithm that constructs an execution graph which, basically, consists of message-block nodes (for message blocks m i in message M ) an IV-node (for the initialization vector), h-nodes representing compression function evaluations and a single g-node representing the final transformation. Furthermore, a universal algorithm Eval given oracle access to h and the unique execution graph for (hk, M ) can compute value H h (hk, M ). In Figure 10 we give the execution graph for a chop-KZIP evaluation for message m 1 . . . m = M and key hk (for ease of presentation we ignore padding). 15 To compute the corresponding hash value relative to function h the generic algorithm Eval h recursively performs the following steps on the execution graph: Search for a node that has no ingoing edges. If it is a message-block node or an IV-node then label all outgoing edges with the corresponding value (message-block or IV) and remove the node from the graph. If the node is an h-node or the single g-node such that all ingoing edges are labeled, then compute the corresponding function taking the labels of the ingoing edges as input, label all outgoing edges with the result and remove the node from the graph. Finally, return the result from the final g computation.

Zipper Hash, chop-MD and also chop-KZIP can be casted in this way and, indeed, Zipper Hash and chop-MD are examples used in [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF].

Unsplittability. It remains to show unsplittability for ICE[C ∩ C skup ]. Unsplittability is defined relative to certain events regarding queries of adversaries to the compression function h. Consider a specific game G H h ,A1,...,Am with respct to an iterative hash construction H h and adversarial procedures A 1 , . . . , A m . In our specific case this would be the ICE game with adversary D. Now consider an execution of game G H h ,A1,...,Am on some random coins r. Then, we can formalize predicates on the compression function queries by the adversaries, for example, we say that the second h-query by adversary A 3 has a certain property. A query is called an initial query if it is of the form (m, IV), that is, the second input to the compression function is the initialization vector. A query (m, x) to h is called a chained query if previously during the game there are h queries (m 0 , x 0 ), . . . , (m , x ) such that x 0 = IV and ∀i = 1, . . . , -1 : x i+1 = h(m i , x i ) and x = h(m , x ) .

Note that here we consider all queries that were made during the game by the adversaries before the point in time where (m, x) is queried. A query is called a result query, if it is a chained query and the structure of the chain corresponds to a correct evaluation of Zipper Hash, that is: hk, m 1 , . . . , m , m , . . . , m 1 , hk for some value hk and message blocks m 1 to m . We say that an h-query (m, x) by an adversary A i is bad if it is a chained query, but that it is not chained with respect to only the queries by adversary A i that occurred before (m, x). Finally, a query is a bad result query if it is a result query and a bad query. We refer to [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] for formal definitions.

We now recall the definition of unsplittability. Let H h be an iterative hash function and let h be an ideal compression function. We say game G, where only adversarial procedures access h directly,16 is unsplittable for H h if for every efficient adversary A 1 , . . . , A m there exist efficient algorithms A * 1 , . . . , A * m and negligible function negl such that

Adv G H h ,A1,...,Am (λ) ≤ Adv G H h ,A * 1 ,...,A * m (λ) + negl(λ) ,
where Adv G H h ,A1,...,Am denotes the success probability of (A 1 , . . . , A m ) in game G with hash construction H h . Moreover, it holds for game G H h ,A * 1 ,...,A * m that bad result queries occur only with negligible probability.

Unsplittability allows composition. We present a self-contained explanation of how unsplittability can be used to argue composition [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF].

Figure 11 (top) shows the ICE game with respect to chop-KZIP and the ICE game with respect to the random oracle is shown on the bottom. We next, give the intuition on how unsplittability allows us to go from an adversary in the Zipper Hash setting to an adversary in the random-oracle setting.

Let function H R denote the hash function with H.Ev R (hk, m) := R(hk m) which is ICE secure in the random-oracle model (see Theorem 1) for a superclass of adversaries considered here. From any efficient ICE adversary D we will, in several steps of which one is using the unsplittability property, construct an adapted adversary

D * such that Pr ICE D chop-KZIP h (λ) ≤ Pr ICE D * H R (λ) + negl(λ)
and thus Adv ice chop-KZIP h ,D (λ) ≈ Adv ice H R ,D * (λ) by the composition theorem of Mittelbach. Note that on the left we are considering the ICE game with respect to chop-KZIP and the ideal compression function h (see also top of Figure 11), while on the right we have the ICE game with respect to hash construction H R in the random-oracle model (Figure 11, bottom), for which we know by Theorem 1 that

Adv ice H R ,D * (λ) ≤ negl(λ) .
We will construct adversary D * as

D * 1 := D Sim 1 D * 2 := D Sim 2
where adversary D will be the adversary guaranteed by the unsplittability property, and simulator Sim R is an indifferentiability simulator that uses the random oracle to simulate h for D .

To construct the simulator Sim R we will use the generic indifferentiability simulator from [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF]. This generic simulator exists and is a good indifferentiability simulator, if the hash function in question is an iterative hash construction and is indifferentiable from a random oracle. As discussed, both properties hold in case of chop-KZIP.

We briefly sketch how the generic simulator works, and refer to [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] for a detailed discussion. Simulator Sim R keeps an internal list of all queries it receives. (Note that each adversary runs an independent copy of Sim R .) On query (m, x) simulator Sim R checks if this query is "part of a valid execution" of chop-KZIP, that is, whether the internal list of queries contains a chain of queries starting from an initial query and leads to this query.

The simulator distinguishes between result queries and non-result queries. If it sees all the queries in the chain of a result query, it is easily seen that the simulator can reconstruct key hk and message M and, thus, recognize a result query. If so it uses its access to the random oracle to return R(hk M ). Else, if a query (m, x) is not a result query, then the simulator responds with a randomly chosen value. We stress that this random value does not depend on the state of the simulator but only on the query and the simulator's random coins (which is important for consistency across different instances of the simulator).

For a single-stage game, the story ends here. The single adversary composed with the simulator will be as good when playing in the random-oracle setting as it is when playing in the chop-KZIP setting. For multi-stage games, however, this does not directly work, as queries by different adversarial stages (in our case D 1 and D 2 ) must be answered consistently. This difference between multi-stage and single-stage games was first noted by Ristenpart, Shacham and Shrimpton [START_REF] Ristenpart | Careful with composition: Limitations of the indifferentiability framework[END_REF]. That is (1) the same query must get the same answer, and (2) if D 1 starts to compute a hash value, sends an intermediate compression function result to D 2 , and D 2 continues the evaluation (note that this corresponds to a bad query) we need to argue that the simulator can still detect the final result query.

Unsplittability, solves problem (2). Given an adversary D we can build an adversary D that has the same advantage in the ICE game, but does not make bad result queries. To solve problem (1), Mittelbach [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] uses a derandomization technique due to Bennet and Gill [START_REF] Bennett | Relative to a random oracle A, P A = N P A = coN P A with probability 1[END_REF] that allows to derandomize the simulator relative to the adversary using the random oracle. Hence any non-potential hash query is answered with a random value that is now generated deterministically (relative to the random oracle) and, thus, the same query (m, x) will be answered identically by any instance of simulator Sim R .

This yields that if we compose adversary D with the derandomized simulator then this adversary will be (almost) as good in the random-oracle setting as adversary D in the chop-KZIP setting. ICE[C ∩ C skup ] is unsplittable for chop-KZIP. We now turn to showing that ICE[C ∩ C skup ] is unsplittable for chop-KZIP. Assume that adversary D during the ICE game makes a bad result query, that is, D 1 , or D 2 makes a query to the compression function without having queried all intermediary queries in the corresponding chain. We have to show that in this case an adversary D exists which is at least as good but, with overwhelming probability, does not make bad result queries. We will show that the original adversary is already of this form.

As h is ideal, a bad query means that an intermediary value must have been communicated from one stage to another (also see [Mit13, Lemma 3.3]). Note that there is direct communication from D 1 to D 2 and indirect communication from D 2 to D 1 via the Hash oracle (i.e., we restrict the second distinguisher to be in C ε 2 ). For the second case, note that via calls to Hash distinguisher D 1 receives value chop-KZIP(hk, M ) for whatever message M was written on the shared tape. Since, chop-KZIP only returns half of the bits of the final compression function computation distinguisher D 1 does not learn a full result of a compression function. Together with the restriction, that distinguishers must always query the Hash oracle on distinct messages we can, thus, conclude that only D 2 can make bad queries. Now assume that D 2 makes a bad result query. Then, by the definition of result query for chop-KZIP, distinguisher D 2 uses hash key hk. We define efficient predictor P as follows. Predictor P takes as input the view of D 2 and outputs one of its h-queries at random. If Q(λ) is an upper bound on the number of h-queries by D 2 then predictor P outputs hash key hk with probability 1/Q(λ) times the probability that D 2 makes a bad result query. This, however, directly contradicts the assumption that adversary D is in class C skup , the class of adversaries where hash key hk remains statistically hidden from D 2 .

It follows that ICE[C ∩C skup ] is unsplittable for chop-KZIP and the proposition follows with the composition theorem for unsplittable games [Mit13, Theorem 4.2].

D.3 chop-KZIP is ICE[C] secure

In this section we extend the previous discussion to general C adversaries where the second distinguisher may or may not learn the hash key.

Theorem 2 (restated from page 12). The VIL hash function chop-KZIP h constructed above is ICE[C] secure in the FIL-RO model for h : {0, 1} µ × {0, 1} n -→ {0, 1} n for the class

C := C poly ∩ C sup ∩ C dist ∩ C 1-hk 1 ∩ C 0 1 ∩ C 0-hk 2 ∩ C ε 2 .
An analogous result holds for polynomial-time distinguishers that are only computationally unpredictable.

Proof. Given the above discussion it remains to show that distinguisher D 2 does not make any bad result queries. Let us assume the contrary, i.e., we fix the randomness r of game ICE[C] and assume that distinguisher D 2 makes a bad result query (m b , x b ) to compression function h. Then, by the definition of a bad query, the query is not properly chained, that is, it is chained with respect to all h-queries by D 1 and D 2 , but it is not chained with respect to only the h-queries by D 2 . Let qry h Di [r] denote the sequence of h-queries by distinguisher D i (for i ∈ {1, 2}) up to and (possibly) including the bad result query (m b , x b ). We distinguish two types of bad result queries BQ-TYPE: BQ-TYPE 1 : The type BQ-TYPE 1 corresponds to the bad query appearing in the first message pass for a message M = m 1 , . . . , m . In Figure 12 we illustrate how the hash function evaluation is divided over the two distinguishers. Formally, there exists an index j ≤ + 1 such that (m 0 , x 0 ), . . . , (m j , x j ) ∈ qry h D1 [r] and (m j+1 , x j+1 ), . . . , (m , x ), (m , x +1 ), . . . , (m 0 , x 2 ) ∈ qry h D2 [r] for x i = h(m i1 , x i-1 ) and (m 0 , x 0 ) := (hk, IV). BQ-TYPE 2 : Type BQ-TYPE 2 corresponds to the bad query appearing in the second message pass. Formally, there exists index + 1 ≤ j ≤ 2 such that (m 0 , x 0 ), . . . , (m , x ), (m , x +1 ), . . . , (m j , x j ) ∈ qry h D1 [r] and (m j+1 , x j+1 ), . . . , (m 0 , x 2 ) ∈ qry h D2 [r] for x i = h(m i1 , x i-1 ) and (m 0 , x 0 ) := (hk, IV).

In the following we construct an adapted distinguisher that does not make any bad result queries. For this we argue that the distinguisher does not make a bad result query in either of the above two cases: We consider the ICE game together with the following adversary (D 1 , D 2 ). Before we describe the distinguishers in detail let us describe the underlying idea.

Result queries are always of the form (hk, x), that is the key is used in the first slot (cf. Figure 12). In order for D 2 to recognize such queries (and perform adequate steps) it must, thus, be able to recognize key hk. We can, however, not simply forward the key from D 1 to D 2 since this might lead to the distinguishers making predictable Hash queries. Instead D 1 forwards a random value TestKey together with value h(hk, TestKey). This allows D 2 to test if a given query from D 2 contains key hk and at the same time hides the key from D 2 unless it is communicated by D 1 . Now that D 2 can recognize potential result queries, D 2 can ensure that the above described types of bad result queries do not occur. For type BQ-TYPE 1 note that the entire second message pass is performed by D 2 . On seeing a result query D 2 can, thus, extract the corresponding message M and recompute chop-KZIP.Ev h (hk, M ) thereby avoiding bad result queries of type BQ-TYPE 1 . For bad result queries of type BQ-TYPE 2 we use a similar trick as before and let D 1 forward the necessary information to recognize and properly answer such queries without needing to call h (and thereby avoiding the bad result query). For this, we let D 1 choose two additional random values TestVal and BlindVal (which it also forwards to D 2 ). Furthermore, D 1 keeps track of all h queries by D 1 and constructs all (partial) chains. For each of those partial chains it then reconstructs the corresponding message M -message M consists j message blocks if the chain consists of j + 1 queries; note that the first query contains key hk-and computes chop-KZIP.Ev h (hk, M ). Let query (hk, x 2j ) be the final h query in that computation. Distinguisher D 1 computes values h(TestVal, x 2j ) and h(BlindVal, x 2j ) ⊕ h(hk, x 2j ) which it also forwards to distinguisher D 2 . Given these two values, distinguisher D 2 can check if a potential result query (i.e., a query of the form (hk, x)) is equivalent to a precomputed result query by D 1 by comparing h(TestVal, x) to the values received from D 1 . If so, it can recover value h(hk, x 2j ) from h(BlindVal, x 2j ) ⊕ h(hk, x 2j ) without having to make the bad result query. Further note, that the additionally leaked values statistically hide key hk as well as x 2j and h(hk, x 2j ) as long as the number of oracle h queries is bounded by a polynomial. We now describe the distinguishers in detail.

Distinguisher D 1 . On the first invocation distinguisher D 1 chooses values TestKey ∈ {0, 1} n and BlindVal, TestVal ∈ {0, 1} µ .

Distinguisher D 1 runs distinguisher D 1 forwarding oracle calls to its own oracles and keeping track of all h queries in set Q. When distinguisher D 1 finishes and outputs leakage L, then distinguisher D 1 stops and outputs the following leakage L . From all queries to h it constructs all valid (partial) chains C as follows: remove query (hk, IV) from Q and add chain 1 := [(hk, IV)] to C, where chain 1 is a sequence of tuples containing only tuple (hk, IV). Repeat the following steps until Q is empty, or no new chain was constructed in the last step. For each chain i ∈ C let (m i , x i ) be the last tuple in the chain. If there exists query (m, x) ∈ Q such that h(m i , x i ) = x then create a new chain chain ← [chain i (m, x)] whereby [chain i (m, x)] we mean the chain that contains all tuples from chain i and as (additional) final tuple in the sequence tuple (m, x). Add chain to C.

In a next step distinguisher D 1 further processes each chain. Let T ← [ ] be an empty table. For each chain ∈ C the following steps are performed. If |chain| = 1 (that is the chain only consists of query (hk, IV)) then nothing is done. Else, set j := |chain| -1. The distinguisher extracts M = m 1 , . . . , m j from chain chain where m i corresponds to the first entry of the ith tuple. It then computes chop-KZIP.Ev h (hk, M ). Let (hk, x 2j ) be the final h query in the computation of chop-KZIP.Ev h (hk, M ). It then sets T [h(TestVal, x 2j )] ← h(BlindVal, x 2j ) ⊕ h(hk, x 2j ) and prepares its leakage as L ← TestKey, TestVal, BlindVal, h(hk, TestKey), T, L .

Distinguisher D 2 . Distinguishers D 2 parses the leakage as (TestKey, TestVal, BlindVal, h(hk, TestKey), T, L) , and runs distinguisher D 2 . It forwards oracle queries to its own oracles keeping track of h-calls in set Q and furthermore handling h-calls as follows: on an h query (m, x) by distinguisher D 2 , distinguisher D 2 computes h(m, TestKey) and compares it to h(hk, TestKey). If the two values do not match, then it forwards the query to h and returns the result to D 2 . If, on the other hand h(m, TestKey) = h(hk, TestKey), then distinguisher D 2 further distinguishes two cases: T [h(TestVal, x)] = ⊥ and T [h(TestVal, x)] = ⊥. In the first case, where table T does not contain an entry for value h(TestVal, x) distinguisher D 2 reconstructs all (tail) chains from Q that end in query (m, x). This can be done with a similar process as the chain reconstruction by D 1 . For each chain it extracts the corresponding message M and computes chop-KZIP.Ev h (hk, M ) where we denote by (hk, x 2j ) the final h query. If for any of these x 2j = x then D 2 returns the result of h(hk, x 2j ) to D 2 . If this is not the case for all reconstructed chains it queries h on (hk, x) and forwards the result to D 2 .

In case table T contains a value for h(TestVal, x), that is, T [h(TestVal, x)] = ⊥, then distinguisher D 2 returns T [h(TestVal, x) ⊕ h(BlindVal, x)

to D 2 . When D 2 stops and outputs a bit b, then so does D 2 .

Analysis. We need to argue that (1) the adapted adversary D has a similar advantage as the original adversary, (2) bad result queries in the ICE game with adversary D and hash construction chop-KZIP h (for ideal h) occur only with negligible probability and (3) D ∈ C, that is, the Hash queries by D 1 and D 2 are statistically unpredictable.

For (1) note that unless D 1 or D 2 make an h query containing any of the random values TestVal, BlindVal, TestKey and furthermore no h-collision occurs then the view of D 1 and D 2 simulated by D 1 and D 2 is perfect. The collision probability is negligible since h is ideal and since values TestVal, BlindVal, TestKey are chosen uniformly at random and not given to D 1 nor D 2 the probability of either distinguisher guessing any of the three constants is also negligible.

For (2) note that the probability of guessing a value within a hash chain for an iterative hash function without honestly computing the chain is negligible (see Lemma 3.3 and its strengthened version in [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF]). As intuition note that h is ideal and thus a value h(m, x) has n bits of min-entropy. As the result of each h query goes into the next query in a chain this entropy is, so to speak, passed on. It follows that for potential bad result queries of type BQ-TYPE 1 distinguisher D 2 will with overwhelming probability recover the correct message M . Similarly for potential bad result queries of type BQ-TYPE 2 table T will with overwhelming probability contain the necessary information to answer the query without making the bad result query.

Finally, for (3) note that all that is additionally leaked by D 1 are the randomly chosen values TestVal, BlindVal, TestKey and the result of specially crafted h-queries of the forms: h(hk, TestKey) and h(TestVal, x 2j ) and h(BlindVal, x 2j ) ⊕ h(hk, x 2j ) All these values are statistically hidden from D 1 and D 2 since values TestVal, BlindVal, TestKey remain hidden. Furthermore, values hk, x 2j and h(hk, x 2j ) remain hidden unless values hk or x 2j can be reconstructed given the view of distinguisher D 2 . For this note that also the unbounded predictors can only make polynomially many h queries.

Fig. 1 .

 1 Fig. 1. The interactions in the UCE game (left) and the ICE game (right).

  h (hk, m) replaced by k 1 for NMAC replaced by k 2 for NMAC

Fig. 4 .

 4 Fig. 4. The HMAC construction. If the dashed boxes are exchanged for independent keys k1 and k2, we obtain NMAC.Here we are ignoring padding.

Fig. 5 .

 5 Fig. 5. The Zipper Hash construction merged with chop-MD [CDMP05] and keyed with hk. The final node g corresponds to the projection to the first half of the output of h. outputs a guess for b which D 2 echoes. With the other restrictions present this change is without loss of generality.This result cannot be strengthened for the (large) adversarial classes that were used in Theorem 1. To see this, consider two distinguishers that engage in a distributed computation of chop-KZIP h hash values as follows. Distinguisher D 1 knows hk and m 1 and D 2 knows m 2 , where message m := m 1 m 2 is being hashed. Distinguisher D 1 computes an intermediate hash digest using (hk, m 1 ) and forwards it to D 2 . Distinguisher D 2 now computes another iteration of the hash using m 2 and forwards the result to D 1 . Distinguisher D 1 can now complete the hash computation using its knowledge of (hk, m 1 ) and the intermediate hash digest that it receives.A straightforward generalization of this attack also rules out multi-pass variants of chop-KZIP h (where messages are processed multiple times in the forward and backward directions), including those whose number of passes is not fixed a priori and can depend on the number of message blocks. This is due to the fact that the number of rounds in an ICE attack is not fixed. This, in turn, raises the question if ICE[C poly ∩ C sup ] is feasible in the FIL-RO model. We conclude the paper with a candidate construction that we conjecture to reach this level of security.

Fig. 8 .

 8 Fig. 8. Φ-SPUP predictor P i corresponding to ICE adversary D = (D1, D2) and predictor P . Here L denotes the list of RKD functions (φ1, φ2) that are internally generated by D as it runs A.

Fig. 10 .

 10 Fig. 10. The Zipper Hash construction [Lis07] merged with chop-MD [CDMP05] evaluated on a message m1 . . . m := m where |m| := k is a multiple of the block size λ and hash key hk. The final node g corresponds to the projection of the first half of the output of h, that is, g : {0, 1} n → {0, 1} n/2 . D.2 Proof for restricted ICE[C ∩ C skup ]

Fig. 12 .

 12 Fig. 12. Splitting of an execution of chop-KZIP.Ev h (hk, M ) for some message M = m1 . . . m where the first distinguisher computes the first j + 1 compression function calls up to and including h(mj, xj), and the second distinguisher computes the remainder.

Table 2 .

 2 Distinguisher classes used (above) and shown feasibility for (below). Here C

Such computational UCE notions are intrinsically needed for applications such as simultaneous had-core bits and deterministic PKEs.

This can be viewed as an interactive analogue of BFM's attack[START_REF] Brzuska | Indistinguishability obfuscation and UCEs: The case of computationally unpredictable sources[END_REF].

In UCEs, "universal" refers to the fact that extraction should work with respect to universal (i.e., all admissible) sources. Analogously, "interactive" in ICEs refers to the fact that extraction should work for sources that can interact.

This is also motivated by impossibility results for statistically secure two-party protocols.

Recall that in RKA security the adversary can see encryptions of messages under keys φ(K) for a random K and functions φ of its choice. In KDM security the adversary can see encryptions of φ(K), under a random key K, for φ's of its choice.

BRS[START_REF] Black | Encryption-scheme security in the presence of key-dependent messages[END_REF] analyze their scheme in the unkeyed RO model, which translates to unkeyed instantiations in practice.

Note that this does not contradict the BFM attack as ROs do not have succinct descriptions.

We emphasize that computational notions are still valuable as combined with our feasibility results, they would enable easier and more modular security proofs in the RO model.

For simplicity we assume that these are just the left and right halves of the key. Our proof will however also apply to any two substrings of super-logarithmic lengths.

Indeed, MixHash is a (highly) offline function: for α ∈ [0, 1], it requires space roughly n √ 1 -α bits after a fraction α of the n ( + 1)/2 bits are processed.

Note that a direct simulation of (D, P ) by P i would not work at this point since P i will guess the output of a sub-RKD with respect to a known key K.

We emphasize that we do not simulate the queries of D1 and D2 to Hash independently. Doing so would arguably lead to an easier simulation of the oracles, but comes at the cost of introducing the extra restriction that the distinguishers belong to C dist . Interestingly, similar restrictions are necessarily in related contexts (e.g.,[START_REF] Bellare | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF]). The reason we can avoid C dist is that the predictor explicitly sees these hash values. When not provided with these values, the distinctness of queries would ensure that these hash values are random and independent, and hence of little use to a predictor.

In[START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] execution graphs are defined to have one message-block node per message-block mi in M . Here, we relax this requirement to support the presentation. We refer to[START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF] for a detailed description of how Zipper Hash is represented in that framework.

This corresponds to a functionality respecting game, in the terminology of Ristenpart, Shacham and Shrimpton[START_REF] Ristenpart | Careful with composition: Limitations of the indifferentiability framework[END_REF].

Acknowledgments

The authors would like to thank Christina Brzuska for taking part in the early stages of this work. Pooya Farshim was supported in part by grant ANR-14-CE28-0003 (Project EnBid).

D Write,Hash 1 (L 1 ; st 1 ) if (st1 = ε) then hk ←$ {0, 1} H.kl(λ) K1 ←$ {0, 1} SE.kl(λ)/2 b ←$ {0, 1} (φ1, φ2, M0, M1; stA) ←$ A(hk) st1 ← (hk, K1, b, φ1, M0, M1, stA) return (⊥, φ2; st1) if (st1 = ε) then (hk, K1, b, φ1, M0, M1, stA) ← st1 R ←$ {0, 1} SE.rl(λ) Write(H.kl(λ) + 1, φ1(K1)) Write(H.kl(λ) + SE.kl(λ) + 1, R) H ←$ Hash() (aux; stA) ← A(R, H ⊕ M b ; stA) if (aux ∈ {0, 1}) then return (aux = b, ε; ⊥) (φ1, φ2, M0, M1) ← aux st1 ← (hk, K1, b, φ1, M0, M1, stA) return (⊥, φ2; st1) D Write,Hash 2 (L 2 ; st 2 ) if (st2 = ε) then K2 ←$ {0, 1} SE.kl(λ)/2 st2 ← K2 if (L2 = ε) then return (0, ε; ⊥) K2 ← st2 φ2 ← L2 Write(H.kl(λ) + SE.rl(λ)/2 + 1, φ2(K2)) return (0, ε; st2) Proof. For an intuition of the proof we refer the reader to Section 4. Given A we construct an ICE adversary (D 1 , D 2 ) as shown in Figure 7. We denote the internal state of D i by st i , which is initialized to ε. We assume, without loss of generality, that A places at least one RKA query.

Let d denote the hidden bit in the ICE game. When d = 1 adversary A is run in an environment that is identical to the RKA game for BRS with respect to hash function λ) . This proves the first part of the theorem.

We next prove that D ∈ C sup i for i = 1, 2. (Membership in C ppt ∩ C dist is easy to check.) Let P be a predictor against D in game Pred P i,D (λ). We construct a predictor P i in game Φ-SPUP. Intuitively, algorithm P i will use D to construct a list of candidate sub-RKD functions whose output it will then predict using P . 13 We consider a slight modification of Pred P i,D (λ), where Hash queries are answered by returning uniform and independent strings in {0, 1} SE.rl(λ) × {0, 1} H.ol(λ) in a forgetful manner. Modulo the distinctness of the sampled R values, this game is identical to the real unpredictability game. Hence the two games are within statistical distance Q(λ) 2 /2 SE.rl(λ)+1 .

We introduce a final modification. If i = 1, when computing the list of queries Q 1 and Q 2 the game uses φ 2 ( K2 ) for an independent key K2 . Analogously, when i = 2, when computing Q 1 and Q 2 the game uses C Proof of Theorem 1: ICE Feasibility in ROM Let H.kl(•) and H.ol(•) be two arbitrary functions as in the syntax of a hash function. Let R be a family of variable-input-length (VIL) ROs (i.e., with domain {0, 1} * ) and range {0, 1} H.ol(λ) . We construct the required hash function H R by defining H.Kg(1 λ ) to return a random hk ←$ {0, 1} H.kl(λ) and the evaluation algorithm H.Ev R (hk, x) to return R(hk x).

Theorem 1 (restated from page 11). The VIL hash function H R constructed above is ICE[C] secure in the VIL-RO model for R for the following (incomparable) classes of adversaries:

Proof. We prove the theorem for the first class corresponding to poly-query and statistically unpredictable distinguishers. The proofs for computational distinguishers that are computationally unpredictable are analogous. The only difference is that the predictors that we construct run the distinguishers, and hence their assumed computational complexities should match.

Consider games G 1 -G 3 in Figure 9, where game G 1 does not include the boxed statements. Let d denote the challenge bit in the ICE security game. Game G 1 is identical to the ICE game with d = 1, where Hash implements the construction. Game G 3 is identical to the ICE game with d = 0, where Hash is a lazily sampled random function independent of the random oracle used in the construction. In all games, Ro 1 and Ro 2 are the interfaces for the random oracle given to D 1 and D 2 respectively. We have that 9 on top with boxed statements included) simply adds sets for bookkeeping and two bad flags. Therefore, Pr G D 1 (λ) = Pr G D 2 (λ) . Game G 3 (shown in Figure 9 bottom) exchanges the random oracle for adversaries D 1 and D 2 by an independent oracle; that is, the answers are no longer consistent with those of the Hash oracle (note the different tables T and H used). As long as a full query to Hash (with the hash key prepended) never collides with one to Ro 1 or Ro 2 , this modification does not change the game. 14 This collision event is captured by a flag bad. Since G 2 and G 3 are identical until bad,

Flag bad can be set in two ways:

Event E 1 : An Ro 1 query of D 1 matches a query of either D 1 or D 2 to Hash. Event E 2 : An Ro 2 query of D 2 matches a query of either D 1 or D 2 to Hash.

Fig. 9. Games for the random-oracle feasibility of ICEs.

We bound the proabrbility of each of these events in G 3 via the unpredictability of D 1 in the first case, and the unpredictability of D 2 in the second case.

The predictors. We bound the probability that flag bad gets set via a D 1 query to Ro 1 by constructing a predictor P R 1 against D 1 (event E 1 above). Predictor P R 1 uses a full view of D 1 provided in its inputs and R to perfectly simulate a run of D 1 in the ICE game with respect to an (independent) random implementation of the hash oracle (see remark on page 8). Hence P R 1 runs D 1 in an environment that is identical to G 3 . Algorithm P R 1 picks a random query v of D 1 to Ro 1 and outputs it. Whenever flag bad is set due to event E 1 , algorithm P R 1 wins the prediction game as long as it correctly guesses the query that set bad. Hence, if we let Q 1 (λ) denote an upper bound on the number of Ro 1 queries of D 1 , we may conclude that

The second predictor P R 2 corresponding to event E 2 is constructed and analyzed analogously:

It follows that

The theorem follows for D ∈ C poly ∩ C sup .

D Proof of Theorem 2: VIL-ICEs from FIL-RO

In the following section we consider instantiatoions of ICEs via a hybrid between Zipper Hash [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF] and chop-MD [START_REF] Coron | Merkle-Damgård revisited: How to construct a hash function[END_REF] and analyzed in the ideal compression function model (where the compression function is assumed to be a fixed-input-length random oracle).

D.1 Chopped & keyed Zipper Hash

Liskov's Zipper Hash can be seen as a variant of the Merkle-Damgård construction [START_REF] Ralph | One way hash functions and DES[END_REF][START_REF] Damgård | A design principle for hash functions[END_REF]. The basic Merkle-Damgård construction H h (m 1 , . . . , m ) is computed recursively as H h (m 1 , . . . , m ) := h(m , x -1 ) where x 0 := IV is some initialization vector and x i := h(m i , x i-1 ) is computed as the compression function evaluated on the current message block and the last chaining value. In the Zipper Hash construction, the message is not passed once, but twice, the second time in reversed block order. In Liskov's original formulation of Zipper Hash [START_REF] Liskov | Constructing an ideal hash function from weak ideal compression functions[END_REF] two independent compression functions were used, one for the first message pass, and one for the second. For our proof, this is not necessary, and we consider only a single (idealized) compression function. We denote this construction with ZH h . The chop Merkle-Damgård (chop-MD) construction is essentially the basic Merkle-Damgård construction appended by a projection map that drops half of the bits of the final compression function evaluation [START_REF] Coron | Merkle-Damgård revisited: How to construct a hash function[END_REF]. We consider a hybrid construction: Zipper Hash with a final projection.

Zipper Hash is specified as an unkeyed hash function. We will, however, consider a keyed variant of Zipper Hash, and define chop-KZIP h as chop-KZIP h (hk, M ) := g(ZH h (hk M )) , where we assume that hk is padded to the length of one message block and g is a projection to the first half of its input. As a consequence, during the evaluation of chop-KZIP h (hk, M ), the first call to the compression function as well as the last call, both take the key hk as input, which is crucial to proving that the construction is ICE secure. We give a schematic diagram of an evaluation of the resulting hybrid called Chopped & Keyed Zipper Hash (chop-KZIP) in Figure 10. Note, that chop-KZIP is also a key-prefixed hash construction in the terminology of Mittelbach [START_REF] Mittelbach | Salvaging indifferentiability in a multi-stage setting[END_REF].