Keywords

1 Introduction

Known-Key Attacks and Our Approach. Known-key distinguishers for block ciphers were introduced by Lars Knudsen and Vincent Rijmen at ASIACRYPT 2007 [25]. In the classical single secret-key setting, the attacker does not know the randomly generated key and aims to recover it or build another distinguisher for the cipher. The security model in known-key attacks is quite different though: the attacker knows the randomly drawn key the block cipher operates with and aims to find a structural property for the cipher under the known key – a property which an ideal cipher (a permutation drawn at random) would not have. An example of such a structural property from [25] is as follows. For an \(n\)-bit block cipher with a known key, the goal is to find a plaintext/ciphertext pair with the least \(s<n/2\) significant bits zero. For the ideal cipher, the adversary needs to invest about \(2^s\) encryptions. A cipher that allows one to find such a pair with much less effort than \(2^s\) encryptions is considered insecure in the known-key model. The seminal work [25] proposes a distinguisher for a permutation-based 7-round Feistel cipher and for 7 rounds of AES.

Since their introduction, known-key attacks have been a major research topic in the symmetric-key community. In explicit terms, there has been a great deal of effort towards refining and extending the distinguishers proposed by Knudsen and Rijmen, including generalizations to Rijndael [34, 44], SP-based Feistel ciphers [45–47] and some other constructions [17, 35, 37]. More importantly though, implicitly, known-key attacks have drawn attention to the security of block ciphers in the open key model where the adversary knows or even chooses keys. We think it is to some extent this renewed attention that eventually has given rise to a recent line of cryptanalytic results for the full AES: chosen-key distinguishers [7], related-key attacks [5–7] and single-key biclique meet-in-the-middle attacks [8] — all essentially exploiting the weaknesses of AES in the open key model.

Despite this cumulative impact in the symmetric-key community over the last years, known-key attacks have been known to be difficult to formalize since, formally speaking, it is not clear what an exploitable structural property of a block cipher under a known key is. There have been several attempts to solve the problem in general but we are not aware of any published results here. In this work, we take a slightly different approach to the problem: we focus on known-key distinguishers for block ciphers based on idealized primitives such as randomly drawn functions or permutations (examples of such constructions are balanced Feistel ciphers, generalized Feistel ciphers, and (multiple) Even-Mansour ciphers). For such block ciphers, we formulate the new notion of known-key indifferentiability which we believe captures the known-key security. To demonstrate its meaningfulness, we prove that the existing known-key attacks on block ciphers with idealized primitives actually lead to the violation of this notion. To demonstrate its constructiveness, we prove Feistel and Even-Mansour known-key indifferentiable for a sufficient number of rounds.

Indifferentiability Framework. Traditionally, block ciphers have been examined under the classical notion of indistinguishability. In that setting a block cipher \(\mathcal {C}\) is claimed secure if it is (computationally) indistinguishable from a fixed random permutation \(\mathcal {R}\) with the same domain and range as \(\mathcal {C}\). In other words, an attacker has to distinguish between \(\mathcal {C}\) and \(\mathcal {R}\) when placed in either real or ideal worlds, respectively. The seminal paper [27] of Luby and Rackoff showed that three (four) rounds of the Feistel construction, with independent pseudorandom functions in each round, yield a pseudorandom permutation (strong pseudorandom permutation) where the distinguisher does not have access to the internal functions. This result was followed by a number of works [21, 30, 36, 38–41, 52]. On the other hand, the indistinguishability of Even-Mansour cipher was only analyzed by [9, 18, 51]. Indistinguishability has been established as the de facto security notion for block ciphers because in the encryption setting the intended use of the cipher key is in a secret manner; a fact comfortably accommodated by the notion of indistinguishability.

However, block ciphers find numerous and important uses beyond encryption. Block ciphers have been used as a building block for hash functions[19, 23, 26, 31, 33, 42, 50].Footnote 1 Here, the block cipher should work towards achieving the desired property of the higher level structure, and the cipher key is not necessarily secret, but known or easy to manipulate by a distinguisher. Clearly, indistinguishability cannot provide strong security guarantees in the open key model: a distinguisher’s task becomes trivial once the key is known or chosen. Even more, if for example we decide to examine the indistinguishability “security” of a block cipher built out of an ideal underlying primitive (by explicitly giving to the distinguisher additional access to the internal primitive) in the open key setting, then again the notion indistinguishability falls short. A straightforward distinguishability attack here is possible in only two queries: one \((K, M)\) query to the cipher \(\mathcal {C}\) to obtain \(Y\) and one message and/or public key dependant \(x\) input to the underlying primitive \(\mathcal {P}\) to help him compute \(Y'\) as a function of \(\mathcal {C}_K\). The distinguisher needs to only verify if \(Y\) equals \(Y'\), which is true for the real construction \(\mathcal {C}\) and false with high probability for a random permutation \(\mathcal {R}\). The weakness of such an indistinguishability notion that allows access to the internal primitives lays in the fact that there is an obvious “constructive” gap in the ideal world where no communication between \(\mathcal {R}\) and \(\mathcal {P}\) is provided (as opposed to the real world where \(\mathcal {C}\) evaluates on \(\mathcal {P}\)).

It is here where the notion of indifferentiability of Maurer et al. [29] comes into use to allow for: (i) arguing security in the open key model and (ii) enabling the distinguisher to gain access to the input/output behavior of the underlying primitive. The notion of indifferentiability argues the security of an idealized system built upon ideal underlying components, such as random functions or permutations. Initially, indifferentiability was used to analyze hash functions [1–4, 11, 20], more recently results for block ciphers have also appeared. In [15], Dodis and Puniya proved that the Feistel construction with a super-logarithmic number of rounds (random functions) is indifferentiable from an ideal permutation in the honest-but-curious indifferentiability model, where the adversary can only query the global Feistel construction and get all the intermediate results. The work of Coron et al. [10] attempted an indifferentiability proof for the Feistel construction with 6 rounds to obtain a fixed random permutation. But it were Holenstein et al. [22] who succeeded in proving a 14 round Feistel construction indifferentiable from a fixed random permutation. Weaker variants of the indifferentiability notion have appeared also in [16, 28, 53].

In its essence, indifferentiability, similarly to indistinguishability, aims at estimating the adversarial distinguishing advantage between the cipher \(\mathcal {C}\) and \(\mathcal {R}\) in the real and ideal worlds, respectively. Indifferentiability allows the adversary to access the underlying primitive(s) where the underlying ideal primitive(s) in the ideal world is replaced by a simulator \(\mathcal {S}\), which aims to both mimic the behavior of the ideal primitive(s) and provide for responses that evaluate correctly when computed under the cipher composition. To fulfill the latter task the simulator is given access to the idealized system \(\mathcal {R}\). That functionality of \(\mathcal {S}\) allows for overcoming the existing “constructive” gap in the indistinguishability definition.

In fact, indifferentiability was introduced as the right notion to argue security of a block cipher as an ideal cipher, where each key names a new randomly chosen permutation. This theoretical treatment of block ciphers allows one to argue security results in a setting where the adversary freely chooses the key and each chosen key namely fixes a new random permutation. But while this interpretation might accommodate the analysis of block ciphers in the chosen key setting, it appears to be too strong for the case when the key is actually fixed but publicly known and thus the permutation is fixed. This brings us to our newly proposed notion of known-key indifferentiability (\(\mathrm {iff}{\text {-}}\mathrm {KK}\)), which examines the security of a block cipher as a composition from ideal primitives under a known key. Notice that an indifferentiability related view was already taken in the work of Mandal, Patarin and Seurin [28], who introduced the notion sequential indifferentiability and then relate it to that of correlation intractability in the ideal model to argue known key security. Our \(\mathrm {iff}{\text {-}}\mathrm {KK}\) notion is however more general and differs by the fact that it does not limit the adversary to make queries first to the underlying primitive and then to the cipher. Moreover, \(\mathrm {iff}{\text {-}}\mathrm {KK}\) explicitly provides the distinguisher with a public key which directly influences the queries to the block cipher and potentially the ones to the underlying primitives (whenever that is required by composition).

Our Contributions. The contributions of this paper are as follows:

Known-key attacks on type-I generalized Feistel networks. Knudsen-Rijmen [25] proposed known-key distinguishers on 7 rounds of the 2-line (balanced) Feistel network: GFN\(_{(2,7)}\) with any permutations and explicit key addition at the beginning of the round function. We propose a known-key attack on \(4\ell -1\) rounds of an \(\ell \)-line permutation-based type-I generalized Feistel network: GFN\(_{(\ell ,4\ell -1)}\) also with explicit key addition at the beginning of the round function. See Sect. 3.

Known-key indifferentiability. We propose a way to formalize the known-key security of block ciphers based on ideal primitives via the indifferentiability framework and put forward the notion of known-key indifferentiability in Sect. 4. By no means we claim to have formalized what a known-key attack is for all block ciphers and all existing attacks, but we do believe to have found an appropriate notion when the underlying components of the cipher are ideal (e.g. random permutations or random functions).

Meaningfulness of known-key indifferentiability. To show that our notion of known-key indifferentiability is useful and meaningful, we prove that the known-key attacks proposed to date on block ciphers with ideal components and explicit key input (namely, the attack by Knudsen-Rijmen on 7-round Feistel with permutations, our attack on (\(4\ell -1\))-round \(\ell \)-line type-I Generalized Feistel construction, and an attack by Coron et al. and Mandal et al. [10, 28]) imply the known-key differentiability bound computed in Sect. 5.

Constructiveness of known-key indifferentiability. To demonstrate the constructiveness of our known-key indifferentiability notion, we prove two popular generic block cipher constructions known-key indifferentiable in Sect. 6. First, regarding the general indifferentiability result of [22], we prove that 14 rounds of balanced Feistel with random functions are known-key indifferentiable with a security bounds of \(O(q^{16}/2^{n/2})\). Second, we prove that the multiple Even-Mansour construction instantiated with random permutations is perfectly known-key indifferentiable for any number of rounds starting from 1. As opposed to Feistel ciphers, this puts forward the Even-Mansour construction as particularly suitable for building known-key resistant ciphers.

2 Block Cipher Constructions

In this work, we mainly focus on known-key security of generalized Feistel networks and multiple Even-Mansour constructions.

2.1 Generalized Feistel Networks

Feistel networks are very common block cipher designs, dating back to the design of Lucifer [49], and many generalizations of this design appeared in literature. In our work, we focus on type-I networks, as described by Zheng, Matsumoto and Imai [54], simply referring to it as generalized Feistel networks.

The generalized Feistel network GFN\(_{(\ell ,r)}:\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}\) consists of \(r\) evaluations of a fixed random permutation \(\pi \) on \(n/\ell \) bits, and it uses \(\ell \) lines. For \(i\in \{1,\ldots ,r\}\), the \(i\)-th round \(\psi _i\) of GFN\(_{(\ell ,r)}\) is defined as

$$\begin{aligned} \psi _i(p_1,\ldots ,p_\ell )=(p_2\oplus \pi (p_1\oplus k_i),p_3,\ldots ,p_\ell ,p_1)\,, \end{aligned}$$

where \(k_1,\ldots ,k_r\) denote the round keys derived from the master key \(K\) using some key schedule. The function \(\psi _i\) is depicted in Fig. 1. In this work, we also consider a slightly modified variant of GFN\(_{(\ell ,r)}\), where no keys are XORed with the inputs to the primitive, but instead, \(r\) different random functions \(f_1,\ldots ,f_r\) are employed. We refer to this construction as GFNR\(_{(\ell ,r)}\), where the \(i\)-th round is defined as \(\psi _i(p_1,\ldots ,p_\ell )=(p_2\oplus f_i(p_i),p_3,\ldots ,p_\ell ,p_1)\). Note that by construction, GFNR\(_{(\ell ,r)}\) does not have an explicit key input. However, one can append an \(n\)-bit subkey to the input of function \(f_i\) if explicit key input is needed. In this case, random function \(f_i\) maps \((1+1/\ell )n\) bits to \(n/\ell \) bits.

Luby and Rackoff showed in the setting where independent pseudorandom functions are used, three (four) rounds of the balanced Feistel construction (that is, GFNR\(_{(2,3)}\) and GFNR\(_{(2,4)}\)) yield a pseudorandom permutation (strong pseudorandom permutation) where the distinguisher does not have access to the internal functions. This research line was followed up by a number of works [21, 30, 36, 38–41, 52].

2.2 Multiple Even-Mansour

The multiple Even-Mansour construction relates to the notion of key-alternating ciphers, which itself goes back to Daemen [12–14] and was used in the design of AES. However, it was Knudsen [24] who proposed to instantiate multiple-round key-alternating ciphers with randomly drawn, fixed and public permutations. The single-round key-alternating construction or EM\(_1\) was proposed by Even-Mansour [18].

Multiple Even-Mansour constructions EM\(_r:\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}\) consist of \(r\) evaluations of a fixed permutation \(\pi \) on \(n\) bits, which are separated by key addition. In other words,

$$\begin{aligned} \text {EM}_r(K,p)= k_r\oplus \pi (\cdots \pi (k_1\oplus \pi (k_0\oplus p))\cdots )\,, \end{aligned}$$

where \(k_0,\ldots ,k_r\) denote the round keys derived from the master key \(K\) using some key schedule. For \(i\in \{1,\ldots ,r\}\), round \(i\) of EM\(_r\) (together with the addition of the previous key) is depicted in Fig. 1.

Fig. 1.
figure 1

For \(1\le i\le r\), round \(i\) of GFN\(_{(\ell ,r)}\) with \(\ell \) input lines (left) and EM\(_r\) (right, with XOR of previous key additionally included).

Full size image

In the setting where the \(r\) permutations are distinct and the round keys are independently generated and secret, Bogdanov et al. [9] recently proved that EM\(_r\) is indistinguishable from a randomly drawn permutation with less than \(2^{2n/3}\) queries for \(r\ge 2\), and Steinberger [51] improved this result to indistinguishability up to \(2^{3n/4}\) queries for \(r\ge 3\).

3 Known-Key Attacks on GFN\(_{(\ell ,r)}\)

Consider GFN\(_{(\ell ,4\ell -1)}\) based on \(r=4\ell -1\) calls to a random invertible function \(\pi \). Label the incoming lines as \(p=(p_1,\ldots ,p_\ell )\) and the outgoing ones as \(c=(c_1,\ldots ,c_\ell )\). Denote by \(K\) the random, but known, master key, and let \(k_1,\ldots ,k_r\) be the \(r\) round keys. Denote the inputs to the \(i\)-th \(\pi \)-evaluations by \(s_i \oplus k_i\). Note that there is a one-to-one correspondence between \(p\) and \((s_1,\ldots ,s_\ell )\), as well as between \(c\) and \((s_{r-\ell +1},\ldots ,s_r)\). Following the idea of Knudsen and Rijmen [25], the goal is to find tuples \(p,p'\) with corresponding \(c,c'\) that satisfy \(p_1\oplus c_2=p_1'\oplus c_2'\). Note that \(c_2=s_{r-\ell +2}\) by construction, and in our analysis we refrain from computing \((s_{r-\ell +3},\ldots ,s_r)\) if not needed.

Before describing the inputs \(p,p'\) chosen by the attacker, we first explain the attack. Let \(x\) be an arbitrary value, and consider \(z,\alpha ,\beta ,\gamma ,\delta \) variables to be determined later. Distinguisher \(\mathsf {D}\) aims at the following intermediate state values

$$\begin{aligned} s_{\ell +1}&= x\oplus k_{\ell +1}&s_{\ell +1}'&= x\oplus \alpha \oplus k_{\ell +1} \\ s_{\ell +2}&= x\oplus k_{\ell +2}&s_{\ell +2}'&= x\oplus \beta \oplus k_{\ell +2} \\ s_{\ell +3}&= x\oplus k_{\ell +3}&s_{\ell +3}'&= x\oplus k_{\ell +3} \\&\;\;\vdots&\;\;\vdots \\ s_{2\ell -1}&= x\oplus k_{2\ell -1}&s_{2\ell -1}'&= x\oplus k_{2\ell -1} \\ s_{2\ell }&= z\oplus k_{2\ell }&s_{2\ell }'&= z\oplus \gamma \oplus k_{2\ell } \\ s_{2\ell +1}&= x\oplus \delta \oplus k_{2\ell +1}&s_{2\ell +1}'&= x\oplus k_{2\ell +1}\,. \end{aligned}$$

Here, we point out two exceptions from this general (otherwise) description of the attack. Firstly, for \(\ell =2\), \(s_4\) and \(s_4'\) adapt the value of \(s_{2\ell }\) and \(s_{2\ell }'\), and similarly for \(s_5\) and \(s_5'\). Secondly, for \(\ell =3\), \(s_6\) and \(s_6'\) follow the notation of \(s_{2\ell }\) and \(s_{2\ell }'\), and similarly for later state values. For \(\ell >3\) the description is non-ambiguous. Then, \(s_\ell ,\ldots ,s_1\) and \(s_{2\ell +2},\ldots ,s_{r}\) are computed in the straightforward way (i.e. using \(s_i = s_{i+\ell }\oplus f(s_{i+\ell -1}\oplus k_{i+\ell -1})\)), and similar for the \(s'\)-values. For \(\ell >3\), the general attack is depicted in Fig. 2. By construction, \(z\) and \(\gamma \) need to be such that \(\pi (z)=\delta \oplus k_{\ell +1}\oplus k_{2\ell +1}\) (from \(s_{\ell +1}\), \(s_{2\ell }\), and \(s_{2\ell +1}\)) and \(\pi (z\oplus \gamma )=\alpha \oplus k_{\ell +1}\oplus k_{2\ell +1}\) (from \(s_{\ell +1}'\), \(s_{2\ell }'\), and \(s_{2\ell +1}'\)). For the rest of the attack, we distinguish among \(\ell =2\), \(\ell =3\), and \(\ell >3\).

\(\ell =2\). Starting with \(\ell =2\) (this is in fact the attack of Knudsen and Rijmen [25]). Note that \(\beta \) does not occur in the analysis. We simply set \(\gamma =0\), and thus \(\delta =\alpha \) and we require \(\pi (z)=\alpha \oplus k_3\oplus k_5\). It remains to determine the value \(\alpha \). We have:

$$\begin{aligned} p_1 = s_1&= x\oplus k_3\oplus \pi (z\oplus k_2\oplus k_4\oplus \pi (x)) \\ c_2 = s_7&= x\oplus \alpha \oplus k_5\oplus \pi (z\oplus k_4\oplus k_6\oplus \pi (x\oplus \alpha )) \\ p_1' = s_1'&= x\oplus \alpha \oplus k_3\oplus \pi (z\oplus k_2\oplus k_4\oplus \pi (x\oplus \alpha )) \\ c_2' = s_7'&= x\oplus k_5\oplus \pi (z\oplus k_4\oplus k_6\oplus \pi (x))\,. \end{aligned}$$

As demonstrated in [25], \(p_1\oplus c_2=p_1'\oplus c_2'\) holds if \(\alpha =x\oplus \pi ^{-1}(\pi (x)\oplus k_2\oplus k_6)\). The tuples \(p\) and \(p'\) queried by \(\mathsf {D}\) are easily derivable and not discussed.

\(\ell =3\). Next we consider \(\ell =3\). This case turns out to require a special treatment. We have:

$$\begin{aligned} p_1 = s_1&= x\oplus k_4\oplus \pi (z\oplus k_3\oplus k_6\oplus \pi (x)) \\ c_2 = s_{10}&= x\oplus \delta \oplus k_7\oplus \pi (z\oplus k_6\oplus k_9 \oplus \pi (x\oplus k_5\oplus k_8\oplus \pi (x\oplus \delta ))) \\ p_1' = s_1'&= x\oplus \alpha \oplus k_4\oplus \pi (z\oplus \gamma \oplus k_3\oplus k_6\oplus \pi (x\oplus \beta )) \\ c_2' = s_{10}'&= x\oplus k_7\oplus \pi (z\oplus \gamma \oplus k_6\oplus k_9\oplus \pi (x\oplus \beta \oplus k_5\oplus k_8\oplus \pi (x)))\,. \end{aligned}$$

Note that

$$\begin{aligned} p_1\oplus c_2&= \pi (z)\oplus \pi (z\oplus k_3\oplus k_6\oplus \pi (x)) \,\oplus \\&\qquad \qquad \qquad \quad ~\pi (z\oplus k_6\oplus k_9 \oplus \pi (x\oplus k_5\oplus k_8\oplus \pi (x\oplus \delta ))) \\ p_1'\oplus c_2'&= \pi (z\oplus \gamma ) \oplus \pi (z\oplus \gamma \oplus k_3\oplus k_6\oplus \pi (x\oplus \beta )) \,\oplus \\&\qquad \qquad \qquad \quad \pi (z\oplus \gamma \oplus k_6\oplus k_9\oplus \pi (x\oplus \beta \oplus k_5\oplus k_8\oplus \pi (x)))\,. \end{aligned}$$

Our goal is these values to satisfy \(p_1\oplus c_2=p_1'\oplus c_2'\), but the same approach as for \(\ell =2\) (and [25]) does not work here. However, if we take \(\delta \) such that \(\pi (x\oplus k_5\oplus k_8\oplus \pi (x\oplus \delta ))=k_6\oplus k_9\), and \(\beta \) such that \(\pi (x\oplus \beta \oplus k_5\oplus k_8\oplus \pi (x))=k_6\oplus k_9\), and \(\gamma = \pi (x)\oplus \pi (x\oplus \beta )\), the desired equation is satisfied. Then, by construction, \(z=\pi ^{-1}(\delta \oplus k_4\oplus k_7)\) and \(\alpha =\pi (z\oplus \gamma )\oplus k_4\oplus k_7\). The tuples \(p\) and \(p'\) queried by \(\mathsf {D}\) are easily derivable and not discussed.

Fig. 2.
figure 2

Attack of Sect. 3 for \(\ell >3\). Parameter \(x\) can be freely chosen, parameters \(\alpha \) (\(=\beta \)), \(\gamma \), and \(z\) depend on \(x\) and the round keys, and are explained in the text.

Full size image

\(\ell >3.\) Remains to consider the general case, \(\ell >3\). This attack is visualized in Fig. 2. In this case, we simply set \(\gamma =0\), and thus \(\delta =\alpha \) and we require \(\pi (z)=\alpha \oplus k_{\ell +1}\oplus k_{2\ell +1}\). It remains to determine the values \(\alpha \) and \(\beta \). We find:

$$\begin{aligned} p_1 = s_1&= x\oplus k_{\ell +1}\oplus \pi (z\oplus k_\ell \oplus k_{2\ell }\oplus \pi (x)) \\ c_2 = s_{3\ell +1}&= x\oplus \alpha \oplus k_{2\ell +1}\oplus \pi (z\oplus k_{2\ell }\oplus k_{3\ell } \oplus \tilde{\pi }(K,x,\alpha ))\\ p_1' = s_1'&= x\oplus \alpha \oplus k_{\ell +1}\oplus \pi (z\oplus k_\ell \oplus k_{2\ell }\oplus \pi (x)) \\ c_2' = s_{3\ell +1}'&= x\oplus k_{2\ell +1} \oplus \pi (z\oplus k_{2\ell }\oplus k_{3\ell }\oplus \tilde{\pi }'(K,x,\alpha ,\beta ))\,, \end{aligned}$$

where

$$\begin{aligned} \tilde{\pi }(K,x,\alpha )&= \pi (x\oplus k_{2\ell -1}\oplus k_{3\ell -1} \oplus \cdots \pi (x\oplus k_{\ell +2}\oplus k_{2\ell +2}\,\oplus \\&\qquad \qquad \qquad \qquad \pi (x\oplus k_{\ell +1}\oplus k_{2\ell +1}\oplus \pi (x\oplus \alpha )))\cdots )\\ \tilde{\pi }'(K,x,\alpha ,\beta )&= \pi (x\oplus k_{2\ell -1}\oplus k_{3\ell -1}\oplus \cdots \pi (x\oplus \beta \oplus k_{\ell +2}\oplus k_{2\ell +2}\,\oplus \\&\qquad \qquad \qquad \qquad \pi (x\oplus \alpha \oplus k_{\ell +1}\oplus k_{2\ell +1}\oplus \pi (x)))\cdots )\,. \end{aligned}$$

Note that

$$\begin{aligned} p_1\oplus c_2\oplus p_1'\oplus c_2' =&\;\pi (z\oplus k_{2\ell }\oplus k_{3\ell } \oplus \tilde{\pi }(K,x,\alpha )) \,\oplus \\&\;\pi (z\oplus k_{2\ell }\oplus k_{3\ell }\oplus \tilde{\pi }'(K,x,\alpha ,\beta ))\,. \end{aligned}$$

We now put \(\alpha \) to satisfy \(\tilde{\pi }(K,x,\alpha ) = k_{2\ell }\oplus k_{3\ell }\) (note that by the construction of \(\tilde{\pi }\) this is really possible), and \(\beta \) to satisfy \(\tilde{\pi }'(K,x,\alpha ,\beta ) = k_{2\ell }\oplus k_{3\ell }\) for this given \(\alpha \). This choice is well-defined: \(\alpha \) is defined as a function of \(K\) and \(x\), while \(\beta \) and \(z\) are a function of \(K,x\), and \(\alpha \). The tuples \(p\) and \(p'\) queried by \(\mathsf {D}\) are easily derivable and not discussed.

Conclusion of the attack. Once \(x\) is arbitrarily chosen, \(z,\alpha ,\beta ,\gamma ,\delta \) are easily computable from \(K\) and \(x\). For GFN\(_{(\ell ,4\ell -1)}\), the resulting plaintexts and ciphertexts satisfy \(p_1\oplus c_2 = p_1'\oplus c_2'\) with probability \(1\). This equation is, however, satisfied by an ideal cipher \(\mathcal {R}\) with probability at most \(1/2^{n/\ell }\). This completes the attack.

4 Known-Key Indifferentiability for Block Ciphers

Consider a composed system \(\mathcal {C}:\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}\) based on an underlying idealized primitive \(\mathcal {P}:\{0,1\}^{\kappa }\times \{0,1\}^{x}\rightarrow \{0,1\}^{y}\). Here, \(\mathcal {C}\) is always a keyed primitive (i.e., a block cipher), but \(\mathcal {P}\) may or may not be keyed, and the key space may differ from that of \(\mathcal {C}\). Furthermore, depending on \(\mathcal {C}\), \(\mathcal {P}\) denotes either a single or a composition of multiple idealized primitives \(\mathcal {P}_i\).

Where the classical notion of indistinguishability is established to provide strong security guarantees in the secret key setting, this is not true in the open key model where chosen or known keys come into play. In the latter setting, one can benefit from the known indifferentiability definition introduced in the work of Maurer et al. [29] and adapted for the case of hash functions by Coron et al. [11]. Building upon these results, we propose a new definition of known-key security. Our definition differs from earlier weaker versions of indifferentiability [11, 16, 28, 53] by its generality and the fact that it explicitly provides the distinguishing adversary with a public key under which it queries both the block cipher and potentially the underlying primitives (if that is required by composition). It moreover, does not limit the adversary’s type of queries, as is the case for leaky, public, and sequential indifferentiability.

We thus propose the following formalization:

Definition 1

Let \(\mathcal {C}\) be a composed primitive with oracle access to an ideal primitive \(\mathcal {P}\). Let \(\mathcal {R}\) be an ideal primitive with the same domain and range as \(\mathcal {C}\). Let \(\mathcal {S}\) be a simulator with the same domain and range as \(\mathcal {P}\) with oracle access to \(\mathcal {R}\) and making at most \(q_\mathcal {S}\) queries, and let \(\mathsf {D}\) be a distinguisher making at most \(q_\mathsf {D}\) queries. The known-key indifferentiability advantage \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D})\) of \(\mathsf {D}\) is defined as

$$\begin{aligned} \left| \Pr \left( K\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}\{0,1\}^{k}; \mathsf {D}^{\mathcal {C}^{\mathcal {P}},\mathcal {P}}(K)=1\right) - \Pr \left( K\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}\{0,1\}^{k}; \mathsf {D}^{\mathcal {R},\mathcal {S}^{\mathcal {R}}}(K)=1\right) \right| \,. \end{aligned}$$

By \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(q_\mathsf {D})\) we denote the maximum advantage of any distinguisher making at most \(q_\mathsf {D}\) queries to its oracles. Primitive \(\mathcal {C}\) is said to be \((q_\mathsf {D}; q_\mathcal {S}; \varepsilon )\) indifferentiable from \(\mathcal {R}\) if \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(q_\mathsf {D})<\varepsilon \).

In this indifferentiability experiment, the distinguisher is provided with access to either of two worlds: left (real) and right (ideal). In the left world the distinguisher \(\mathsf {D}\) has a query access to the composed construction \(\mathcal {C}\) and the primitive \(\mathcal {P}\), while in the right world \(\mathsf {D}\) accesses the ideal primitive \(\mathcal {R}\) and the simulator \(\mathcal {S}\), respectively. In case the composed primitive \(\mathcal {C}\) is invertible, \(\mathsf {D}\) obtains access to it in both forward and backward (inverse) direction. We refer to \(\mathcal {C}\) and \(\mathcal {R}\) as the “composed” oracles \(\mathcal {O}_1\), and these oracles always respond under the known-key \(K\). Hence, \(\mathsf {D}\) can forward query a message input \(M\) to receive \(C=\mathcal {C}(K,M)\) in the left world and \(C = \mathcal {R}(M)\) in the right world (here the randomly chosen key \(K\) implicitly fixes an instance of \(\mathcal {R}\)), or \(\mathsf {D}\) can also backward query \(C\) to receive \(M=\mathcal {C}^{-1}(K,C)\) and \(M = \mathcal {R}^{-1}(M)\) in the left and right worlds, respectively. We refer to \(\mathcal {P}\) and \(\mathcal {S}\) as the “small” oracles \(\mathcal {O}_2\), to which \(\mathsf {D}\) has full access (i.e., even if \(\mathcal {C}\) is designed to query \(\mathcal {P}\) only on the key \(K\)), but we note that \(\mathcal {S}\) knows this public key \(K\). From a practical point of view, the full access to the small oracles makes perfect sense, as the original idea of indifferentiability is that the distinguisher may know the underlying structure, and thus, use the underlying primitive as it wishes.

The particular way of allowing the key input to the composed primitive to be always the known key \(K\) but the key input to the small primitive to be anything, sets this known-key indifferentiability definition apart from existing versions of indifferentiability like [11, 16, 28, 53]. In more detail, in Table 1, we compare the interfaces in Definition 1 with the ones used in the indifferentiability definition (see [10, 22] for its block cipher instantiation). As it turns out, this change makes our definition particularly suitable for analyzing known-key security. In Proposition 1, we prove that \(\mathrm {iff}\) implies \(\mathrm {iff}{\text {-}}\mathrm {KK}\). Moreover, in Sect. 6 we also show a counterexample that an implication in the opposite direction does not hold.

Table 1. Interface of \(\mathsf {D}\) with the composed oracle \(\mathcal {O}_1\) (\(\mathcal {C}\) in the left world, \(\mathcal {R}\) in the right world) in the standard indifferentiability setting and in Definition 1. For both security definitions, the interface with the right oracle \(\mathcal {O}_2\) is the same: \(\mathsf {D}\) has full access to \(\mathcal {O}_2\)
Full size table

Proposition 1

If \(\mathcal {C}\) is \((q_\mathsf {D}; q_\mathcal {S}; \varepsilon )\) \(\mathrm {iff}\)-secure block cipher, then it is \((q_\mathsf {D}; q_\mathcal {S}; \varepsilon )\) \(\mathrm {iff}{\text {-}}\mathrm {KK}\)-secure.

Proof

Let \(\mathcal {S}\) be a simulator such that for any distinguisher \(\mathsf {D}\) making at most \(q_\mathsf {D}\) queries, the \(\mathrm {iff}\) advantage is at most \(\varepsilon \). We define \(\mathcal {S}'=\mathcal {S}\) to be the simulator for the \(\mathrm {iff}{\text {-}}\mathrm {KK}\) security. We prove that for any \(\mathrm {iff}{\text {-}}\mathrm {KK}\) distinguisher \(\mathsf {D}'\) making at most \(q_\mathsf {D}\) queries, we have \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}'}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}')<\varepsilon \).

Let \(\mathsf {D}'\) be any such distinguisher. We build an \(\mathrm {iff}\) distinguisher \(\mathsf {D}\) using \(\mathsf {D}'\) that has the same advantage in breaking \(\mathcal {C}\). Distinguisher \(\mathsf {D}\) simulates the environment for \(\mathsf {D}'\) as follows: firstly, it selects uniformly at random a key \(K\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}\{0,1\}^{k}\) and runs \(\mathsf {D}'\) on input \(K\); then it forwards all queries by \(\mathsf {D}'\) to its own oracles. If \(\mathsf {D}'\) succeeds in distinguishing the left and right worlds, \(\mathsf {D}\) succeeds as well. In particular, we have \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}'}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}')=\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}}}(\mathsf {D})<\varepsilon \).

5 Known-Key Indifferentiability is Meaningful

Consider any known-key distinguishing attack on a block cipher \(\mathcal {C}\) with idealized primitive \(\mathcal {P}\). Let \(K\in \{0,1\}^{k}\) be a known key. A classical known-key distinguisher for a function \(\mathcal {C}(K,\cdot )\) based on ideal primitive \(\mathcal {P}\) operates as follows: it makes \(q\) queries to its primitives, and then it outputs 1 if the queries show some “unexpected” relation, which means that such relation should not hold for a random primitive \(\mathcal {R}\) with the same domain and range of \(\mathcal {C}\). We formalize and translate such known-key distinguisher \(\mathsf {D}\) to a distinguisher for the indifferentiability notion \(\mathrm {iff}{\text {-}}\mathrm {KK}\) as follows. Let \(\mathcal {S}\) be a simulator. In advance of making any queries, this distinguisher fixes a predicate \(\varphi (\mathcal {Q})\), where \(\mathcal {Q}\) is a list of query tuples. Then, the distinguisher makes \(q_\mathsf {D}\) queries to its left and right oracles, to obtain a query history \(\mathcal {Q}_{q_\mathsf {D}}\) of size \(q_\mathsf {D}\). If \(\varphi (\mathcal {Q}_{q_\mathsf {D}})\) holds, it outputs 1, and otherwise it outputs 0. Clearly, \(\mathsf {D}\) bases its decision solely on the predicate \(\varphi (\mathcal {Q}_{q_\mathsf {D}})\), and by Definition 1:

$$\begin{aligned} \mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(q_\mathsf {D})&\ge \mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}) \nonumber \\&= \left| \Pr \left( \varphi (\mathcal {Q}_{q_\mathsf {D}})~\text {for}~\mathcal {C}^\mathcal {P},\mathcal {P}\right) - \Pr \left( \varphi (\mathcal {Q}_{q_\mathsf {D}})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\right) \right| \,. \end{aligned}$$
(1)

Now, in classical known-key distinguishing attacks, the first probability is (close to) 1, while the second probability is significantly smaller. Note that for the second probability, the distinguisher may ask queries to the simulator \(\mathcal {S}\), but in order for \(\mathcal {S}\) to be successful, it will try to consult \(\mathcal {R}\) as often as possible and queries to \(\mathcal {S}\) can consequently be seen as indirect queries to \(\mathcal {R}\).

We demonstrate this approach using the attack of Sect. 3 on GFN\(_{(\ell ,4\ell -1)}\) and an attack on GFNR\(_{(2,5)}\) by Coron et al. and Mandal et al. [10, 28], therewith demonstrating that this approach applies to any known-key distinguishing attack known in literature.

Theorem 1

Let \(\mathcal {C}\) be GFN\(_{(\ell ,r)}:\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}\) for \(r=4\ell -1\) with oracle access to an ideal primitive \(\mathcal {P}=\pi :\{0,1\}^{n/\ell }\rightarrow \{0,1\}^{n/\ell }\) (cf. Sect. 3). Let \(\mathcal {R}\) denote an ideal cipher with the same domain and range as \(\mathcal {C}\). For any simulator \(\mathcal {S}\) that makes at most \(q_{\mathcal {S}}\le 2^{n-1}-1\) queries to \(\mathcal {R}\), there exists a distinguisher \(\mathsf {D}\) that makes at most \(2r+2\) queries to its oracles, such that

$$\begin{aligned} \mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}) \ge 1- \frac{q_{\mathcal {S}}^2+2}{2^{n/\ell }}\,. \end{aligned}$$

Proof

Let \(\mathcal {S}\) be any simulator making at most \(q_{\mathcal {S}}\) queries to \(\mathcal {R}\). Let \(K\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}\{0,1\}^{k}\) be the given key, and \(k_1,\ldots ,k_r\) be the round keys. We construct a distinguisher \(\mathsf {D}\) that differentiates \((\mathcal {C},\mathcal {P})\) from \((\mathcal {R},\mathcal {S})\) with high probability. Define predicate \(\varphi (\mathcal {Q})\) as follows:

$$\begin{aligned} \exists \; (p_1 \ldots p_\ell ;c_1 \ldots c_\ell ),(p_1' \ldots p_\ell ';c_1' \ldots c_\ell ')\in \mathcal {Q}~\text {such that}~p_1\oplus c_2 = p_1'\oplus c_2'\,. \end{aligned}$$
(2)

The distinguisher makes \(2r\) queries to \(\mathcal {P}\) as explained in Sect. 3. Then, it makes its two corresponding queries to the left oracle, which results in \(\mathcal {Q}_{2r+2}\) containing exactly two left oracle queries. By construction,

$$\begin{aligned} \Pr \left( \varphi (\mathcal {Q}_{2r+2})~\text {for}~\text {GFN}_{(\ell ,r)}^\mathcal {P},\mathcal {P}\right) = 1\,. \end{aligned}$$

Remains to consider the probability \(\varphi (\mathcal {Q}_{2r+2})\) holds in the other game. Suppose the simulator makes \(q_{\mathcal {S}}\) queries, denote by \(\mathcal {Q}^\mathcal {S}\) the query history of \(\mathcal {S}\) to \(\mathcal {R}\). By basic probability theory:

$$\begin{aligned} \Pr \left( \varphi (\mathcal {Q}_{2r+2})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\right) =&\, \Pr \left( \varphi (\mathcal {Q}_{2r+2})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\mid \varphi (\mathcal {Q}^\mathcal {S})\right) \Pr \left( \varphi (\mathcal {Q}^\mathcal {S})\right) \,+\\&\, \Pr \left( \varphi (\mathcal {Q}_{2r+2})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\mid \lnot \varphi (\mathcal {Q}^\mathcal {S})\right) \Pr \left( \lnot \varphi (\mathcal {Q}^\mathcal {S})\right) \\ \le&\, \Pr \left( \varphi (\mathcal {Q}^\mathcal {S})\right) + \Pr \left( \varphi (\mathcal {Q}_{2r+2})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\mid \lnot \varphi (\mathcal {Q}^\mathcal {S})\right) . \end{aligned}$$

We first consider \(\Pr \left( \varphi (\mathcal {Q}^\mathcal {S})\right) \). Any two queries the simulator makes to \(\mathcal {R}\) satisfy \(p_1\oplus c_2 = p_1'\oplus c_2'\) with probability at most \(\frac{2^{n-n/\ell }}{2^n-q_\mathcal {S}}\), as any query is randomly drawn from a set of size at least \(2^n-q_\mathcal {S}\). Consequently, as the simulator makes \(q_\mathcal {S}\) queries, and any couple may result in a collision,

$$\begin{aligned} \Pr \left( \varphi (\mathcal {Q}^\mathcal {S})\right) \le {q_\mathcal {S}\atopwithdelims ()2}\frac{2^{n-n/\ell }}{2^n-q_\mathcal {S}}\,. \end{aligned}$$

Regarding the second probability: conditioned on \(\lnot \varphi (\mathcal {Q}^\mathcal {S})\), (2) may still hold if the two queries the distinguisher makes to \(\mathcal {R}\) accidentally satisfy it. As the second oracle query is drawn from a set of size at least \(2^n-(q_\mathcal {S}+1)\), the queries satisfy \(p_1\oplus c_2 = p_1'\oplus c_2'\) with probability at most \(\frac{2^{n-n/\ell }}{2^n-(q_\mathcal {S}+1)}\). Concluding, we find

$$\begin{aligned} \Pr \left( \varphi (\mathcal {Q}_{2r+2})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\right) \le \left( {q_\mathcal {S}\atopwithdelims ()2} + 1\right) \frac{2^{n-n/\ell }}{2^n-(q_\mathcal {S}+1)} \le \frac{q_\mathcal {S}^2+2}{2^{n/\ell }}\,. \end{aligned}$$

where we use that \(2^n-(q_{\mathcal {S}}+1) \ge 2^{n-1}\) for \(q_{\mathcal {S}}+1\le 2^{n-1}\). Hence, we find \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(2r+2) \ge 1- \frac{q_\mathcal {S}^2+2}{2^{n/\ell }}\). \(\square \)

Next we consider a distinguishing attack described in [10] and [28, Appendix C].

Fig. 3.
figure 3

GFNR\(_{(2,5)}\) (see Theorem 2)

Full size image

Theorem 2

Let \(\mathcal {C}\) be GFNR\(_{(2,5)}:\{0,1\}^{n}\rightarrow \{0,1\}^{n}\) with oracle access to 5 ideal primitives \(\mathcal {P}=(f_1,\ldots ,f_5)\) with \(f_i:\{0,1\}^{n/2}\rightarrow \{0,1\}^{n/2}\) (see Fig. 3). Let \(\mathcal {R}\) denote an ideal permutation with the same domain and range as \(\mathcal {C}\). For any simulator \(\mathcal {S}\) that makes at most \(q_{\mathcal {S}}\le 2^{n-1}-1\) queries to \(\mathcal {R}\), there exists a distinguisher \(\mathsf {D}\) that makes at most 24 queries to its oracles, such that

$$\begin{aligned} \mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}) \ge 1- \frac{q_{\mathcal {S}}^4+2}{2^{n/2}}\,. \end{aligned}$$

Proof

Denote the inputs of a GFNR\(_{(2,5)}\) evaluation by \((p,r)\) and the outputs by \((c,d)\). The attack of [10] and [28, Appendix C] describes a way to find 4 plaintext-ciphertext pairs that satisfy \(p_1\oplus p_2\oplus p_3\oplus p_4 = d_1\oplus d_2\oplus d_3\oplus d_4 = 0\). As in Theorem 1, predicate \(\varphi (\mathcal {Q})\) is defined as follows:

$$\begin{aligned}&\exists \; (p_1,r_1;c_1,d_1),\ldots ,(p_4,r_4;c_4,d_4)\in \mathcal {Q}~\text {such that}\nonumber \\&\qquad \qquad \qquad \qquad ~~~p_1\oplus p_2\oplus p_3\oplus p_4 = d_1\oplus d_2\oplus d_3\oplus d_4 = 0\,. \end{aligned}$$
(3)

The distinguisher makes \(20\) queries to \(\mathcal {P}\) (as in the proof of Theorem 1), and the four corresponding queries to the left oracle, which results in \(\mathcal {Q}_{24}\). By construction, \(\varphi (\mathcal {Q}_{24})\) holds for \(\text {GFN}_{(2,5)}^\mathcal {P},\mathcal {P}\) with probability \(1\), and it remains to consider the probability \(\varphi (\mathcal {Q}_{24})\) holds in the other game. Similar to the proof of Theorem 1, we find

$$\begin{aligned} \Pr \left( \varphi (\mathcal {Q}_{24})~\text {for}~\mathcal {R},\mathcal {S}^\mathcal {R}\right) \le {q_\mathcal {S}\atopwithdelims ()4}\frac{2^{n/2}}{2^n-q_\mathcal {S}} + \frac{2^{n/2}}{2^n-(q_\mathcal {S}+1)}\,, \end{aligned}$$

and hence we obtain \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(24) \ge 1- \frac{q_{\mathcal {S}}^4+2}{2^{n/2}}\), for \(q_{\mathcal {S}}+1\le 2^{n-1}\). \(\square \)

6 Known-Key Indifferentiability is Constructive

The next obvious question then is, whether there exist block cipher constructions that are known-key indifferentiable from an ideal cipher. In this section, we prove that this is indeed the case.

First, we consider generalized Feistel networks. In [22], Holenstein et al. considered GFNR\(_{(2,14)}\), a variant of GFN\(_{(2,14)}\) where the keys are not XORed to get the input to the primitives, but are used to obtain \(14\) different random functions (see also Sect. 2), and proved that this construction has indifferentiable advantage from an ideal cipher of \(O(q^{16}/2^{n/2})\). Here, we refer to standard indifferentiability (see Table 1 for the interfaces in this notion). Using this result, we obtain the following theorem.

Theorem 3

Let \(\mathcal {C}\) be GFNR\(_{(2,14)}\) with oracle access to an ideal primitive \(\mathcal {P}\) consisting of 14 random functions (and where no round keys are XORed). Let \(\mathsf {D}\) be an arbitrary distinguisher making at most \(q\) queries. Then there exists a simulator \(\mathcal {S}\) such that

$$\begin{aligned} \mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}) = O(q^{16}/2^{n/2})\,, \end{aligned}$$

where \(\mathcal {S}\) makes at most \(1400q^8\) queries to \(\mathcal {R}\) and runs in time \(O(q^8)\).

Proof

Holenstein et al. [22] proved that for \(\mathcal {C}\) being GFN\(_{(2,14)}\) any distinguisher making at most \(q\) queries, has indifferentiability an advantage of \(\mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}}}(\mathsf {D}) = O(q^{16}/2^{n/2})\). Their simulator makes at most \(1400q^8\) queries to \(\mathcal {R}\) and runs in time \(O(q^8)\). From Proposition 1, we conclude that the same bound holds for the \(\mathrm {iff}{\text {-}}\mathrm {KK}\)-security of GFN\(_{(2,14)}\), which completes the proof. \(\square \)

Next, we consider multiple Even-Mansour, and show that already with one round, this construction turns out to be optimally known-key indifferentiable secure.

Theorem 4

Let for \(r\ge 1\), \(\mathcal {C}_r\) be EM\(_r\) with oracle access to an ideal primitive \(\mathcal {P}\) consisting of \(r\) random permutations. Let \(\mathsf {D}\) be an arbitrary distinguisher making at most \(q\) queries. Then there exists a simulator \(\mathcal {S}\) such that

$$\begin{aligned} \mathbf {Adv}_{\mathcal {C},\mathcal {S}}^{\mathrm {\mathrm {iff}{\text {-}}\mathrm {KK}}}(\mathsf {D}) = 0\,, \end{aligned}$$

where \(\mathcal {S}\) makes at most \(q\) queries to \(\mathcal {R}\) and runs in time \(O(q)\).

Proof

First, consider \(r=1\). Let \(k_0\Vert k_1\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}\{0,1\}^{2n}\) be the public key. Intuitively, as soon as \(k_0\Vert k_1\) is fixed, \(\mathcal {C}\) behaves perfectly as a random permutation as \(\mathcal {P}\) is. Formally, simulator \(\mathcal {S}\) uses oracle \(\mathcal {R}\) to respond with \(Y=\mathcal {R}(X\oplus k_0)\oplus k_1\) on a forward query \(X\); and uses its oracle \(\mathcal {R}\) to respond with \(X=\mathcal {R}^{-1}(Y\oplus k_1)\oplus k_0\) on an inverse query \(Y\). By construction, all queries made by the distinguisher to \(\mathcal {S}\) are exactly in correspondence with the random primitive \(\mathcal {R}\) and \(\mathsf {D}\) cannot distinguish.

Now, for \(r>1\), the proof is not much different, although the simulator needs to do some more bookkeeping. It responds randomly at every query, except when it completes a chain, an evaluation EM\(_r(K,p)\), in which case it adapts its response to fit the random oracle. Note that, as the key is fixed, it can be considered constant, and different EM\(_r\) evaluations never collide somewhere in the middle. In other words, for any \(i\in \{1,\ldots ,r\}\) the following holds: if \(\pi _i\) denotes the permutation in the \(i\)-th round, then one input-output-tuple of \(\pi _i\) corresponds to exactly one \(\mathcal {C}(K,\cdot )\) evaluation, and vice versa. \(\square \)

We note that EM\(_1\) is not \(\mathrm {iff}\)-secure. Briefly, let \(\mathcal {S}\) be any simulator making at most \(q_\mathcal {S}\) queries. We construct a distinguisher \(\mathsf {D}\) as follows. Here, \(\mathcal {O}_1\) denotes its composed oracle (\(\mathcal {C}\) or \(\mathcal {R}\)) and \(\mathcal {O}_2\) its primitive oracle (\(\mathcal {P}\) or \(\mathcal {S}\)). Firstly, \(\mathsf {D}\) chooses arbitrary key \(k_0\Vert k_1\) and message \(M\), and queries \(Y\leftarrow \mathcal {O}_2(M\oplus k_0)\) and \(C\leftarrow \mathcal {O}_1(k_0\Vert k_1,M)\). Then, if \(C=Y\oplus k_1\), then \(\mathsf {D}\) outputs \(1\), otherwise it outputs \(0\). Note that \(C=Y\oplus k_1\) holds with probability \(1\) in the real world, and with probability \(1/2^n\) in the ideal world (as in this setting the simulator does not know \(k_1\)). Using Theorem 4, this renders a separation between \(\mathrm {iff}{\text {-}}\mathrm {KK}\) and \(\mathrm {iff}\), as already mentioned in Sect. 4.