The Equivalence of The Random Oracle Model and The Ideal Cipher Model, Revisited

The Equivalence of the Random Oracle Model
and the Ideal Cipher Model, Revisited

Thomas Holenstein∗ Robin Künzler† Stefano Tessaro‡
October 22, 2018

arXiv:1011.1264v2 [cs.CR] 1 Jun 2011
Abstract
We consider the cryptographic problem of constructing an invertible random permutation
from a public random function (i.e., which can be accessed by the adversary). This goal is
formalized by the notion of indifferentiability of Maurer et al. (TCC 2004). This is the natural
extension to the public setting of the well-studied problem of building random permutations
from random functions, which was first solved by Luby and Rackoff (Siam J. Comput., ’88)
using the so-called Feistel construction.
The most important implication of such a construction is the equivalence of the random
oracle model (Bellare and Rogaway, CCS ’93) and the ideal cipher model, which is typically used
in the analysis of several constructions in symmetric cryptography.
Coron et al. (CRYPTO 2008) gave a rather involved proof that the six-round Feistel con-
struction with independent random round functions is indifferentiable from an invertible random
permutation. Also, it is known that fewer than six rounds do not suffice for indifferentiability.
The first contribution (and starting point) of our paper is a concrete distinguishing attack which
shows that the indifferentiability proof of Coron et al. is not correct. In addition, we provide
supporting evidence that an indifferentiability proof for the six-round Feistel construction may
be very hard to find.
To overcome this gap, our main contribution is a proof that the Feistel construction with
fourteen rounds is indifferentiable from an invertible random permutation. The approach of our
proof relies on assigning to each of the rounds in the construction a unique and specific role
needed in the proof. This avoids many of the problems that appear in the six-round case.
Keywords. Cryptography, random oracle model, ideal cipher model, Feistel construction,
indifferentiability.
∗
ETH Zurich, Department of Computer Science, 8092 Zurich, Switzerland. E-mail:
[email protected]
†
ETH Zurich, Department of Computer Science, 8092 Zurich, Switzerland. E-mail: [email protected]
‡
University of California, San Diego, Department of Computer Science & Engineering, La Jolla, CA 92093-0404.
E-mail: [email protected]
Contents
1 Introduction 1
1.1 Random Functions and Permutations: The Feistel Construction . . . . . . . . . . . . 1
1.2 The Random Oracle and Ideal Cipher Models: Indifferentiability . . . . . . . . . . . 1
1.3 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Sketch of the Previous Problems and the New Proof . . . . . . . . . . . . . . . . . . 3
1.5 Model and Notational Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 The Six-Round Feistel Construction: An Attack 7

2.1 The Simulator of Coron et al. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 A problem in the Proof of [CPS08c] . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 The Attack against the Simulator of [CPS08c] . . . . . . . . . . . . . . . . . . . . . . 9
3 Indifferentiability of the Feistel Construction from a Random Permutation 11

3.1 Simulator Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.1 Informal description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.2 The simulator in pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Proof of Indifferentiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Replacing the permutation with a random function . . . . . . . . . . . . . . . 15
3.2.2 Introducing a Feistel-construction . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.3 Removing the simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.4 Indifferentiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Equivalence of the First and the Second Experiment . . . . . . . . . . . . . . . . . . 19
3.4 Complexity of the Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.5 Equivalence of the Second and the Third Experiment . . . . . . . . . . . . . . . . . . 23
3.5.1 Partial chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.5.2 Bad events and good executions . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5.3 Bad events are unlikely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5.4 Properties of good executions . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5.5 Mapping randomness of S2 to randomness of S3 . . . . . . . . . . . . . . . . . 33
A Detailed Definition of the Simulator of Coron et al. 39
B Detailed Analysis of the Attack against the Simulator of Coron et al. 45
C A Stronger Attack 52
2
1 Introduction
1.1 Random Functions and Permutations: The Feistel Construction
Many cryptographic security proofs rely on the assumption that a concrete cryptographic function
(e.g. a block cipher or a hash function) behaves as a random primitive, i.e., an ideal object which
answers queries “randomly”. A typical example is a random function F : {0, 1}m → {0, 1}n ,
which associates with each m-bit input x a uniformly distributed n-bit value F(x). We speak of a
random oracle if the domain consists of all strings of finite length, rather than all m-bit ones. A
random permutation P : {0, 1}n → {0, 1}n is another example: It behaves as a uniformly-chosen
permutation from the set of all permutations on {0, 1}n , allowing both forward queries P(x) and
backward queries P−1 (y).
Many results in cryptography can be recast as finding an explicit construction of a random
primitive from another one in a purely information-theoretic setting. For instance, the core of Luby
and Rackoff’s seminal result [LR88] on building pseudorandom permutations from pseudorandom
functions (a computational statement) is a construction of a random permutation from random
functions via the r-round Feistel construction Ψr : It implements a permutation taking a 2n-bit
input (L0 , R0 ) (where L0 , R0 are n-bit values), and the output (Lr , Rr ) is computed via r rounds
mapping Li , Ri to Li+1 , Ri+1 as
Li+1 := Ri , Ri+1 := Li ⊕ Fi+1 (Ri ),
where F1 , . . . , Fr : {0, 1}n → {0, 1}n are so-called round functions. The main statement of [LR88] is
that if the round functions are independent random functions, then Ψ3 is information-theoretically
indistinguishable from a random permutation which does not allow backward queries, whereas Ψ4
is indistinguishable from a full-fledged random permutation.
1.2 The Random Oracle and Ideal Cipher Models: Indifferentiability

Random primitives are frequently employed to model an idealized cryptographic function accessible
by all parties in the scenario at hand, including the adversary. The most prominent example is the
Random Oracle Model [BR93], where a random oracle models an ideal hash function. Although it
is known that no concrete hash function can achieve the functionality of a random oracle [CGH04]
(see also [MRH04]), security proofs in the random oracle model provide a common heuristic as to
which schemes are expected to remain secure when the random oracle is instantiated with a concrete
hash function. In fact, to date, many widely employed practical schemes, such as OAEP [BR94]1
and FDH [BR96], only enjoy security proofs in the random oracle model.
The ideal cipher model is another widespread model in which all parties are granted access
to an ideal cipher E : {0, 1}κ × {0, 1}n → {0, 1}n , a random primitive such that the restrictions
E(k, ·) for k ∈ {0, 1}κ are 2κ independent random permutations. Application examples of the
ideal cipher model range from the analysis of block-cipher based hash function constructions (see,
for example [BRS02]) to disproving the existence of generic attacks against constructions such as
cascade encryption [BR06, GM09] and to studying generic related-key attacks [BK03].
Equivalence of models and indifferentiability. This paper addresses the fundamental ques-
tion of determining whether the random oracle model and the ideal cipher model are equivalent,
1
However, we note that standard model instantiations of OAEP for certain classes of trapdoor functions ex-
ist [KOS10], even though they only achieve a weaker security notion than what provable in the random oracle model.
1
where equivalence is to be understood within a simulation-based security framework such as [Can01]:
In other words, we aim at answering the following two questions:
(1) Can we find a construction C1 , which uses an ideal cipher E, such that CE
1 is “as good as” a
random oracle R, meaning that any secure cryptographic scheme using R remains secure when
using CE
1 instead?
(2) Conversely, is there C2 such that CR

2 is “as good as” an ideal cipher E?
Indistinguishability is not sufficient to satisfy the above requirement of being “as good as”, as the
adversary can exploit access to the underlying primitive. Instead, the stronger notion of indifferen-
tiability due to Maurer et al. [MRH04] is needed: the system CE 1 is indifferentiable from R if there
exists a simulator 2 S accessing R such that (CE 1 , E) and (R, SR ) are information-theoretically in-
distinguishable. This is equivalent to stating that the adversary is able to locally simulate the ideal
cipher consistently with R, given only access to the random oracle and without knowledge of the
queries to R of the honest users. Of course, indifferentiability generalizes to arbitrary primitives:
The definition of CR 2 being indifferentiable from E is analogous.
3
Prior work and applications. Question (1) above is, to date, well understood: Coron et
al. [CDMP05], and long series of subsequent work, have presented several constructions of ran-
dom oracles from ideal ciphers based on hash-function constructions such as the Merkle-Damgård
construction [Mer89, Dam89] with block-cipher based compression functions. In particular, indif-
ferentiability has become a de-facto standard security requirement for hash function constructions,
generally interpreted as the absence of generic attacks against the construction treating the block
cipher as a black box.
In a similar vein, answering question (2) could provide new approaches to designing block ciphers
from non-invertible primitives. But in contrast to question (1), the problem is far less understood.
Dodis and Puniya [DP06] considered constructions in the so-called honest-but-curious model, where
the adversary only gets to see queries made by the construction to the public random function,
but is not allowed to issue queries of her choice: They showed that ω(log n) rounds of the Feistel
construction are sufficient to build an ideal cipher.4 In the same work, it was first noted that four
rounds are insufficient to achieve indifferentiability of the Feistel construction.
Finally, at CRYPTO 2008, Coron et al. [CPS08a] presented a first proof that the six-round
Feistel construction Ψ6 with independent random round functions is indifferentiable from a random
permutation,5 hence seemingly settling the equivalence of the ideal cipher model and the random
oracle model. They also showed that five rounds are insufficient for this task. Also, a somewhat
simpler proof that the ten-round Feistel construction Ψ10 with independent round functions is
indifferentiable from a random permutation was later presented in [Seu09], the PhD thesis of the
last author of [CPS08a].
Following the publication of this result, the equivalence of the random oracle and ideal cipher
models has been used to infer security in the random oracle model using an ideal cipher (or random
2
Usually required to be efficient, i.e., with running time polynomial in the number of queries it processes
3
Interestingly, we cannot construct a non-invertible random permutation from a random oracle. This follows from
a well-known result by Rudich [Rud89] and Kahn et al. [KSS00].
4
The notion of honest-but-curious indifferentiability is very subtle, as in general it is not even implied by full
indifferentiability.
5
Note that this implies a construction of an ideal cipher from a random oracle, as we can construct the independent
round functions from a random oracle. Moreover, they can be keyed to obtain an independent cipher for each value
of the key.
2
permutation) as an intermediate step [DPW10] and to prove impossibility of black-box constructions
from block ciphers [LZ09].
1.3 Our Contributions

The surprising starting point of our work is a distinguishing attack, outlined and analyzed in
Section 2, which shows that the proof of [CPS08c] (the full version of [CPS08a]) is not correct: For
the simulator given in the proof, our attack distinguishes with overwhelming advantage. Despite
hopes, at first, that we could fix the proof of Coron et al. by minor modifications, we were unable
to do so. In fact, we provide a stronger attack which appears to succeed against a large class of
simulators following the natural approach of [CPS08c]. We also found similar problems in the proof
given in [Seu09], and so the question of settling the equivalence of the ideal cipher model and of
the random oracle model remains open.
In order to overcome this situation, the main contribution of this paper is a proof (given in
Section 3) that the fourteen-round Feistel construction Ψ14 is indifferentiable from a random per-
mutation. The round number is motivated by the goal of providing a simple to understand proof,
rather than by the goal of minimizing the number of rounds. Our proof relies on techniques which
are significantly different than the ones used in [CPS08c].
We discuss our results in more detail in the following section.
1.4 Sketch of the Previous Problems and the New Proof

First, we discuss the basic idea of building a random permutation from a random oracle via the
r-round Feistel construction Ψr . Then we discuss the problems in the previous proofs and finally
sketch our new proof. Some readers might find it helpful to consider the illustration of the Feistel
construction on page 12 in the following.
Simulation via chain-completion. Since we already fixed our construction to be Ψr , the core of
the proof is the construction of a simulator S that uses a given random permutation P : {0, 1}2n →
{0, 1}2n to consistently simulate r independent functions F1 , . . . , Fr from {0, 1}n → {0, 1}n . In
particular, suppose that a distinguisher queries the round functions to evaluate Ψr on input x ∈
{0, 1}2n . Then, it is required that the result matches the output of P on input x.6 To this end, the
simulator needs to somehow recognize queries belonging to such a sequence x1 , . . . , xr , and to set
the values Fi (xi ) to enforce consistency with P. In the following, such sequences x1 , . . . , xr will be
called chains.
The natural idea used by Coron et al. is to isolate so-called partial chains among queries made to
the round functions. An example of a partial chain is a triple (x1 , x2 , x3 ) such that x3 = x1 ⊕F2 (x2 ),
and each of x1 , x2 , and x3 has previously been queried to the corresponding round function Fi .
In particular, upon each query to Fi , the simulator checks whether one (or more) partial chains
are created. When such a partial chain is detected (and some additional conditions are met),
the simulator completes it to a (full) chain x1 , x2 , . . . , xr such that xi+1 = Fi (xi ) ⊕ xi−1 for all
i = 2, . . . , r − 1, and P(x0 , x1 ) = xr , xr+1 , where x0 := F1 (x1 ) ⊕ x2 and xr+1 = Fr (xr ) ⊕ xr−1 . In
particular, the simulator defines two consecutive values F` (x` ) and F`+1 (x`+1 ) adaptively to satisfy
all constraints. In our example, the simulator could complete the partial chain by first finding x0 ,
computing xr and xr+1 from P(x0 , x1 ), and finally evaluate the Feistel construction backwards, by
setting each undefined Fi (xi ) to a fresh uniform random string, until only F4 (x4 ) and F5 (x5 ) are
6
Of course, much more is needed, as the distribution of the output needs to be indistinguishable, but surely, the
above requirement is necessary.
3
undefined. These two values are then defined as F4 (x4 ) := x3 ⊕ x5 , and F5 (x5 ) := x4 ⊕ x6 . We
refer to this step as adapting the output values of x4 and x5 .
At this point, one faces (at least) two possible problems:
(i) The simulator defines new values at chain completion, and may keep producing new partial
chains while it completes chains, hence potentially running forever. Coron et al. solve this
problem very elegantly by a smart decision of which partial chains are completed. Then, they
are able to show that the recursion stops after at most poly(q) steps, where q is the number
of queries the distinguisher makes to the permutation. We use their strategy in our proof,
even though in the simplified version of [Seu09], as we detect fewer chains.
(ii) The simulator may try to adapt F` (x` ) to some value, even though F` (x` ) has been fixed to a
different value before. In this case, the simulator by Coron et al. aborts, and it hence becomes
necessary to show that no distinguisher can make the simulator abort except with negligible
probability.
Breaking previous simulators. Unfortunately, the proof given in [CPS08c] does not solve (ii)
above. In fact, it is possible to find a sequence of queries such that the simulator, with high
probability, attempts to change a value of a previously fixed Fi (x), and aborts. We provide an
intuition of the attack in Section 2.3. A full proof that that our attack breaks the simulator is
contained in Appendix B.
We formally prove that our attack distinguishes with overwhelming advantage. However, in
view of the complexity of the considered random experiments, we have also decided to gain extra
confidence in the correctness of our proof by simulating the setting of the attack. We therefore
implemented the simulator from [CPS08c] in Python, and then used our distinguisher on it. The
results confirm our theoretical analysis. The code is included as an ancillary file in the full version
of this paper [HKT10], and is available for download.
We also point out that the proceedings version of [CPS08c], as well as an earlier version available
on the eprint archive [CPS08b], presented a significantly simpler simulator. However, it suffered
from the same problem, and a simpler attack was possible. We assume that the authors were aware
of this problem when they modified the simulator, as some modifications appear to specifically rule
out some of the attacks we found against the simpler simulator. However, this is speculation: no
explanation is given in [CPS08c].
In the 10-round case, Seurin gives a much simpler simulator in his PhD thesis [Seu09]. At
present, we do not know whether this simulator can be attacked.
Problems with the previous proofs. Given our attack, it is natural to ask where the proof
given in [CPS08c] fails. We explore this question in Section 2.2, but we can give a short explanation
here. Consider the example above. When the simulator attempts to define the value of F5 (x5 ), the
proof assumes that it can do so, because earlier on, F6 (x6 ) was chosen uniformly at random, and x5
was set to be x5 := x7 ⊕ F6 (x6 ). The hope is that this implies that in the meanwhile F5 (x5 ) has not
been defined, except with very small probability. Unfortunately, between the moment where F6 (x6 )
was chosen uniformly, and the moment where F5 (x5 ) needs to be defined, the simulator may have
completed a large number of other partial chains. This can destroy our expectation completely,
and indeed, our attack does exploit this fact. We cannot hope to complete each detected chain
immediately when it is detected: For example, the definition of a single function value may cause
that we detect many new chains at the same time. These chains have to be completed in some
4
order, and thus there exist chains such that between their detection and their completion many
other function values are defined. This means that it is not obvious how to solve this problem.
Furthermore, while we do not know whether the simulator in [Seu09] can be attacked, the
problems with the proof we describe here are present in [Seu09] as well.
Further problems with previous proofs. There are, in fact, further problems with the pre-
vious proofs [CPS08c, Seu09]. All previous proofs reduced the task of proving indifferentiability to
the task of upper bounding the abort probability of the given simulator. Yet, it turns out that this
reduction is quite delicate as well. In fact, both proofs of [CPS08c] and [Seu09] have several gaps
in this part, which we were not able to fill directly.7 Thus, we give a completely new proof for this
part as well.
Ideas we use from the previous proofs. Since evidence points towards the fact that simulating
a 6-round Feistel construction is difficult, we consider the simulator for the 10-round construction
used in [Seu09], which is significantly simpler and much more elegant. Even though our simulator
is for 14 instead of 10 rounds, it is similar to the one in [Seu09]: the zones where we detect and
adapt chains are analogous. This allows us to reuse the elegant idea of [Seu09] for bounding the
simulator’s running time.
Intuition of our proof. In order to explain the main new ideas we use, we first give a more
complete sketch of our simulator and our proof. Of course, many details are omitted in this sketch.
As in previous ideas, our simulator detects chains, and completes them. In order to detect
chains, we follow [Seu09] and use special detect zones, where the simulator detects new chains.
Also, as in [Seu09], we have adapt zones, in which the simulator fixes the values of Fi (xi ) such that
the produced chain matches the given permutation P. Unlike before, we use buffer rounds (namely
rounds 3,6,9, and 12) between the zones where chains are detected, and the zones where values are
adapted. The function values in the buffer rounds are always defined by setting them to uniform
random values. The figure on page 12 has these zones marked.
We now discuss what happens when the simulator detects a new chain with values (x1 , x2 , x13 , x14 ),
and suppose that the simulator decides to adapt the resulting chain at positions 4 and 5. Because
of the way the simulator chooses the adapt zone to use, it is not extremely hard to show that at
the moment this chain is detected, the values F3 (x3 ) and F6 (x6 ) in the buffer rounds around this
adapt zone have not been defined yet, where x3 and x6 are the values corresponding to round 3
and 6 of the detected chain (and similar statements are proven in [Seu09]).
The hope at this point is that F3 (x3 ) (and also F6 (x6 ), but let us concentrate on F3 (x3 )) is
still unset when the simulator is ready to complete this chain. Intuitively, this should hold at least
in case the function values F2 and F4 are set at random, because then, the simulator should only
run into trouble if some kind of unlikely collision happens (it turns out later that actually it is not
necessary to always set F4 at random, but the intuition why this holds is somewhat advanced).
In order to prove that indeed this hope holds, we first use a queue to order the chains which the
simulator detects and completes. This ensures that when it detects the chain C = (x1 , x2 , x13 , x14 )
above, any chain during completion of which the simulator could possibly define F3 (x3 ) is defined
before the simulator detects C.
7
In very broad terms, both proofs present a step where an ideal permutation is replaced by the Feistel construction,
and values of the round functions are set by the evaluation of the construction: While each of the proofs presents a
different approach how this is done, neither of them presents a convincing argument of why this modification does
not affect the input-output behavior.
5
Next, we define a bad event BadlyCollide, which we show to occur if our hope fails. To understand
the main idea of event BadlyCollide, consider the chain C again. Even though F3 (x3 ) is not yet
defined when the chain is detected, the value x3 is already fixed at this point. The event BadlyCollide
occurs only if such a value appears in some other chain due to some unlikely collision (the “unlikely
collision” part is crucial: in general a distinguisher can set up new chains which contain such values,
in which case BadlyCollide should not occur).
In total, the above shows that our simulator never aborts (in contrast to the one given in
[CPS08c]). Of coures, it is still necessary to show that the result is indifferentiable from a Feistel
construction.
To see why this can be difficult, consider a distinguisher which first queries the given permuta-
tion P(x0 , x1 ), giving values (x14 , x15 ). The distinguisher then checks (say) the first bit of x14 , and
depending on it, starts evaluating the simulated Feistel construction from the top with the input
values (x0 , x1 ), or from the bottom with values (x14 , x15 ). Inspection of our simulator reveals that
the choice of the adapt zone of the simulator then depends on the first bit of x14 .
The problem which now comes in is that the randomness inherent in (x14 , x15 ) is needed in
order to show that the values of F in the adapt zones look random. However, conditioned on using
the upper adapt zone, one bit of x14 is already fixed.
In order to solve this problem, we take the following, very explicit approach: we consider the
two experiments which we want to show to behave almost the same, and define a map associat-
ing randomness in one experiment to randomness in the other experiment. We then study this
map. This leads to a more fine-grained understanding and a much more formal treatment of the
indistinguishability proof.8
1.5 Model and Notational Conventions

The results throughout this paper are information-theoretic, and consider random experiments
where a distinguisher D interacts with some given system S, outputing a value D(S). In the
context of this paper, such systems consist of the composition S = (S1 , S2 ) of two (generally
correlated) systems accessible in parallel, where Si is either a random primitive (such as a random
function F, a random permutation P defined above), or a construction CS accessing the random
primitive S. The advantage ∆D (S, S0 ) of a distinguisher D in distinguishing two systems S and S0
is defined as the absolute difference |Pr[D(S) = 1] − Pr[D(S0 ) = 1]|.
We dispense to the largest extent with a formal definition of such systems (cf. e.g. the framework
of Maurer [Mau02] for a formal treatmenet). Most systems we consider will be defined formally
using pseudocode in a RAM model of computation, following the approach of [BR06, Sho04]. The
time complexity of a system/distinguisher is also measured with respect to such a model.
Defining indifferentiability is somewhat subtle, as different definitions [MRH04, CDMP05] are
used in the literature. Furthermore, it turns out that our simulator runs in polynomial time only
with overwhelming probability (which is a bit weaker than giving a worst-case polynomial bound
on its running time). In particular, we meet the following definition, which implies the original
definition in [MRH04]:
Definition 1.1. For a construction C accessing independent random functions F = (F1 , . . . , Fr ),9
we say that CF is indifferentiable from a random permutation P if there exists a simulator S
such that for all polynomially bounded q, the advantage ∆D ((CF , F), (P, SP )) is negligible for all
8
For reference: this step can be found in Section 3.5.5.
9
Such a tuple can also be seen as a random primitive.
6
distinguishers D issuing a total of at most q queries to the two given systems, and furthermore there
exists a fixed polynomial p(q), such that S runs in time p(q) except with negligible probability. ♦
Finally, we warn the reader that the notation used in Section 2 differs strongly from the one
used in Section 3. The reason is that first in Section 2 we aim to stay close to the notation used
in [CPS08c] (with some minor modifications which we believe enhance readability). Unfortunately
this notation has some obvious problems when as many as 14 rounds are used, which is why we
cannot use it in Section 3.
2 The Six-Round Feistel Construction: An Attack

This section presents several problems in the existing proof of Coron et al. [CPS08c]. While we
cannot rule out the fact that the six-round Feistel construction is indeed indifferentiable from a
random permutation, the contents of this section show that any such proof would be significantly
more involved than the one given in [CPS08c].
2.1 The Simulator of Coron et al.

We first provide a high-level description of the simulator S used in the indifferentiability proof of
[CPS08c] for the six-round Feistel construction. This description is sufficient to convey the main
ideas underlying our attack and the problems with the existing proof, and a complete description
is given in Appendix A. For ease of reference, we use a similar notation to the one of [CPS08c]
throughout this section.
Recall that the simulator S queries P and P−1 to simulate the round functions F1 , . . . , F6
consistently, where the given P needs to have the same behaviour as the constructed six-round
Feistel construction. For each i ∈ {1, . . . , 6}, the simulator stores the values Fi (x) it has defined
up to the current point of the execution as a set H(Fi ) of pairs (x, Fi (x)), called the history of Fi .
We will write x ∈ Fi if Fi (x) is defined. At any point in time, the simulator considers so-called
3-chains, which are triples of values appearing in the histories of three consecutive round functions
and which are consistent with the evaluation of the Feistel construction. In the following, when we
refer to round i − 1 or i + 1, addition and subtraction are modulo 6, and the elements {1, . . . , 6}
represent the equivalence classes.
Definition 2.1 (3-chain). A 3-chain is a triple (x, y, z) (where the values are implicitly associated
with three consecutive rounds i − 1, i, and i + 1) which satisfies one of the following conditions with
respect to the given histories:
(i) If i ∈ {2, 3, 4, 5}, x ∈ Fi−1 , y ∈ Fi and z ∈ Fi+1 , and Fi (y) = x ⊕ z;
(ii) If i = 6, x ∈ F5 , y ∈ F6 , z ∈ F1 , and ∃x0 ∈ {0, 1}n : P−1 (ykF6 (y) ⊕ x) = x0 kz;
(iii) If i = 1, x ∈ F6 , y ∈ F1 , z ∈ F2 , and ∃x7 ∈ {0, 1}n : P(z ⊕ F1 (y)ky) = xkx7 .

♦
We next describe the main points how the simulator attempts to simulate the round functions.
On a query x ∈ Fi for the i-th round function Fi , the simulator S replies with Fi (x). If x ∈
/ Fi , the
simulator assigns to Fi (x) a uniform random value, and invokes a procedure called ChainQuery
with input (x, i).
The procedure ChainQuery operates as follows. Let C(+, x, i) and C(−, x, i) be the sets
of all 3-chains with x in round i as their first value (these are so-called positive chains) and as
7
their last value (so-called negative chains), respectively. The procedure iterates over all 3-chains
C(+, x, i) ∪ C(−, x, i), and for some subset of these chains it calls the procedure CompleteChain.
How the simulator chooses this subset is not important for this discussion.
The procedure CompleteChain ensures consistency of the defined values with respect to
the six-round Feistel construction, and operates as follows on input a positive 3-chain (x, y, z)
(a negative chain is processed analogously): It extends it to a 6-tuple (x1 , . . . , x6 ) with xi = x,
xi+1 = y and xi+2 = z and the additional property that Fi (xi ) = xi−1 ⊕ xi+1 for all i ∈ {2, 3, 4, 5}
and also that P(x2 ⊕ F1 (x1 )kx1 ) = x6 kF6 (x6 ) ⊕ x5 . This is achieved by first computing xj for
some j ∈ {i − 2, i + 2} and setting the value Fj (xj ) uniformly at random (if undefined), and then
computing the two remaining values x` and x`+1 , and adapting the respective output values F` (x` )
and F`+1 (x`+1 ) to satisfy the constraint imposed by the permutation P. Note that it may be that
setting these values is not possible (since some x0` ∈ F` or some x0`+1 ∈ F`+1 ), in which case we
say the simulator aborts. We point out that in this situation, the simulator is unable to define the
remaining chain values consistently with P. The precise choice of how j is chosen depends on the
index i, and we describe it in detail in Appendix A.
As the completion of these 3-chains defines new entries for the function tables, new 3-chains
may appear. In this case, ChainQuery is recursively called on input (x0 , i0 ) for each value Fi0 (x0 )
defined within one of the CompleteChain calls invoked by ChainQuery.
In the above description, we omitted one more complication: at the beginning of each invo-
cation of ChainQuery, some special special procedures (called XorQuery1 , XorQuery2 , and
XorQuery3 ) are invoked. Their purpose is to avoid some distinguishing attacks which are possible
against the simulator as detailed above, but in our distinguishing attack these procedures are not
helpful. We refer the reader to the Appendix for a complete treatment.
2.2 A problem in the Proof of [CPS08c]

The core of the proof of [CPS08c] considers a distinguisher which interacts with P and S. The goal
is to show that the probability that S aborts is negligible.
The natural approach taken in [CPS08c] is, for any execution of ChainQuery and under the
condition that no abort has occurred so far, to upper bound the probability that S aborts in one
of the recursive calls to ChainQuery. To achieve this, the following condition is introduced:
The distribution of Fi (x) when ChainQuery(x, i) is called is uniform in {0, 1}n given
the histories of all round functions, but where the value Fi (x) is removed from the
history, and in the case where the ChainQuery invocation results from the completion
of a chain, also all other values defined in that completion are removed from the history.
The proof idea is as follows: Suppose that the condition holds for a ChainQuery invocation,
and no abort has occurred so far. Then, except with negligible probability, no CompleteChain
execution within that ChainQuery leads to an abort, and the condition holds for every recursive
call to ChainQuery.10
The proof of this statement is very subtle: Between the point in time where the value Fi (x) is
set and the invocation of ChainQuery(x, i), potentially several other ChainQuery are executed
and extend the history. These additional values in the history could depend on Fi (x) and could
fully determine Fi (x).
10
We note that in some cases it turns out that the condition may not hold, but then a separate proof is given
that no abort occurs for such a ChainQuery execution, and that the condition holds for all subsequent calls to
ChainQuery, i.e., such bad invocations do not propagate.
8
In fact, for specific cases where [CPS08c] claims that the condition described above can be
established (such as Lemma 10), it is possible to show that the value Fi (x) is not distributed
uniformly, but is in fact fully determined by the given history values. Thus, the condition does
clearly not hold. For details, we refer to [Kün09]. We do not see how the proof can be extended
to fix this problem. These issues led to a concrete attack, which we describe below. Since this
is a much stronger statement, we dispense with a more detailed description of the problems in
[CPS08c].
A Problem in the Proof of [Seu09]. An alternative, and more elegant approach for the 10-
round Feistel construction is given by Seurin [Seu09] in his PhD thesis. The core of the proof also
consists in proving an upper bound on the abort probability of the simulator.
However, the proof suffers from similar problems as in [CPS08c]. As an example, the proof
of Lemma 2.11 in [Seu09] claims that the simulator aborts only with negligible probability in
CompleteChain2 (W, R, S, D) when adapting F3 (X), because X = R ⊕ F2 (W ), and F2 (W ) is
distributed uniformly in {0, 1}n . Yet, the statement about F2 (W ) being uniform is questionable,
since, similarly to the above case, there are function values defined after F2 (W ) ←R {0, 1}n oc-
curred, but before F3 (X) gets adapted. These values might well depend on F2 (W ), and therefore
it is not at all clear if F2 (W ) is still distributed uniformly given the values in the history, and how
one could prove such a statement.
Orthogonally, conditioning on something different than the complete history at the moment
where F2 (W ) is used does also not appear a viable option. This leads us to the conclusion that it
is still open if this simulator can be used to prove indifferentiability. However, in contrast to the
6-round case, we have been unable to find a concrete distinguishing attack when this simulator is
used.
2.3 The Attack against the Simulator of [CPS08c]

As formalized by the following theorem, we show that there exists a strategy for D such that S
aborts with overwhelming probability. This immediately implies that S cannot be used to prove
indifferentiability, since using the given strategy, one can distinguish the real setting from the ideal
setting (where S aborts).
Theorem 2.2. There is a distinguisher D such that S aborts with overwhelming probability when
D interacts with P and S.
The attack asks a very limited number of queries (i.e., 7 queries to the simulator, and three
permutations queries). When asking the last simulator query, the simulator is forced to complete
five different 3-chains. The queries are chosen in a way that after completing the first four chains,
four values of the completion of the remaining 3-chain are defined before the associated permutation
query is issued by the simulator. At this point, regardless of the strategy used, it is unlikely that
the simulator can set values so that this last chain is completed, and the simulator aborts. Figure 1
illustrates the structure of the (completed) 3-chains.
Outline of the attack and intuition. The distinguisher D chooses n-bit values X, R2 , R3 ,
and for i ∈ {2, 3}, lets Li := F1 (Ri ) ⊕ X, Si kTi := P(Li kRi ), and Ai := F6 (Si ) ⊕ Ti . Then, it
defines R1 := R2 ⊕ A2 ⊕ A3 , L1 := F2 (X) ⊕ R1 , S1 kT1 := P(L1 kR1 ), and A1 := F6 (S1 ) ⊕ T1 . It
is not hard to verify that (Si , Ri , X) are all 3-chains for i = 1, 2, 3. When completed to full chains
(Ri , X, Yi , Zi , Ai , Si ), the values (Y1 , Z2 , A3 ) also constitute a 3-chain, since
F4 (Z2 ) = A2 ⊕ Y2 = R1 ⊕ R2 ⊕ A3 ⊕ Y2 = R1 ⊕ F2 (X) ⊕ A3 = Y1 ⊕ A3
9
Figure 1: Illustration of the attack provoking the simulator S to abort.
under the assumption that the first three chains have been completed correctly. Finally, the dis-
tinguisher queries Ā := A1 ⊕ R1 ⊕ R2 to F5 . Note that (Y2 , Z1 , Ā) also constitutes a 3-chain under
the assumptions that the first three chains are completed correctly, since
F4 (Z1 ) = Y1 ⊕ A1 = Y1 ⊕ Ā ⊕ R1 ⊕ R2 = F2 (X) ⊕ Ā ⊕ R2 = Ā ⊕ Y2 .
Finally, note that

Z1 ⊕ F3 (Y2 ) = Z1 ⊕ Z2 ⊕ X = Z2 ⊕ F3 (Y1 ).
This means in particular that when completed, the 3-chains (Y1 , Z2 , A3 ) and (Y2 , Z1 , Ā) have a
common second value, which we denote as X 0 .
The core idea of the attack is the following: The simulator S first completes the 3-chains
(Si , Ri , X) for i = 1, 2, 3, and only subsequently turns to completing the two remaining 3-chains.
Say it completes the 3-chain (Y2 , Z1 , Ā) first: Then, as this chain has a common value with the
completion of the 3-chain (Y1 , Z2 , A3 ), in the end the simulator has only two possible values (namely,
those at both ends of the completed chain) which are still free to be set to complete the 3-chain
(Y1 , Z2 , A3 ), and this leads to an abort. (In fact, we prove the slightly stronger statement that the
simulator fails even if it adopts any other strategy to complete this last chain, once the second-last
chain is completed.)
The main difficulty of the full analysis, given in Appendix B, is that the actual simulator makes
calls to procedures (called XorQuery1 , XorQuery2 , and XorQuery3 ) which are intended to
prevent (other) attacks. To show that no such call affects the intuition behind our attack is a rather
cumbersome task.
Note that our implementation of the simulator and our attack in Python indeed shows that the
simulator aborts (the code can be found as ancilliary file in [HKT10]).
A stronger attack. It is actually possible to come up with a simulator that defines all function
values consistently with P under the attack present in the previous section, and thus the attack falls
short of proving that the six-round Feistel construction cannot be indifferentiable from a random
permutation. Appendix C presents a stronger distinguishing attack, for which, in fact, we were not
able to come up with a simulator which withstands it. We conjecture that no simulator within a
10
very large class of simulators is able to withstand this distinguishing attack, but giving such a proof
seems to be quite difficult and to require a deeper and more general understanding of the possible
dependencies between chains. Nonetheless, we consider this distinguisher to be a useful testbed for
any attempt to fix the indifferentiability proof for six rounds.11
3 Indifferentiability of the Feistel Construction from a Random

Permutation
We prove that the 14-round Feistel construction is indifferentiable from a random permutation.
Theorem 3.1. The 14-round Feistel construction using 14 independent random functions is indif-
ferentiable from a random permutation.
The remainder of this section is devoted to the proof of Theorem 3.1. Our task is to provide
a simulator S with access to a random permutation P such that (SP , P) is indistinguishable from
(F, ΨF ), where F denotes the random functions used in the Feistel construction.
We first define the simulator S in Section 3.1. Then we transform (SP , P) stepwise to (F, ΨF ).
The random functions we consider in this section are always from n bits to n bits, and the random
permutation P is over 2n bits.
3.1 Simulator Definition

We first give a somewhat informal, but detailed description of the simulator. We then use pseu-
docode to specify the simulator in a more formal manner.
3.1.1 Informal description

The simulator provides an interface S.F(k, x) to query the simulated random function Fk on input x.
For each k, the simulator internally maintains a table that has entries which are pairs (x, y). They
denote pairs of inputs and outputs of S.F(k, x). We denote these tables by S.Gk or just Gk when
the context is clear. We write x ∈ Gk to denote that x is a preimage in this table, often identifying
Gk with the set of preimages stored. When x ∈ Gk , Gk (x) denotes the corresponding image.
On a query S.F(k, x), the simulator first checks whether x ∈ Gk . If so, it answers with Gk (x).
Otherwise the simulator picks a random value y and inserts (x, y) into Gk (x). After this, the simu-
lator takes steps to ensure that in the future it answers consistently with the random permutation
P.
There are two cases in which the simulator performs a specific action for this. First, if k ∈
{2, 13}, the simulator considers all newly generated tuples (x1 , x2 , x13 , x14 ) ∈ G1 × G2 × G13 × G14 ,
and computes x0 := x2 ⊕ G1 (x1 ) and x15 := x13 ⊕ G14 (x14 ). It then checks whether P(x0 , x1 ) =
(x14 , x15 ). Whenever the answer to such a check is positive, the simulator enqueues the detected
values in a queue. More precisely, it enqueues a four-tuple (x1 , x2 , 1, `). The value 1 ensures that
later the simulator knows that the first value x1 corresponds to G1 . The value ` describes where
to adapt values of G` to ensure consistency with the given permutation. If k = 2, then ` = 4 and
if k = 13 then ` = 10.
The second case is when k ∈ {7, 8}. Then, the simulator enqueues all newly generated pairs
(x7 , x8 ) ∈ G7 × G8 . It enqueues all these pairs into the queue as (x7 , x8 , 7, `), where ` = 4 if k = 7
and ` = 10 if k = 8 (this is illustrated in Figure 2).
11
We have also implemented this more general attack in Python, and, not surprisingly, its execution also leads to
an abort of the simulator S.
11
x0
G1 x1
G2 x2
set uniform G3 x3
x2 detect
G4 x4
adapt
G5 x5
x7 detect
set uniform G6 x6
G7 x7
G8 x8
set uniform G9 x9
x8 detect
G10 x10
adapt
G11 x11
x13 detect
set uniform G12 x12
G13 x13
G14 x14
x15
Figure 2: The 14-round Feistel with the zones where our simulator detects chains and adapts them.
Whenever a function value G2 (x2 ), G7 (x7 ), G8 (x8 ), or G13 (x13 ) is defined, the simulator checks
whether the values in the blue dashed zones x7 , x8 and x1 , x2 , x13 , x14 form a partial chain. In case
a chain is detected, it is completed; the function values in the red dashed zones are adapted in
order to ensure consistency of the chain.
12
After enqueuing this information, the simulator immediately takes the partial chain out of the
queue again, and starts completing it. For this, it evaluates the Feistel chain forward and backward
(invoking P or P−1 at one point in order to wrap around), until x` and x`+1 are computed, and
only the two values G` (x` ) and G`+1 (x`+1 ) are possibly undefined. The simulator defines the
remaining two values in such a way that consistency with P is ensured, i.e., G` (x` ) := x`−1 ⊕ x`+1
and G`+1 (x`+1 ) := x` ⊕ x`+2 . If a value for either of these is defined from a previous action of the
simulator, the simulator overwrites the value (possibly making earlier chains inconsistent).
During the evaluation of the Feistel chain, the simulator usually defines new values for the
tables G. Whenever a value Gk (xk ) for k ∈ {2, 13} is defined, the exact same checks as above are
performed on the newly generated tuples (x1 , x2 , x13 , x14 ). Whenever a value Gk (xk ) for k ∈ {7, 8}
is defined, the simulator similarly enqueues all new pairs (x7 , x8 ).
When the simulator has finished completing a chain, it checks whether the queue is now empty.
While it is not empty, it keeps dequeuing entries and completing chains, otherwise, it returns the
answer to the initial query to the caller.
In order to make sure the simulator does not complete the same chains twice, the simulator
additionally keeps a set CompletedChains that contains all triples (xk , xk+1 , k) which have been
completed previously. Whenever the simulator dequeues a chain, it only completes the chain if it
is not in the set CompletedChains.
3.1.2 The simulator in pseudocode

We now provide pseudocode to describe the simulator as explained above in full detail. Later, during
the analysis, we will consider a slightly different simulator T. For this, we replace whole lines; the
replacements are put into boxes next to these lines. The reader can ignore these replacements at
the moment.
First, the simulator internally uses a queue and some hashtables to store the function values,
and a set CompletedChains to remember the chains that have been completed already.
1 System S: System T(f ):
2 Variables:
3 Queue Q
4 Hashtable G1 , . . . , G14
5 Set CompletedChains := ∅
The procedure F(i, x) provides the interface to a distinguisher. It first calls the corresponding
internal procedure Finner , which defines the value and fills the queue if necessary. Then, the
procedure F(i, x) completes the chains in the queue that were not completed previously, until the
queue is empty.
6 public procedure F(i, x)
7 Finner (i, x)
8 while ¬Q.Empty() do
9 (xk , xk+1 , k, `) := Q.Dequeue()
10 if (xk , xk+1 , k) ∈ / CompletedChains then // ignore previously completed chains
11 // complete the chain
12 (x`−2 , x`−1 ) := EvaluateForward(xk , xk+1 , k, ` − 2)
13 (x`+2 , x`+3 ) := EvaluateBackward(xk , xk+1 , k, ` + 2)
14 Adapt(x`−2 , x`−1 , x`+2 , x`+3 , `)
15 (x1 , x2 ) := EvaluateBackward(xk , xk+1 , k, 1)
16 (x7 , x8 ) := EvaluateForward(x1 , x2 , 1, 7)
13
17 CompletedChains := CompletedChains ∪ {(x1 , x2 , 1), (x7 , x8 , 7)}
18 return Gi (x)
The procedure Adapt adapts the values. It first sets the values marked green in Figure 2
uniformly at random, and also the next ones. It then adapts the values of G` (x` ) and G`+1 (x`+1 )
such that the chain matches the permutation.
It would be possible to simplify the code by removing lines 20 to 25 below, and changing the
parameters in lines 12 and 13 above. The current notation simplifies notation in the proof.
19 private procedure Adapt(x`−2 , x`−1 , x`+2 , x`+3 , `)
20 if x`−1 ∈
/ G`−1 then
21 G`−1 (x`−1 ) ←R {0, 1}n G`−1 (x`−1 ) := f (` − 1, x`−1 )
22 x` := x`−2 ⊕ G`−1 (x`−1 )
23 if x`+2 ∈
/ G`+2 then
24 G`+2 (x`+2 ) ←R {0, 1}n G`+2 (x`+2 ) := f (` + 2, x`+2 )
25 x`+1 := x`+3 ⊕ G`+2 (x`+2 )
26 ForceVal(x` , x`+1 ⊕ x`−1 , `)
27 ForceVal(x`+1 , x` ⊕ x`+2 , ` + 1)
28
29 private procedure ForceVal(x, y, `)

30 G` (x) := y
The procedure Finner provides the internal interface for evaluations of the simulated function.
It only fills the queue, but does not empty it.
31 private procedure Finner (i, x):
32 if x ∈
/ Gi then
33 Gi (x) ←R {0, 1}n Gi (x) := f (i, x)
34 if i ∈ {2, 7, 8, 13} then
35 enqueueNewChains(i, x)
36 return Gi (x)
The procedure enqueueNewChains detects newly created chains and enqueues them. Some-
times, chains may be detected which have been completed before, but they are ignored when they
are dequeued.
37 private procedure enqueueNewChains(i, x):
38 if i = 2 then
39 forall (x1 , x2 , x13 , x14 ) ∈ G1 × {x} × G13 × G14 do
40 if Check(x2 ⊕ G1 (x1 ), x1 , x14 , x13 ⊕ G14 (x14 )) then
41 Q.Enqueue(x1 , x2 , 1, 4)
42 else if i = 13 then
43 forall (x1 , x2 , x13 , x14 ) ∈ G1 × G2 × {x} × G14 do
44 if Check(x2 ⊕ G1 (x1 ), x1 , x14 , x13 ⊕ G14 (x14 )) then
45 Q.Enqueue(x1 , x2 , 1, 10)
47 forall (x7 , x8 ) ∈ {x} × G8 do
48 Q.Enqueue(x7 , x8 , 7, 4)
50 forall (x7 , x8 ) ∈ G7 × {x} do
14
51 Q.Enqueue(x7 , x8 , 7, 10)
52
53 private procedure Check(x0 , x1 , x14 , x15 )

54 return P(x0 , x1 ) = (x14 , x15 ) return R.Check(x0 , x1 , x14 , x15 )
The helper procedures EvaluateForward and EvaluateBackward take indices k and `
and a pair (xk , xk+1 ) of input values for Gk and Gk+1 , and either evaluate forward or backward in
the Feistel to obtain the pair (x` , x`+1 ) of input values for G` and G`+1 .
55 private procedure EvaluateForward(xk , xk+1 , k, `):
56 while k 6= ` do
57 if k = 14 then
58 (x0 , x1 ) := P−1 (x14 , x15 ) (x0 , x1 ) := R.P−1 (x14 , x15 )
59 k := 0
60 else
61 xk+2 := xk ⊕ Finner (k + 1, xk+1 )
62 k := k + 1
63 return (x` , x`+1 )
64
65 private procedure EvaluateBackward(xk , xk+1 , k, `):

66 while k 6= ` do
67 if k = 0 then
68 (x14 , x15 ) := P(x0 , x1 ) (x14 , x15 ) := R.P(x0 , x1 )
69 k := 14
70 else
71 xk−1 := xk+1 ⊕ Finner (k, xk )
72 k := k − 1
73 return (x` , x`+1 )
3.2 Proof of Indifferentiability

In this section, we provide the indifferentiability analysis. The overall plan is that we first fix a
deterministic distinguisher D, and suppose that it makes at most q queries.12 We then show that
the probability that D outputs 1 when interacting with (P, SP ) differs by at most poly(q)
2n from the
probability it outputs 1 when interacting with (ΨF , F), where Ψ is a 14-round Feistel construction,
and F is a collection of 14 uniform random functions.
We denote the scenario where D interacts with (P, SP ) by S1 , and the scenario where D interacts
with (ΨF , F) by S4 . The scenarios S2 and S3 will be intermediate scenarios.
3.2.1 Replacing the permutation with a random function

Scenario S2 (f, p) is similar to S1 . However, instead of the simulator S we use the simulator T(f ),
and instead of a random permutation P we use a two-sided random function R(p). The differences
between these systems are as follows:
12
We may assume that D is deterministic, since we are only interested in the advantage of the optimal distinguisher,
and for any probabilitstic distinguisher, the advantage can be at most the advantage of the optimal deterministic
distinguisher.
15
Explicit randomness: We make the randomness used by the the simulator explicit. Whenever
S sets Gi (xi ) to a random value, T(f ) takes it from f (i, xi ) instead, where f is a table which
contains an independent uniform random bitstring of length n for each i ∈ {1, 2, . . . , 14} and
xi ∈ {0, 1}n . This modification does not change the distribution of the simulation, because it
is clear that the simulator considers each entry of f at most once.
As depicted in the pseudocode below, the randomness of the two-sided random function R(p)
is also explicit: it is taken from p(↓, x0 , x1 ) or p(↑, x14 , x15 ), a table in which each entry is an
independent uniform random bitstring of length 2n.
Two-sided random function: We replace the random permutation P by a two-sided random

function R(p) (see below for pseudocode). This function keeps a hashtable P which contains
elements (↓, x0 , x1 ) and (↑, x14 , x15 ). Whenever the procedure R.P(x0 , x1 ) is queried, R checks
whether (↓, x0 , x1 ) ∈ P , and if so, answers accordingly. Otherwise, an independent uniform
random output (x14 , x15 ) is picked (by considering p), and (↓, x0 , x1 ) as well as (↑, x14 , x15 )
are added to P , mapping to each other.
Check procedure: The two-sided random function R has a procedure Check(x0 , x1 , x14 , x15 ).
It checks whether P maps (↓, x0 , x1 ) to (x14 , x15 ), and if so, returns true. If not, it checks
whether P maps (↑, x14 , x15 ) to (x0 , x1 ), and if so, returns true. Otherwise, it returns false.
The simulator T(f ) also differs from S in that T(f ).Check simply calls R.Check.
Pseudocode for T(f ) can be obtained by using the boxed contents on the right hand side in the
pseudocode of S instead of the corresponding line. For the two-sided random function R, the
pseudocode looks as follows:
1 System Two−sided random function R(p):
2 Variables:
3 Hashtable P
4
5 public procedure P(x0 , x1 )

6 if (↓, x0 , x1 ) ∈
/ P then
7 (x14 , x15 ) := p(↓, x0 , x1 )
8 P (↓, x0 , x1 ) := (x14 , x15 )
9 P (↑, x14 , x15 ) := (x0 , x1 ) // (May overwrite an entry)
10 return P (↓, x0 , x1 )
11
12 public procedure P−1 (x14 , x15 )

13 if (↑, x14 , x15 ) ∈
/ P then
14 (x0 , x1 ) := p(↑, x14 , x15 )
15 P (↓, x0 , x1 ) := (x14 , x15 ) // (May overwrite an entry)
16 P (↑, x14 , x15 ) := (x0 , x1 )
17 return P (↑, x14 , x15 )
18
19 public procedure Check(x0 , x1 , x14 , x15 )

20 if (↓, x0 , x1 ) ∈ P then return P (↓, x0 , x1 ) = (x14 , x15 )
21 if (↑, x14 , x15 ) ∈ P then return P (↑, x14 , x15 ) = (x0 , x1 )
22 return false
We claim that for uniformly chosen (f, p), the probability that D outputs 1 in scenario S2 (f, p)
differs only by poly(q)
2n from the probability it outputs 1 in S1 . For this, we first note that clearly the
16
simulator can take the randomness from f without any change. Secondly, instead of the procedure
Check in the simulator S, we can imagine that the random permutation P has a procedure
P.Check which is implemented exactly as in line 53 of S, and S.Check simply calls P.Check.
The following lemma states that such a system P is indistinguishable from R as above, which
then implies the claim. We prove the lemma in Section 3.3; the proof is neither surprising nor
particularly difficult.
Lemma 3.2. Consider a random permutation over 2n bits, to which we add the procedure Check
as in line 53 of the simulator S. Then, a distinguisher which issues at most q 0 queries to either
0 )2
the random permutation or to the two-sided random function R has advantage at most 6(q 22n
in
distinguishing the two systems.
Additionally, we will need that in S2 the number of queries made by the simulator is poly(q).
This is given in the following lemma, which we prove in Section 3.4.
Lemma 3.3. In S2 , at any point in the execution we have |Gi | ≤ 6q 2 for all i. Furthermore, there
are at most 6q 2 queries to both R.P, and R.P−1 , and at most 1296q 8 queries to R.Check.
In order to prove Lemma 3.3, we can follow the elegant idea from [CPS08c]. Thus, while we
give the proof for completeness, it should not be considered a contribution of this paper. It is in
fact very similar to the corresponding proof in [Seu09].
3.2.2 Introducing a Feistel-construction

In S3 (h), we replace the above two-sided random function R(p) by a Feistel construction Ψ(h). For
this, we use the following system:
1 System Ψ(h):
2
3 Variables:
4 Hashtable H1 , . . . , H14
5 Hashtable P
6
7 private procedure F(i, xi ):

8 if xi ∈
/ Hi then
9 Hi (xi ) := h(i, xi )
10 return Hi (xi )
11
12 public procedure P(x0 , x1 )

13 for i := 2 to 15 do
14 xi := xi−2 ⊕ F(i − 1, xi−1 )
15 P (↓, x0 , x1 ) := (x14 , x15 )
16 P (↑, x14 , x15 ) := (x0 , x1 )
17 return (x14 , x15 )
18
19 public procedure P−1 (x14 , x15 )

20 for i := 13 to 0 step −1 do
21 xi := xi+2 ⊕ F(i + 1, xi+1 )
22 P (↓, x0 , x1 ) := (x14 , x15 )
23 P (↑, x14 , x15 ) := (x0 , x1 )
17
24 return (x0 , x1 )
25
26 public procedure Check(x0 , x1 , x14 , x15 )

29 return false
We define S3 (h) to be the system where the distinguisher interacts with (Ψ(h), T(h)Ψ(h) ). Note
that the randomness used by Ψ and T is the same, and we call it h. We show the following lemma
in Section 3.5.
Lemma 3.4. The probability that a fixed distinguisher answers 1 in S2 (f, p) for uniform random
19 10
(f, p) differs at most by 8·102n·q from the probability that it answers 1 in S3 (h) for uniform ran-
dom h.
The proof of this lemma is the main contribution of this paper. A large part of the proof consists
in showing that the simulator does not overwrite a value in calls to ForceVal; this part is very
different than the corresponding step in [CPS08c]. An interesting feature of the proof is that in a
second part it directly maps pairs (f, p) to elements h = τ (f, p) such that S2 (f, p) and S3 (h) behave
the same for most pairs (f, p), and the distribution induced by τ is close to uniform. This part is
also very different than [CPS08c].
3.2.3 Removing the simulator

In S3 , the distinguisher accesses the random functions through the simulator. We want to show
that the distinguisher can instead access the random functions directly.
Lemma 3.5. Suppose that in S3 (h) the simulator T(h) eventually answers a query F(i, x). Then,
it is answered with h(i, x).
Proof. The simulator T(h) either sets Gi (x) := h(i, x) or Gi (xi ) := xi−1 ⊕ xi+1 in a call to Adapt.
For pairs (i, x) which are set by the first call the lemma is clear. Otherwise, consider the Adapt
call: just before the call, the Feistel construction was evaluated either forward or backward in a call
to Ψ.P(x0 , x1 ) or Ψ.P−1 (x14 , x15 ). Since Ψ evaluates P and P−1 with calls to h, the value Gi (xi )
must be h(i, x) as well.
3.2.4 Indifferentiability
We can now prove Theorem 3.1, which we restate here for convenience.
Theorem 3.1. The 14-round Feistel construction using 14 independent random functions is indif-
ferentiable from a random permutation.
Proof. Fix a distinguisher D which makes at most q queries. We want to show that D fails to
distinguish S1 = (P, SP ) from S4 = (ΨF , F), and furthermore, that the simulator runs in polynomial
time, except with negligible probability.
Consider the system S1 , where the distinguisher interacts with (P, SP ). If we replace P with
the two-sided random function R as described above and the simulator S by T(f ), then we obtain
S2 . According to Lemma 3.3 the number of queries the simulator makes in S2 to R is at most
6q 2 + 6q 2 + 1296q 8 ≤ 1400q 8 . Since Lemma 3.2 gives that the permutation is indistinguishable from
a two-sided random function, we get for q 0 = 1400q 8 that the probability that D outputs 1 differs
18
10q 0 2 7 16
by at most 22n
≤ 2·1022n·q in S1 and S2 . Furthermore, also by Lemma 3.2, with probability at
2·107 ·q 16
least 1 − 22n
, the first 1400q 8
queries and answers to P in S1 and R in S2 are equivalent, so
that the simulator is efficient (that is, it makes at most 1400q 8 queries) in S1 with probability at
7 16
least 1 − 2·1022n·q .
19 10
Now, the probability that D outputs 1 does not differ by more than 8·102n·q in S2 and S3 , by
19 10
Lemma 3.4. Finally, since this implies that with probability 1 − 8·102n·q the distinguisher must
give an answer in S3 , we can also use Lemma 3.5 and get that the probability that the distinguisher
19 10
answers 1 differs in S3 and S4 by at most 8·102n·q .
Finally, from the above results, the probability that D outputs 1 in S1 and S4 differs by at most
2 · 107 · q 16 8 · 1019 · q 10 1022 · q 16

+ 2 · < ,
22n 2n 2n
which implies the lemma.
3.3 Equivalence of the First and the Second Experiment

We now show that S1 and S2 behave the same way, more concretely, that our two-sided random
function R behaves as a uniform random permutation P.
Lemma 3.2. Consider a random permutation over 2n bits, to which we add the procedure Check
as in line 53 of the simulator S. Then, a distinguisher which issues at most q 0 queries to either
0 )2
the random permutation or to the two-sided random function R has advantage at most 6(q 22n
in
distinguishing the two systems.
To prove the lemma, fix any deterministic distinguisher D that issues at most q 0 queries. Con-
sider the following random experiment E0 :
Experiment E0 : D interacts with P0 (p), which is defined as follows: The procedures

P0 .P and P0 .P−1 are the same as R.P and R.P−1 . The Check procedure is defined as
1 public procedure P0 (p).Check(x0 , x1 , x14 , x15 )
4 return P(x0 , x1 ) = (x14 , x15 ) // Note that the procedure P0 .P is called!
Finally, p is the table of a uniform random permutation (i.e., p(↓, x0 , x1 ) = (x14 , x15 ) if
and only if p(↑, x14 , x15 ) = (x0 , x1 )).
If we let D interact with P (adding a Check-procedure to P in the most standard way, i.e., as in
the simulator S), then we get an experiment which behaves exactly as E0 .
We next replace the table p of the random permutation by a table that has uniform random
entries:
Experiment E2 : D interacts with P0 (p), where the entries of p are chosen uniformly
at random from {0, 1}2n .
We will show that

(q 0 )2
Lemma 3.6. The probability that D outputs 1 in E0 differs by at most 22n
from the probability
that D outputs 1 in E2 .
19
Finally we consider the experiment where D interacts with our two-sided random function.
Experiment E3 : D interacts with R(p), where the entries of p are chosen uniformly
at random from {0, 1}2n .
The only difference between E2 and E3 is the change in the last line in the procedure Check. We
show that E2 behaves almost as E3 :
5(q 0 )2
Lemma 3.7. The probability that D outputs 1 in E2 differs by at most 22n
from the probability
that D outputs 1 in E3 .
Lemma 3.2 then follows immediately, as

(q 0 )2 5(q 0 )2 6(q 0 )2
Pr[D outputs 1 in E0 ] − Pr[D outputs 1 in E3 ] ≤ 2n + 2n ≤ 2n .

2 2 2
We proceed to prove Lemmas 3.6 and 3.7.
Proof of Lemma 3.6. This proof is very similar to the proof that a (one-sided) random permutation
can be replaced by a (one-sided) random function.
We introduce the following intermediate experiment:
Experiment E1 : D interacts with P00 (p). In P00 , the procedure P00 .P is defined as
follows:
1 public procedure P00 .P(x0 , x1 )
2 if (↓, x0 , x1 ) ∈
/ P then
3 (x14 , x15 ) := p(↓, x0 , x1 )
4 if (↑, x14 , x15 ) ∈ P then
5 (x14 , x15 ) ←R {0, 1}2n \ {(x014 , x015 )|(↑, x014 , x015 ) ∈ P }
6 P (↓, x0 , x1 ) := (x14 , x15 )
7 P (↑, x14 , x15 ) := (x0 , x1 )
8 return P (↓, x0 , x1 )
The procedure P00 .P−1 is defined analogously, i.e., picks (x0 , x1 ) from p, and replaces it
in case (↓, x0 , x1 ) ∈ P . The procedure Check is defined as in P0 .Check above. Finally,
the entries of p are chosen uniformly at random from {0, 1}2n .
First consider the transition from E0 to E1 . The procedure Check is the same in both experi-
ments. Furthermore, a distinguisher can keep track of the table P and it is also the same in both
experiments, and so we only need to consider the procedures P and P−1 : the procedure Check
could be a part of the distinguisher.
Now, in both experiments, the values chosen in the procedures P and P−1 are chosen uniformly
at random from the set of values that do not correspond to an earlier query. Thus, E0 and E1
behave identically.
Now consider the transition from E1 to E2 . Consider E1 and let BadQuery be the event that in
P we have (↑, x14 , x15 ) ∈ P , or in P−1 we have (↓, x0 , x1 ) ∈ P . We show that this event is unlikely,
and that the two experiments behave identically if BadQuery does not occur in E1 .
There are at most q 0 queries to P or P−1 in an execution of E1 , since each Check query issues
at most one query to P. Observe that each table entry in p is accessed at most once and thus each
time p is accessed it returns a fresh uniform random value. Since for each query there are at most q 0
0 2
values in P , and p contains uniform random entries, we have Pr[BadQuery occurs in E1 ] ≤ (q22n) . The
20

systems E1 and E2 behave identically if BadQuery does not occur. Thus,Pr[D outputs 1 in E1 ] −

0 2
Pr[D outputs 1 in E2 ] ≤ Prp [BadQuery occurs in E1 ] ≤ (q22n) .

Proof of Lemma 3.7. The event BadCheck occurs for some p if P0 .Check returns true in the last
line in E2 in an execution using p. The event BadOverwrite occurs for some p if either in E2 or in
E3 , in any call to P or P−1 , an entry of P is overwritten.13 The event BadBackwardQuery occurs if
in E2 there exist (x0 , x1 ), (x∗14 , x∗15 ) such that all of the following hold:
(i) The query P(x0 , x1 ) is issued in the last line of a Check query, and P (↓, x0 , x1 ) is set to
(x∗14 , x∗15 ) = p(↓, x0 , x1 ).
(ii) After (i), the query P−1 (x∗14 , x∗15 ), or the query Check(x0 , x1 , x∗14 , x∗15 ) is issued.
(iii) The query P(x0 , x1 ) is not issued by the distinguisher between point (i) and point (ii).
We show that these events are unlikely, and that E2 and E3 behave identically if the events do not
occur for a given p.
For BadCheck to occur in a fixed call P0 .Check(x0 , x1 , x14 , x15 ), it must be that (↓, x0 , x1 ) ∈
/P
and (↑, x14 , x15 ) ∈
/ P . Thus, in the call P(x0 , x1 ) in the last line of Check, P (↓, x0 , x1 ) will be
set to a fresh uniform random value p(↓, x0 , x1 ), and this value is returned by P. Therefore, the
1
probability over the choice of p that P(x0 , x1 ) = (x14 , x15 ) is at most 22n . Since Check is called
q 0
0
at most q times, we see that Prp [BadCheck] ≤ 22n .
We now bound the probability that BadOverwrite occurs in E2 . This only happens if a fresh
uniform random entry read from p collides with an entry in P . Since there are at most q 0 queries
0 2
to P and P−1 and at most q 0 entries in P , we get Prp [BadOverwrite occurs in E2 ] ≤ (q22n) . The same
0 2
argument gives a bound on BadOverwrite in E3 , and so Prp [BadOverwrite] ≤ 2(q )
22n
.
We next estimate the probability of (BadBackwardQuery ∧ ¬BadCheck). Consider any pairs
(x0 , x1 ), (x∗14 , x∗15 ) such that (i) holds. Clearly, since BadCheck does not occur, the Check query
returns false. Now, as long as none of the queries P(x0 , x1 ), P−1 (x∗14 , x∗15 ) or Check(x0 , x1 , x∗14 , x∗15 )
is done by the distinguisher, the value of (x∗14 , x∗15 ) is independently chosen at random from all
the pairs (x014 , x015 ) for which Check(x0 , x1 , x014 , x015 ) was not queried. Thus, the probability that
in a single query, the distinguisher queries one of P−1 (x∗14 , x∗15 ) or Check(x0 , x1 , x∗14 , x∗15 ) is at
0 0 2n
most 22nq−q0 ≤ 22q2n (assuming q 0 < 22 ). Since there are at most q 0 Check queries, we find
0 2
Prp [(BadBackwardQuery ∧ ¬BadCheck)] ≤ 2(q )
22n
.
We proceed to argue that if the bad events do not occur, the two experiments behave identically.
Thus, let p be a table such that none of BadCheck, BadBackwardQuery, and BadOverwrite occurs.
We first observe that the following invariant holds in both E2 and E3 : after any call to P, P−1 or
Check, if P (↓, x0 , x1 ) = (x14 , x15 ) for some values (x0 , x1 , x14 , x15 ), then P (↑, x14 , x15 ) = (x0 , x1 ),
and vice versa. The reason is simply that no value is ever overwritten in the tables, and whenever
P (↑, ·, ·) is set, then P (↓, ·, ·) is also set.
Next, we argue inductively that for a p for which none of our bad events occur, all queries and
answers in E2 and E3 are the same.
For this, we start by showing that (under the induction hypothesis), if a triple (↓, x0 , x1 ) is
in P in the experiment E3 , then the triple is in P in E2 as well, and both have the same image
(x14 , x15 ). This holds because of two reasons: first, in E3 , each such entry corresponds to an answer
13
It would actually be sufficient to consider the system E2 here, but we can save a little bit of work by considering
both E2 and E3 .
21
to a previously issued query to P or P−1 . This query was also issued in E2 , and at that point the
answer was identical, so that the entry P (↓, x0 , x1 ) was identical (this also holds if the response in E2
is due to the entry P (↑, x14 , x15 ), because we saw above that this implies P (↓, x0 , x1 ) = (x14 , x15 )).
Since the event BadOverwrite does not occur, the property will still hold later. (We remark that
entries in the table P in E2 may exist which are not in E3 .)
We now establish our claim that all queries and answers of the distinguisher in E2 and E3 are
the same.
Consider first a P-query P(x0 , x1 ). If (↓, x0 , x1 ) ∈ P in E3 , the previous paragraph gives the
result for this query. If (↓, x0 , x1 ) ∈ / P in both E2 and E3 , the same code is executed. The only
remaining case is (↓, x0 , x1 ) ∈ P in E2 and (↓, x0 , x1 ) ∈
/ P in E3 . The only way this can happen is if
the query P(x0 , x1 ) was invoked previously from a query to Check in E2 , in which case the same
entry p(↓, x0 , x1 ) was used to set P , and we get the result.
Next, we consider a P−1 -query P−1 (x∗14 , x∗15 ). Again, the only non-trivial case is if (↑, x∗14 , x∗15 ) ∈
P in E2 and (↑, x∗14 , x∗15 ) ∈
/ P in E3 . This is only possible if during some query to Check(x0 , x1 , ·, ·)
in E2 , the last line invoked P(x0 , x1 ), and (x∗14 , x∗15 ) = p(↓, x0 , x1 ). Since it also must be that
until now the distinguisher never invoked P(x0 , x1 ) (otherwise, P (↑, x∗14 , x∗15 ) = (x0 , x1 ) in E3 ), this
implies that the event BadBackwardQuery must have happened.
Finally, consider a call Check(x0 , x1 , x14 , x15 ) to Check. In case (↓, x0 , x1 ) ∈ P in E3 and in
case (↓, x0 , x1 ) ∈
/ P in E2 , line 20 behaves the same in both E2 and E3 . If (↓, x0 , x1 ) ∈ P in E2 and
(↓, x0 , x1 ) ∈
/ P in E3 , then first in E3 , Check returns false. In E2 , Check can only return true if
the event BadBackwardQuery occurs.
The second if statement in Check (in E3 this is line 21 of R) can only return false in both E2
and E3 : otherwise, the first if statement in Check (in E3 this is line 20 of R) would already have
returned true. This is sufficient, because the event BadCheck does not occur, and so the last line of
Check in both systems also returns false.
Thus,

Pr[D outputs 1 in E2 ] − Pr[D outputs 1 in E3 ]

p p
≤ Pr[(BadCheck ∨ BadOverwrite ∨ BadBackwardQuery)]

p
q0 2(q 0 )2 2(q 0 )2 5(q 0 )2
≤ + + ≤ .
22n 22n 22n 22n
3.4 Complexity of the Simulator

In this section we show that the simulator is efficient in scenario S2 .
Lemma 3.8. Consider S2 , and suppose that the distinguisher makes at most q queries. Then, the
simulator dequeues at most q times a partial chain of the form (x1 , x2 , 1, `) for which (x1 , x2 , 1) ∈
/
CompletedChains.
Proof. Consider such a dequeue call and let (x1 , x2 , 1, `) be the partial chain dequeued for which
(x1 , x2 , 1) ∈
/ CompletedChains. A chain (x1 , x2 , 1, `) is only enqueued when (x1 , x2 , x13 , x14 ) is
detected, and since neither G1 (x1 ) nor G14 (x14 ) are ever overwritten, this means that we can
find a unique 4-tuple (x0 , x1 , x14 , x15 ) associated with (x1 , x2 , 1) for which Check(x0 , x1 , x14 , x15 )
was true at the moment (x1 , x2 , 1, `) was enqueued. We can now find a unique query to p which
corresponds to (x0 , x1 , x14 , x15 ): pick p(↑, x14 , x15 ) = (x0 , x1 ) if this was a query and its answer, or
otherwise p(↓, x0 , x1 ) = (x14 , x15 ). This table entry of p was accessed during a call to P or P−1 ,
and this call was made either by the distinguisher or the simulator. We argue that this call cannot
22
have been by the simulator. The simulator issues such calls only when it completes a chain, and
after this completion, it adds (x1 , x0 ⊕ G1 (x1 ), 1) to CompletedChains, and so it cannot have been
that (x1 , x2 , 1) ∈
/ CompletedChains when it was dequeued. Thus, we found a unique query of the
distinguisher associated with this dequeue call. Finally, note that after (x1 , x2 , 1) is completed by
the simulator, (x1 , x2 , 1) is added to CompletedChains. Thus, there are at most q such dequeue
calls.
Lemma 3.3. Consider S2 , and suppose that the distinguisher makes at most q queries. Then, at
any point in the execution we have |Gi | ≤ 6q 2 for all i. Furthermore, there are at most 6q 2 queries
to both R.P, and R.P−1 , and at most 1296q 8 queries to R.Check.
Proof. We first show that |G7 | ≤ 2q and |G8 | ≤ 2q. Assignments G7 (x7 ) := f (7, x7 ) and G8 (x8 ) :=
f (8, x8 ) only happen in two cases: either when the distinguisher directly queries the corresponding
value using F, or when the simulator completes a chain (x1 , x2 , 1, `) which it dequeued. There can
be at most q queries to F, and according to Lemma 3.8 there are at most q such chains which are
completed, which implies the bound.
The set Gi can only be enlarged by 1 in the following cases: if the distinguisher queries F(i, ·), if
a chain of the form (x1 , x2 , 1, `) is dequeued and not in CompletedChains, or if a chain (x7 , x8 , 7, `)
is dequeued and not in CompletedChains. There are at most q events of the first kind, at most q
events of the second kind (using Lemma 3.8), and at most |G7 | · |G8 | ≤ 4q 2 events of the last kind,
giving a total of 4q 2 + 2q ≤ 6q 2 .
A query to R.P or R.P−1 can be made either by the distinguisher, or by the simulator when
it completes a chain. At most q events of the first kind, and at most q + 4q 2 events of the second
kind are possible. Thus, at most 6q 2 of these queries occur. The number of Check queries by the
simulator is bounded by |G1 × G2 × G13 × G14 | ≤ (6q 2 )4 .
3.5 Equivalence of the Second and the Third Experiment

This section contains the core of our argument: We prove Lemma 3.4, which states that S2 (f, p)
and S3 (h) have the same behaviour for uniformly chosen (f, p) and h. For most part of the analysis,
we consider the scenario S2 (f, p). We let G = (G1 , . . . , G14 ) be the tuple of tables of the simulator
T(f ) in the execution.
3.5.1 Partial chains

Evaluating partial chains. A partial chain is a triple (xk , xk+1 , k) ∈ {0, 1}n ×{0, 1}n ×{0, . . . , 14}.
Given such a partial chain C, and a set of tables T.G and R.P , it can be that we can move “for-
ward” or “backward” one step in the Feistel construction. This is captured by the functions next
and prev. Additionally, the functions val+ and val− allow us to access additional values of the
chain indexed by C, val+ by invoking next, and val− by invoking prev. The function val finally
gives us the same information in case we do not want to bother about the direction.
Definition 3.9. Fix a set of tables G = T.G and P = R.P in an execution of S2 (f, p). Let
C = (xk , xk+1 , k) be a partial chain. We define the functions next, prev, val+ , val− , and val
with the following procedures (for a chain C = (xk , xk+1 , k), we let C[1] = xk , C[2] = xk+1 and
C[3] = k):
1 procedure next(xk , xk+1 , k):
2 if k < 14 then
3 if xk+1 ∈
/ Gk+1 then return ⊥
23
4 xk+2 := xk ⊕ Gk+1 (xk+1 )
5 return (xk+1 , xk+2 , k + 1)
6 else if k = 14 then
7 if (↑, x14 , x15 ) ∈
/ P then return ⊥
8 (x0 , x1 ) := P (↑, x14 , x15 )
9 return (x0 , x1 , 0)
10
11 procedure prev(xk , xk+1 , k):

12 if k > 0 then
13 if xk ∈ / Gk then return ⊥
14 xk−1 := xk+1 ⊕ Gk (xk )
15 return (xk−1 , xk , k − 1)
17 if (↓, x0 , x1 ) ∈
/ P then return ⊥
18 (x14 , x15 ) := P (↓, x0 , x1 )
19 return (x14 , x15 , 14)
20
21 procedure val+
i (C)
22 while (C 6= ⊥) ∧ (C[3] ∈
/ {i − 1, i}) do
23 C := next(C)
24 if C = ⊥ then return ⊥
25 if C[3] = i then return C[1] else return C[2]
26
27 procedure val−
i (C)
28 while (C 6= ⊥) ∧ (C[3] ∈
/ {i − 1, i}) do
29 C := prev(C)
30 if C = ⊥ then return ⊥
31 if C[3] = i then return C[1] else return C[2]
32
33 procedure vali (C)

−
34 if val+ +
i (C) 6= ⊥ return vali (C) else return vali (C)
We use the convention that ⊥ ∈/ Gi for any i ∈ {1, . . . , 14}. Thus, the expression vali (C) ∈
/ Gi
means that vali (C) = ⊥ or that vali (C) 6= ⊥ and vali (C) ∈ / Gi . Furthermore, even though next
and prev may return ⊥, according to our definition of partial chains, ⊥ is not a partial chain.
Equivalent partial chains We use the concept of equivalent partial chains:
Definition 3.10. For a given set of tables G and P , two partial chains C and D are equivalent
(denoted C ≡ D) if they are in the reflexive transitive closure of the relations given by next and
prev. ♦
In other words, two chains C and D are equivalent if C = D, or if D can be obtained by applying
next and prev finitely many times on C.
Note that this relation is not an equivalence relation, since it is not necessarily symmetric.14
However, we will prove that for most executions of S2 (f, p) it actually is symmetric and thus an
14
The symmetry can be violated if in the two-sided random function R an entry of the table P is overwritten.
24
equivalence relation. Furthermore, it is possible that two different chains (x0 , x1 , 0) and (y0 , y1 , 0)
are equivalent (e.g., by applying next 15 times). While we eventually show that for most executions
of S2 (f, p) this does not happen, this is not easy to show, and we cannot assume it for most of the
following proof.
3.5.2 Bad events and good executions

As usual in indistinguishability proofs, for some pairs (f, p) the system S2 (f, p) does not behave as
“it should”. In this section we collect events which we show later to occur with low probability.
We later study S2 (f, p) for pairs (f, p) for which these events do not occur.
All events occur if some unexpected collision happens to one of the partial chains which can be
defined with elements of G1 , . . . , G14 and P .
Definition 3.11. The set of table-defined partial chains contains all chains C for which next(C) 6=
⊥ and prev(C) 6= ⊥. ♦
If C = (xk , xk+1 , k) for k ∈ {1, . . . , 13}, then C is table-defined if and only if xk ∈ Gk and
xk+1 ∈ Gk+1 . For k ∈ {0, 14}, C is table-defined if the “inner” value is in G1 or G14 , respectively,
and a corresponding triple is in P .
Hitting permutations. Whenever we call the two-sided random function, a query to the table
p may occur. If such a query has unexpected effects, the event BadP occurs.
Definition 3.12. The event BadP occurs in an execution of S2 (f, p) if immediately after a call
(x14 , x15 ) := p(↓, x0 , x1 ) in line 7 of R we have one of
• (↑, x14 , x15 ) ∈ P ,
• x14 ∈ G14 .
Also, it occurs if immediately after a call (x0 , x1 ) := p(↑, x14 , x15 ) in line 14 of R we have one of
• (↓, x0 , x1 ) ∈ P ,
• x 1 ∈ G1 .
If BadP does not occur, then we will be able to show that evaluating P and P−1 is a bijection, since
no value is overwritten.
Chains hitting tables. Consider an assignment Gi (xi ) := f (i, xi ). Unless something unexpected
happens, such an assignment allows evaluating next(C) at most once more.
Definition 3.13. The event BadlyHit occurs if one of the following happens in an execution of
S2 (f, p):
• After an assignment Gk (xk ) := f (k, xk ) there is a table-defined chain (xk , xk+1 , k) such that
prev(prev(xk , xk+1 , k)) 6= ⊥.
• After an assignment Gk (xk ) := f (k, xk ) there is a table-defined chain (xk−1 , xk , k − 1) such

that next(next(xk−1 , xk , k − 1)) 6= ⊥.
25
♦
Furthermore, if the above happens for some chain C, and C 0 is a chain equivalent to C before the
assignment, we say that C 0 badly hits the tables.
We will later argue that the event BadlyHit is unlikely, because a chain only badly hits the tables
if f (k, xk ) takes a very particular value. For this (and similar statements), it is useful to note that
the set of table-defined chains after an assignment Gk (xk ) := f (k, xk ) does not depend on the value
of f (k, xk ), as the reader can verify.
Colliding chains. Two chains C and D collide if after an assignment suddenly vali (C) = vali (D),
even though this was not expected. More exactly:
Definition 3.14. Let G and P be a set of tables, let xk ∈

/ Gk , and consider two partial chains
C and D. An assignment Gk (xk ) := y badly collides C and D if for some ` ∈ {0, . . . , 15} and
σ, ρ ∈ {+, −} all of the following happen:
• Before the assignment, C and D are not equivalent.
• Before the assignment, valσ` (C) = ⊥ or valρ` (D) = ⊥.
• After the assignment, valσ` (C) = valρ` (D) 6= ⊥.
We say that the event BadlyCollide occurs in an execution S2 (f, p), if an assignment of the form
Gi (xi ) := f (i, xi ) makes two partial chains badly collide, and the two chains are table-defined after
the assignment. ♦
Finally, we say that a pair (f, p) is good if none of the above three events happen in an execution
of S2 (f, p).
3.5.3 Bad events are unlikely

In this subsection we show that all the bad events we have introduced are unlikely.
Hitting permutations
Lemma 3.15. Suppose that S2 (f, p) is such that for any (f, p) the tables satisfy |Gi | ≤ T for all
i and |P | ≤ T at any point in the execution. Then, the probability over the choice of (f, p) of the
2
event BadP is at most 2T
2n .
Proof. For any query to p, only 2 events are possible. In both cases, these events have probability
at most 2Tn . Since at most T positions of p can be accessed without violating |P | ≤ T we get the
claim.
Chains hitting tables. We now show that the event BadlyHit is unlikely.
i and |P | ≤ T at any point in the execution. Then, the probability over the choice of (f, p) of the
3
event BadlyHit is at most 30 T2n .
26
Proof. We first bound the probability of the first event, i.e., that after the assignment Gk (xk ) :=
f (k, xk ) there is a table-defined chain C = (xk , xk+1 , k) such that prev(prev(C)) 6= ⊥. This can
only happen if xk+1 ⊕ Gk (xk ) has one of at most T different values (namely, it has to be in Gk−1
in case 14 ≥ k ≥ 2 or in P together with x1 in case k = 1). Thus, for fixed xk+1 ∈ Gk+1 the
probability that prev(prev(C)) 6= ⊥ is at most T /2n . Since there are at most T possible choices
for xk+1 (this also holds if k = 14) the total probability is at most T 2 /2n .
The analogous probability for next is exactly the same and thus the probability of BadlyHit for
one assignment is at most 2 · T 2 /2n . In total, there are at most 14 · T assignments of the form
Gk (xk ) := f (k, xk ), and thus the probability of BadlyHit is at most 28T 3 /2n .
Colliding chains We next show that it is unlikely that chains badly collide. First, we give a
useful lemma which explains how the chains behave when they do not badly hit G: only one value
vali (C) can change from ⊥ to a different value.
Lemma 3.17. Consider a set of tables G and P , xk ∈ / Gk , fix a partial chain C, and suppose that
C does not badly hit the tables due to the assignment Gk (xk ) := f (k, xk ). Then, for each chain C
and each σ ∈ {+, −} there is at most one value i such that valσi (C) differs after the assignment from
before the assignment. Futhermore, if some value changes, then it changes from ⊥ to a different
value, and
k + 1 if σ = +
i=
k − 1 if σ = −,
and valσk (C) = xk before the assignment.
Proof. We give the proof for σ = +, the other case is symmetric. First, we see that if val+
i (C) 6= ⊥
before the assignment, then it does not change due to the assignment. This follows by induction
on the number of calls to next in the evaluation of val+ , and by noting that Gk (xk ) := f (k, xk ) is
not called if xk ∈ Gk in the simulator.
Thus, suppose that val+ +
i (C) = ⊥. This means that during the evaluation of vali (C) at some
point the evaluation stopped. This was either because a queried triple was not in P , or because
a value xj was not in Gj during the evaluation. In the first case, the evaluation of val+ i (C) will
not change due to an assignment to Gk (xk ). In the second case, the evaluation can only change
if it stopped because val+ +
k (C) = xk . Then after the assignment, valk+1 (C) will change from ⊥ to
a different value. Since C does not badly hit the tables under the assignment, val+ k+1 (C) ∈ / Gk+1
+ +
after this assignment (in case k + 1 < 15), and (↑, val14 (C), val15 (C)) ∈
/ P (in case k + 1 = 15).
Thus, there is only one change in the evaluation.
Instead of showing that BadlyCollide is unlikely, it is slightly simpler to consider the event
(BadlyCollide ∧ ¬BadlyHit ∧ ¬BadP).
i and |P | ≤ T at any point in the execution. Then, the probability of the event (BadlyCollide ∧
5
¬BadlyHit ∧ ¬BadP) is at most 15 000 T2n .
Proof. If the event (BadlyCollide ∧ ¬BadlyHit ∧ ¬BadP) happens for a pair (f, p), then there is some
point in the execution where some assignment Gk (xk ) := f (k, xk ) makes a pair (C, D) of partial
chains collide as in Definition 3.14. After this assignment, both (C, D) are table defined, and
valσ` (C) = valρ` (D).
We distinguish some cases: first suppose that val− −
` (C) = val` (D) = ⊥ before the assignment,
− −
and val` (C) = val` (D) 6= ⊥ after the assignment. Since BadlyHit does not happen, Lemma 3.17
27
implies that before the assignment, val− −
`+1 (C) = val`+1 (D), and furthermore ` + 1 ∈ {1, . . . , 14}.
Also, since C 6≡ D before the assignment, it must be that before the assignment val− `+2 (C) 6=
− − −
val`+2 (D). However, this implies that val` (C) 6= val` (D) after the assignment. Therefore, this
case is impossible and has probability 0.
Next, we consider the case val− −
` (C) = ⊥, val` (D) 6= ⊥ before the assignment, and val` (C) =
−
val−
` (D) after the assignment. Since D is table defined after the assignment, and we assume BadlyHit
does not occur, by Lemma 3.17 the value val− ` (D) does not change due to the assignment. Since
− −
val` (C) = val`+2 (C) ⊕ G`+1 (x`+1 ), and G`+1 (x`+1 ) is chosen uniformly at random, the probability
that it exactly matches val− ` (D) is 2
−n .
The next two cases are similar to the previous ones, we give them for completeness. The first of
− −
these two is that val+ +
` (C) = val` (D) = ⊥ before the assignment, and val` (C) = val` (D) 6= ⊥ after
the assignment. However, due to Lemma 3.17 this is impossible: we would need both k = ` + 1
and k = ` − 1 for both values to change as needed.
−
Then, we have the case that ⊥ = val+ +
` (C) 6= val` (D) before the assignment, and val` (C) =
− −
val` (D) after the assignment. Again, val` (D) does not change by the assignment due to Lemma 3.17,
−
and also similarly to before, the probability that val+ +
`−2 (C) ⊕ f (` − 1, val`−1 (C)) = val` (D) is 2
−n .
Bounds on the probability of the the 4 remaining cases follow by symmetry of the construction.
There are 4 possibilities for the values of σ and ρ. As previously, there can be at most 14 · T
assignments of the form Gk (xk ) := f (k, xk ). For each assignment, there are at most 15 · T 2
possibilities for a chain to be table-defined before the assignment. Since the chains that are table-
defined after the assignment, but not before must involve xk , there are at most 2 · T possibilities
for a fixed assignment. Thus the probability of the event (BadlyCollide ∧ ¬BadlyHit ∧ ¬BadP) is at
2 +2·T )2
most 4·14·T ·(15·T
2 ·T 5
2n ≤ 4·14·16
2n .
Most executions are good We collect our findings in the following lemma:
Lemma 3.19. Suppose that S2 (f, p) is such that for any (f, p) the tables satisfy |Gi | ≤ T for all i
and |P | ≤ T at any point in the execution. Then, the probability that a uniform randomly chosen
5
(f, p) is not good is at most 16 000 · T2n .
Proof. This follows immediately from Lemmata 3.15, 3.16, and 3.18.
3.5.4 Properties of good executions

We now study executions of S2 (f, p) with good pairs (f, p). One of the main goals of this section is
to prove Lemma 3.28, which states that no call to ForceVal overwrites a previous entry. However,
we later also use Lemma 3.29 (in good executions, evaluating the Feistel construction for a pair
(x0 , x1 ) leads to P (x0 , x1 ) — if not, it would be silly to hope that our simulator emulates a Feistel
construction), and Lemma 3.30 (the number of times Adapt is called in T(f ) is exactly the same
as the number of times the table p is queried in R(p)).
We first state two basic lemmas about good executions:
Lemma 3.20. Consider an execution of S2 (f, p) with a good pair (f, p). Then, we have
(a) For any partial chain C, if next(C) = ⊥ before an assignment Gi (xi ) := f (i, xi ) or a pair of
assignments to P in R, then if C is table-defined after the assignment(s), next(next(C)) = ⊥.
For any partial chain C, if prev(C) = ⊥ before an assignment Gi (xi ) := f (i, xi ) or a pair of
assignments to P in R, then if C is table-defined after the assignment(s), prev(prev(C)) = ⊥.
28
(b) For all partial chains C and D, we have next(C) = D ⇐⇒ prev(D) = C.
(c) The relation ≡ between partial chains is an equivalence relation.
Proof. For assignments of the form Gi (xi ) := f (i, xi ), (a) follows directly since BadlyHit does not
occur. For the assignments to P, it follows because BadP does not occur.
The statement (b) is trivial for chains C = (xk , xk+1 , k) with k ∈ {0, . . . , 13}, since evaluating
the Feistel construction one step forward or backward is bijective. For k = 14 we get (b) because
BadP does not occur: no value is ever overwritten in a call to P or P−1 , and thus evaluating P and
P−1 is always bijective.
To see (c), observe that the relation ≡ is symmetric because of (b), and it is reflexive and
transitive by definition.
Lemma 3.21. Consider an execution of S2 (f, p) with a good pair (f, p). Suppose that at any point
in the execution, two table-defined chains C and D are equivalent. Then, there exists a sequence of
partial chains C1 , . . . , Cr , r ≥ 1, such that
• C = C1 and D = Cr , or else D = C1 and C = Cr ,
• Ci = next(Ci−1 ) and Ci−1 = prev(Ci ),
• and each Ci is table-defined.
Proof. Since C ≡ D, D can be obtained from C by applying next and prev finitely many times. A
shortest such sequence can only apply either next or prev, due to Lemma 3.20 (b). The resulting
sequence of chains is the sequence we are looking for (possibly backwards) – note that the last
bullet point also follows by Lemma 3.20 (b).
We first show that assignments Gi (xi ) := f (i, xi ) and also assignments to P in R do not change
the equivalence relation for chains which were defined before.
Lemma 3.22. Consider an execution of S2 (f, p) with a good pair (f, p). Let C and D be two
table-defined partial chains at some point in the execution. Suppose that after this point, there is
an assignment Gi (xi ) := f (i, xi ) or a pair of assignments to P in R. Then C ≡ D before the
assignment(s) if and only if C ≡ D after the assignment(s).
Proof. Suppose that C ≡ D before the assignment. We apply Lemma 3.21 to get a sequence
C1 , . . . , Cr of table-defined chains. This sequence still implies equivalence after the assignment,
since no value in P or G can be overwritten by one of the assignments considered (recall that BadP
does not occur), i.e. the conditions of Definition 3.10 still hold if they held previously, thus C ≡ D
after the assignment(s).
Now suppose that C and D are equivalent after the assignment. Again consider the sequence
C1 , . . . , Cr as given by Lemma 3.21. Suppose first that the assignment was Gi (xi ) := f (i, xi ). If
xi was not part of any chain, then C1 , . . . , Cr are a sequence which show the equivalence of C and
D before the assignment. Otherwise, there is j such that the chains Cj−1 and Cj have the form
Cj−1 = (xi−1 , xi , i − 1) and Cj = (xi , xi+1 , i). It is not possible that Cj = Cr , as Cj is not table-
defined before the assignment. After the assignment next(next(Cj−1 )) 6= ⊥ which is impossible by
Lemma 3.20 (a). Suppose now we have a pair of assignments to P , mapping (x0 , x1 ) to (x14 , x15 ).
If (x14 , x15 , 14) is not part of the sequence connecting C and D after the assignment, the same
sequence shows equivalence before the assignment. Otherwise, next(next(x14 , x15 , 14)) = ⊥ by
Lemma 3.20 (a), as before.
29
Next, we show that calls to ForceVal also do not change the equivalence relation for previously
defined chains. Also, they never overwrite a previously defined value. However, we only show this
under the assumption x`−1 ∈ / G`−1 and x`+2 ∈/ G`+2 . Later, we will see that this assumption is
safe.
Lemma 3.23. Consider an execution of S2 (f, p) with a good pair (f, p). Let ` ∈ {4, 10} and suppose
that for a call Adapt(x`−2 , x`−1 , x`+2 , x`+3 , `) it holds that x`−1 ∈
/ G`−1 and x`+2 ∈
/ G`+2 before
the call.
Then, the following properties hold:
(a) For both calls ForceVal(x, ·, j) we have x ∈
/ Gj before the call.
(b) Let C be a table-defined chain before the call to Adapt, i ∈ {1, . . . , 14}. Then, vali (C) stays
constant during both calls to ForceVal.
(c) If the chains C and D are table-defined before the call to Adapt, then C ≡ D before the calls
to ForceVal if and only if C ≡ D after the calls to ForceVal.
Proof. Before Adapt is called, EvaluateForward and EvaluateBackward make sure that all
the values x`−1 , x`−2 , . . . , x0 , x15 , . . . , x`+3 , x`+2 corresponding to (x`−2 , x`−1 , ` − 2) are defined in
P and G. By Lemma 3.20 (b) and (d), all partial chains defined by these values are equivalent to
(x`−2 , x`−1 , ` − 2).
By our assumption, x`−1 ∈ / G`−1 and x`+2 ∈ / G`+2 , and thus the procedure Adapt defines
G`−1 (x`−1 ) := f (` − 1, x`−1 ) and G`+2 (x`+2 ) := f (` + 2, x`+2 ). These assignments lead to x` ∈ / G`
and x`+1 ∈ / G`+1 , as otherwise the event BadlyHit would occur. This shows (a).
We next show (b), i.e., for any C the values vali (C) stay constant. For this, note first that this
is true for table-defined chains C that are equivalent to (x`−2 , x`−1 , ` − 2) before the call to Adapt:
vali gives exactly xi both before and after the calls to ForceVal.
Now consider the table-defined chains that are not equivalent to (x`−2 , x`−1 , ` − 2) before the
−
call to Adapt. We show that for such a chain C, even val+ i (C) and vali (C) stay constant, as
σ
otherwise BadlyCollide would occur. A value vali (C) can only change during the execution of
ForceVal(x` , ·, `) if valσ` (C) = x` . But this implies that the assignment G(x`−1 ) := f (` − 1, x`−1 )
in Adapt made the two partial chains C and (x`−2 , x`−1 , ` − 2) badly collide. For this, note
that C is table-defined even before the assignment, since it was table-defined before the call to
Adapt. Moreover, (x`−2 , x`−1 , ` − 2) is table-defined after the assignment. The argument for
ForceVal(x`+1 , ·, ` + 1) is the same. Thus, this establishes (b).
We now show (c). First suppose that C ≡ D before the calls to ForceVal. The sequence of
chains given by Lemma 3.21 is not changed during the calls to ForceVal, since by (a), no value
is overwritten. Thus, the chains are still equivalent after the calls.
Now suppose that C ≡ D after the calls to ForceVal. Let C1 , . . . , Cr be the sequence given
by Lemma 3.21. If C and D were not equivalent before the calls to ForceVal, there is i such that
before the call, Ci was table defined, but Ci+1 was not. Then, val+ (Ci ) changes during a call to
ForceVal, contradicting the proof of (b). Thus, the chains must have been equivalent before the
calls.
Equivalent chains are put into CompletedChains simultaneously:

Lemma 3.24. Suppose that (f, p) is good. Fix a point in the execution of S2 (f, p), and suppose
that until this point, for no call to ForceVal of the form ForceVal(x, ·, `) we had x ∈ G` before
the call. Suppose that at this point C = (xk , xk+1 , k) with k ∈ {1, 7} and D = (ym , ym+1 , m) with
m ∈ {1, 7} are equivalent. Then, C ∈ CompletedChains if and only if D ∈ CompletedChains.
30
Proof. We may assume k = 1. We first show that the lemma holds right after C was added to
CompletedChains. Since the chain was just adapted, and using Lemma 3.20 (b) and (d), the only
chains which are equivalent to C are those of the form (vali (C), vali+1 (C), i). Thus both C and D
are added to CompletedChains, and D is the only chain with index m = 7 that is equivalent to C.
Now, the above property can only be lost if the event BadP occurs or else if a value is overwritten
by ForceVal. Thus, we get the lemma.
If the simulator detects a chain (x9 , x10 , 9) for which val+ is defined for sufficiently many values,
a chain equivalent to it was previously enqueued:
Lemma 3.25. Consider an execution of S2 (f, p) with a good pair (f, p). Suppose that at some
−
point, a chain C = (x7 , x8 , 7) is enqueued for which val+
2 (C) ∈ G2 or val13 (C) ∈ G13 (C). Then,
there is a chain equivalent to C which was previously enqueued.
Proof. We only consider the case val+ 2 (C) ∈ G2 , the other case is symmetric. Define (x0 , x1 , x2 , x13 ,
x14 , x15 ) := (val0 (C), val1 (C), val2 (C), val+
+ + + + +
13 (C), val14 (C), val15 (C)). All these must be different
from ⊥, since otherwise val+ 2 (C) = ⊥.
At some point in the execution, all the following entries are set in their respective hashtables:
G1 (x1 ), G2 (x2 ), G13 (x13 ), G14 (x14 ), and P (↑, x14 , x15 ). The last one of these must have been G2 (x2 )
or G13 (x13 ): if it was P (↑, x14 , x15 ), then the event BadP must have happened. If it was G1 (x1 ),
then the event BadlyHit must have happened (as (x0 , x1 , 0) is table-defined after the assignment).
Analogously, G14 (x14 ) cannot have been the last one. Thus, since G2 (x2 ) or G13 (x13 ) was defined
last among those, the simulator will detect the chain and enqueue it.
If a chain C is enqueued for which previously no equivalent chain has been enqueued, then the
assumptions of Lemma 3.23 actually do hold in good executions. We first show that they hold at
the moment when the chains are enqueued (Lemma 3.26), and then that they still hold when the
chains are dequeued (Lemma 3.27).
Lemma 3.26. Consider an execution of S2 (f, p) with a good pair (f, p). Let C be a partial chain
which is enqueued in the execution at some time and to be adapted at position `. Suppose that at
the moment the chain is enqueued, no equivalent chain has been previously enqueued.
Then, before the assignment Gk (xk ) := f (k, xk ) happens which just preceds C being enqueued,
val`−1 (C) = ⊥ and val`+2 (C) = ⊥.
Proof. We have ` ∈ {4, 10}. We will assume ` = 4, and due to symmetry of the construction, this
also implies the lemma in case ` = 10 for the corresponding rounds.
The assignment sets either the value of G7 (x7 ) or G2 (x2 ) uniformly at random (otherwise,
enqueueNewChains is not called in the simulator). Consider first the case that G2 (x2 ) was
just set. Then, before this happened, val+3 (C) = ⊥, since x2 ∈ / G2 . Furthermore, val−6 (C) = ⊥,
− − −
since otherwise, val7 (C) ∈ G7 , and then (val7 (C), val8 (C), 7) would be an equivalent, previously
enqueued chain. This implies the statement in case G2 (x2 ) is just set. The second case is if
G7 (x7 ) was just set. Then, before the assignment, val− 6 (C) = ⊥, as x7 ∈ / G7 , and val+
3 (C) = ⊥,
since otherwise val+2 (C) ∈ G 2 and so an equivalent chain would have been previously enqueued,
according to Lemma 3.25.
Lemma 3.27. Consider an execution of S2 (f, p) with a good pair (f, p). Let C be a partial chain
which is enqueued in the execution at some time and to be adapted at position `.
Then, at the moment C is dequeued, it holds that C ∈ CompletedChains, or that (val`−1 (C) ∈ /
G`−1 ) ∧ (val`+2 (C) ∈
/ G`+2 ).
31
Proof. Suppose that the lemma is wrong, and let C be the first chain for which it fails. Because this
is the first chain for which it fails, Lemma 3.23(a) implies that until the moment C is dequeued, no
call to ForceVal overwrote a value. Now, consider the set C of table-defined chains at some point
in the execution that is not in an Adapt call, and before C is dequeued. Because of Lemmas 3.22
and 3.23(c), the equivalence relation among chains in C stays constant from this point until the
moment C is dequeued.
We distinguish two cases to prove the lemma. Consider first the case that at the moment C
is enqueued, an equivalent chain D was previously enqueued. The point in the execution where
C is enqueued is clearly not in an Adapt call, and both C and D are table-defined. Then, at
the moment C is dequeued, clearly D ∈ CompletedChains. Thus, because of Lemma 3.24 and the
remark about equivalence classes of C above, this implies that C ∈ CompletedChains when it is
dequeued.
The second case is when C has no equivalent chain which was previously enqueued. To simplify
notation we assume ` = 4 and show val3 (C) ∈ / G3 , but the argument is completely generic. From
Lemma 3.26 we get that before the assignment which led to C being enqueued, val3 (C) = ⊥. If
val3 (C) ∈ G3 at the time C is dequeued, it must be that G3 (val3 (C)) was set during completion
of a chain D. This chain D was enqueued before C was enqueued, and dequeued after C was
enqueued. Also, at the moment C is dequeued, val3 (C) = val3 (D). From the point C is enqueued,
at any point until C is dequeued, it is not possible that C ≡ D: We assumed that there is no chain
in the queue that is equivalent to C when C is enqueued, and at the point C is enqueued both C
and D are table-defined. Furthermore, this point in the execution is not during an Adapt call.
Therefore, by our initial remark, the equivalence relation between C and D stays constant until
the moment C is dequeued.
Consider the last assignment to a table before val3 (C) = val3 (D) 6= ⊥ was true. We first
argue that this assignment cannot have been of the form Gi (xi ) := f (i, xi ), as otherwise the event
BadlyCollide would have happened. To see this, we check the conditions for BadlyCollide for C and
D. The chain D is table-defined even before the assignment, since it is in the queue. The assignment
happens earliest right before C is enqueued, in which case C is table-defined after the assignment.
If the assignment happens later, C is table-defined even before the assignment. Furthermore, we
have already seen that C ≡ D is not possible. Clearly, val3 (C) = ⊥ or val3 (D) = ⊥ before the
assignment, and val3 (C) = val3 (D) 6= ⊥ after the assignment.
The assignment cannot have been of the form P (↓, x0 , x1 ) = (x14 , x15 ) or P (↑, x14 , x15 ) =
(x0 , x1 ), since val can be evaluated at most one step further by Lemma 3.20 (a). Finally, the
assignment cannot have been in a call to ForceVal, because of Lemma 3.23(b).
Thus, val3 (C) ∈ / G3 when C is dequeued, and the same argument holds for the other cases as
well.
The following lemma is an important intermediate goal. It states that the simulator never
overwrites a value in G in case (f, p) is good.
Lemma 3.28. Consider an execution of S2 (f, p) with a good pair (f, p). Then, for any call to
ForceVal of the form ForceVal(x, ·, `) we have x ∈
/ G` before the call.
Proof. Assume otherwise, and let C be the first chain during completion of which the lemma fails.
Since the lemma fails for C, C ∈
/ CompletedChains when it is dequeued. Thus, Lemma 3.27 implies
that val`−1 (C) ∈
/ G`−1 and val`+2 (C) ∈
/ G`+2 when C is dequeued, and so by Lemma 3.23(a) we
get the result.
We say that a distinguisher completes all chains, if, at the end of the execution, it emulates a
32
call to EvaluateForward(x0 , x1 , 0, 14) for all queries to P(x0 , x1 ) or to (x0 , x1 ) = P−1 (x14 , x15 )
which it made during the execution.
Lemma 3.29. Consider an execution of S2 (f, p) with a good pair (f, p) in which the distinguisher
completes all chains. Suppose that during the execution P (↓, x0 , x1 ) is queried. Then, at the end
of the execution it holds that P (↓, x0 , x1 ) = val+ +

14 (x 0 , x1 , 0), val 15 (x 0 , x1 , 0) , and P (↑, x14 , x15 ) =
val−
0 (x , x
14 15 , 14), val −
1 (x , x
14 15 , 14) .
Proof. If the query P (↓, x0 , x1 ) was made by the simulator, then this was while it was completing
a chain. Then, right after it finished adapting we clearly have the result. By Lemma 3.28 no value
is ever overwritten. Since the event BadP does not occur, the conclusion of the lemma must also
be true at the end of the execution.
Consider the case that P (↓, x0 , x1 ) was a query by the distinguisher. Since it eventually issues
the corresponding Feistel queries, it must query the corresponding values x7 and x8 at some point.
Thus, x7 ∈ G7 and x8 ∈ G8 at the end of the execution. One of the two values was defined later,
and in that moment, (x7 , x8 , 7) was enqueued by the simulator. Thus, it is dequeued at some
point. If it was not in CompletedChains at this point, it is now completed and the conclusion of
the lemma holds right after this completion. Otherwise, it was completed before it was inserted
in CompletedChains, and the conclusion of the lemma holds after this completion. Again, by
Lemma 3.28 no value is ever overwritten, and again BadP never occurs, hence the conclusion also
holds at the end of the execution.
Lemma 3.30. Consider an execution of S2 (f, p) with a good pair (f, p) in which the distinguisher
completes all chains. Then, the number of calls to Adapt by the simulator equals the number of
queries to p(·, ·, ·) made by the two-sided random function.
Proof. Since the event BadP does not occur, the number of queries to p(·, ·, ·) equals half the number
of entries in P at the end of the execution.
For each call to Adapt, there is a corresponding pair of entries in P : just before Adapt was
called, such an entry was read either in EvaluateForward or EvaluateBackward. Further-
more, for no other call to Adapt the same entry was read, as otherwise a value would have to be
overwritten, contradicting Lemma 3.28.
For each query to p(·, ·, ·), there was a corresponding call to Adapt: if the query to p occurred
in a call to P by the simulator, then we consider the call to Adapt just following this call (as
the simulator only queries P right before it adapts). If the query to p occurred in a call by the
distinguisher, the distinguisher eventually queries the corresponding Feistel chain. At the moment
it queries G8 (x8 ), we find the first chain which is equivalent to (x7 , x8 , 7) at this point and was
enqueued. This chain must have been adapted accordingly.
3.5.5 Mapping randomness of S2 to randomness of S3

We next define a map τ which maps a pair of tables (f, p) to a partial table h, where a partial table
h : {1, . . . , 14} × {0, 1}n 7→ {0, 1}n ∪ {⊥} either has an actual entry for a pair (i, x), or a symbol
⊥ which signals that the entry is unused. This map will be such that S2 (f, p) and S3 (τ (f, p)) have
“exactly the same behaviour”.
Definition 3.31. The function h = τ (f, p) is defined as follows: Run a simulation of S2 (f, p) in
which the distinguisher completes all chains. If f (i, x) is read at some point, then h(i, x) := f (i, x).
If f (i, x) is never read, but for some y a call ForceVal(i, x, y) occurs, then h(i, x) := y for the
first such call. If f (i, x) is never read and no such call to ForceVal occurs, then h(i, x) := ⊥. ♦
33
Lemma 3.32. Suppose h has a good preimage. Consider any execution of S3 (h) and suppose
the distinguisher completes all chains. Then, S3 (h) never queries h on an index (i, x) for which
h(i, x) = ⊥. Furthermore, the following two conditions on (f, p) are equivalent:
(1) The pair (f, p) is good and τ (f, p) = h.
(2) The queries and answers to the two-sided random function in S2 (f, p) are exactly the same as
the queries and answers to the Feistel construction in S3 (h); and h(i, x) = f (i, x) for any query
(i, x) issued to f or h by the simulator.
Proof. We first show that (1) implies (2). Thus, because the distinguisher is deterministic, we need
to show the following:
• When the simulator sets Gi (xi ) := f (i, xi ) in S2 (f, p), respectively Gi (xi ) := h(i, xi ) in S3 (h),
the two values are the same.
• When the simulator queries P(x0 , x1 ) or P−1 (x14 , x15 ) it gets the same answer in S2 (f, p) and
S3 (h).
The first bullet is obvious, because if the simulator ever sets Gi (xi ) := f (i, xi ) in S2 (f, p), then h
will be set accordingly by definition of τ .
Thus, we consider a query to P(x0 , x1 ) (queries to P−1 are handled in the same way). Recall
that we assume that the distinguisher completes all chains. Because of Lemma 3.29, the answer
of the query to P is exactly what we obtain by evaluating the Feistel construction at the end
in experiment S2 . But each query in the evaluation of the Feistel construction was either set as
Gi (xi ) := f (i, xi ) or in a ForceVal call, and in both cases the values of h must agree, since in
good executions no value is ever overwritten (Lemma 3.28). Thus, the query to P is answered by
the Feistel in the same way.
We now show that (2) implies (1). Assume now that (2) holds. Let (fh , ph ) be a good preimage
of h, i.e., a pair satisfying (1). We know already that condition (2) holds for (fh , ph ), and because
we assume that it holds for (f, p), we see that in the two executions S2 (fh , ph ) and S2 (f, p) all
queries to the two-sided random function are the same, and also the entries f (i, x) and fh (i, x)
for values considered match. This implies that (f, p) must be good. Furthermore, this implies
τ (f, p) = τ (fh , ph ).
Finally, we argue that S3 (h) never queries h on an index (i, x) for which h(i, x) = ⊥. Let (fh , ph )
be a good preimage of h. Clearly (1) holds for h and (fh , ph ), which implies (2) as shown above.
Thus, it cannot be that a query to h in S3 (h) returns ⊥, as otherwise the answers in S2 (fh , ph ) and
S3 (h) would differ.
Lemma 3.33. Suppose h has a good preimage. Pick (f, p) uniformly at random. Then,
Pr[(f, p) is good ∧ τ (f, p) = h] = 2−n|h| , (1)
where |h| is the number of pairs (i, x) for which h(i, x) 6= ⊥.
Proof. Let (fh , ph ) be a good preimage of h. With probability 2−n|h| all queries in S2 (f, p) are
answered exactly as those in S2 (fh , ph ): every query to f is answered the same with probability
2−n , and every query to p with probability 2−2n . Because of Lemma 3.30 the number |h| of non-nil
entries in h is exactly the number of queries to f plus twice the number of queries to p.
Lemma 3.4. The probability that a fixed distinguisher answers 1 in S2 (f, p) for uniform random
19 10
(f, p) differs at most by 8·102n·q from the probability that it answers 1 in S3 (h) for uniform random
h.
34
Proof. First, modify the distinguisher such that for each query to P(x0 , x1 ) or to (x0 , x1 ) =
P−1 (x14 , x15 ) which it made during the execution (to either the two-sided random function in
S2 or the Feistel construction in S3 ), it issues the corresponding Feistel queries to F in the end (i.e.,
it emulates a call to EvaluateForward(x0 , x1 , 0, 14)). This increases the number of queries of the
distinguisher by at most a factor of 14. Furthermore, any unmodified distinguisher that achieves
some advantage will achieve the same advantage when it is modified.
Consider now the following distribution over values h∗ , which are either tables for S3 (h∗ ) which
contain no entry ⊥, or special symbols ⊥. To pick an element h∗ , we pick a pair (f, p) uniformly
at random. If (f, p) is good, we compute h := τ (f, p) and set each entry of h with h(i, x) = ⊥
uniformly at random. The result is h∗ . If (f, p) is not good, we set h∗ = ⊥. Let H be the random
variable that takes values according to this distribution.
∗
We now claim that the probability that any fixed table h∗ 6= ⊥ is output is at most 2−n|h | .
To prove this, we first show that it cannot be that two different values h which both have a
good preimage can yield the same h∗ . Towards a contradiction assume that h and h0 are different
and both have a good preimage, and they yield the same h∗ . Let (fh , ph ) and (fh0 , ph0 ) be good
preimages of h and h0 , respectively. Then, Lemma 3.32 item (2) implies that the queries and
answers in S2 (fh , ph ) and S3 (h) are the same. Furthermore, since S3 (h) never queries h on an index
(i, x) where h(i, x) = ⊥ (Lemma 3.32), we get that the queries and answers in S3 (h) and S3 (h∗ )
are the same. Arguing symmetrically for (fh0 , ph0 ), we see that the queries and answers in S3 (h0 )
and S3 (h∗ ) are the same, and so the queries and answers in S2 (fh , ph ) and S2 (fh0 , ph0 ) must be the
same. But by definition of τ , this implies that h = h0 , a contradiction.
We now calculate the probability of getting a fixed table h∗ 6= ⊥. In the first case, suppose
there exists h with a good preimage that can lead to h∗ . Let ρ be the randomness that is used to
replace the ⊥ entries in h by random entries. We have
Pr [H = h∗ ] = Pr [(f, p) is good ∧ h = τ (f, p) can lead to h∗ ∧ filling with ρ leads to h∗ ].

(f,p),ρ (f,p),ρ
Now, as we have seen, no two different values for h can yield the same h∗ . Thus, we can assume
that h∗ = (h, ρ∗ ), where h is the unique table that leads to h∗ , and ρ∗ stands for the entries that
occur in h∗ , but are ⊥ in h. Then, the above probability equals
Pr [(f, p) is good ∧ τ (f, p) = h ∧ ρ = ρ∗ ]

(f,p),ρ
= Pr [(f, p) is good ∧ τ (f, p) = h] · Pr [ρ = ρ∗ ]

(f,p),ρ (f,p),ρ
−n|h| −n(|h∗ |−|h|) −n|h∗ |
=2 ·2 =2 ,
where for the second equality we apply Lemma 3.33 and note that ρ is chosen uniformly.
In the second case, there exists no h with a good preimage that can lead to h∗ . Then we have
Pr(f,p),ρ [H = h∗ ] = 0, and so in both cases
∗|
Pr [H = h∗ ] ≤ 2−n|h (2)
(f,p),ρ
This implies that the statistical distance of the distribution over h∗ which we described to the
uniform distribution is exactly the probability that (f, p) is not good. For completeness, we give
a formal argument for this. Consider H as above, and let U be a random variable taking uniform
35
∗
random values from {0, 1}|h | . We have
1 X
Pr[U = h∗ ] − Pr [H = h∗ ]

d(U, H) =
2 (f,p),ρ
h∗
1 1 X
Pr[U = h∗ ] − Pr [H = h∗ ]

= Pr[U = ⊥] − Pr [H = ⊥] +
2 | {z } (f,p),ρ 2 ∗ (f,p),ρ
=0 | {z } h 6=⊥
=Pr(f,p) [(f,p) is not good]
1 1 X 1 X
= Pr ((f, p) is not good) + Pr[U = h∗ ] − Pr [H = h∗ ]
2 (f,p) 2 ∗ 2 (f,p),ρ
h 6=⊥ h∗ 6=⊥
| {z } | {z }
=1 =1−Pr(f,p) [(f,p) is not good]
= Pr [(f, p) is not good] ,

(f,p)
where the third equality uses (2).

We proceed to argue that Pr(f,p) [(f, p) is not good] is small. In S2 (f, p), by Lemma 3.3 we have
that |Gi | ≤ 6 · (14 · q)2 and |P | ≤ 6 · (14 · q)2 , where the additional factor of 14 comes in because the
2 )5
distinguisher completes all chains. By Lemma 3.19 Pr(f,p) [(f, p) is not good] ≤ 16 000 · (6·(14·q) 2n <
4·1019 ·q 10
2n .
By Lemma 3.32, for good (f, p), the behaviour of S2 (f, p) and S3 (H) is identical. Thus,
Pr(f,p) [D outputs 1 in S2 (f, p)] − Pr(f,p) [D outputs 1 in S3 (H)] ≤ Pr(f,p) [(f, p) is not good]. Fur-
thermore,

Pr [D outputs 1 in S2 (H)] − Pr[D outputs 1 in S3 (U )] ≤ d(H, U ) = Pr [(f, p) is not good],
(f,p) (f,p)
and therefore

Pr [D outputs 1 in S2 (f, p)] − Pr[D outputs 1 in S3 (U )] ≤ 2 · Pr [(f, p) is not good]
(f,p) (f,p)
8 · 1019 · q 10
< ,
2n
using our bound on the probability that (f, p) is good above.
Acknowledgements
It is a pleasure to thank Ueli Maurer and Yannick Seurin for their insightful feedback.
Robin Künzler was partially supported by the Swiss National Science Foundation (SNF), project
no. 200021-132508. Stefano Tessaro was partially supported by NSF grant CNS-0716790; part of
this work was done while he was a graduate student at ETH Zurich.
References
[BK03] Mihir Bellare and Tadayoshi Kohno. A theoretical treatment of related-key attacks:
RKA-PRPs, RKA-PRFs, and applications. In Advances in Cryptology — EURO-
CRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 491–506,
2003.
36
[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: a paradigm for
designing efficient protocols. In CCS ’93: Proceedings of the 1st ACM conference on
Computer and communications security, pages 62–73, New York, NY, USA, 1993. ACM.
[BR94] Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In Advances in
Cryptology — EUROCRYPT ’94, Lecture Notes in Computer Science, pages 92–111,
1994.
[BR96] Mihir Bellare and Phillip Rogaway. The exact security of digital signatures - How to
sign with RSA and Rabin. In Advances in Cryptology — EUROCRYPT ’96, Lecture
Notes in Computer Science, pages 399–416, 1996.
[BR06] Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework
for code-based game-playing proofs. In Advances in Cryptology — EUROCRYPT 2006,
volume 4004 of Lecture Notes in Computer Science, pages 409–426, 2006.
[BRS02] John Black, Phillip Rogaway, and Thomas Shrimpton. Black-box analysis of the block-
cipher-based hash-function constructions from pgv. In Advances in Cryptology —
CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 320–335,
2002.
[Can01] Ran Canetti. Universally composable security: A new paradigm for cryptographic pro-
tocols. In FOCS ’01: Proceedings of the 42nd IEEE Annual Symposium on Foundations
of Computer Science, pages 136–145, 2001.
[CDMP05] Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, and Prashant Puniya. Merkle–
Damgård revisited: How to construct a hash function. Lecture Notes in Computer
Science, pages 430–448, 2005.
[CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, re-
visited. J. ACM, 51(4):557–594, 2004.
[CPS08a] Jean-Sébastien Coron, Jacques Patarin, and Yannick Seurin. The random oracle model
and the ideal cipher model are equivalent. In David Wagner, editor, CRYPTO, volume
5157 of Lecture Notes in Computer Science, pages 1–20. Springer, 2008.
[CPS08b] Jean-Sebastien Coron, Jacques Patarin, and Yannick Seurin. The random oracle model
and the ideal cipher model are equivalent. Cryptology ePrint Archive, Report 2008/246,
May 2008. Version: 20080603:012059, http://eprint.iacr.org/.
[CPS08c] Jean-Sebastien Coron, Jacques Patarin, and Yannick Seurin. The random oracle model
and the ideal cipher model are equivalent. Cryptology ePrint Archive, Report 2008/246,
August 2008. Version: 20080816:121712, http://eprint.iacr.org/, Extended Ab-
stract at CRYPTO 2008.
[Dam89] Ivan B. Damgård. A design principle for hash functions. In Advances in Cryptology —
CRYPTO ’89, volume 435 of Lecture Notes in Computer Science, pages 416–427, 1989.
[DP06] Yevgeniy Dodis and Prashant Puniya. On the relation between the ideal cipher and
the random oracle models. In Theory of Cryptography — TCC 2006, volume 3876 of
Lecture Notes in Computer Science, pages 184–206, 2006.
37
[DPW10] Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. Non-malleable codes. In
Innovations in Computer Science - ICS 2010, pages 434–452, 2010.
[GM09] Peter Gaži and Ueli Maurer. Cascade encryption revisited. In Advances in Cryptology
— ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 37–51,
December 2009.
[HKT10] Thomas Holenstein, Robin Künzler, and Stefano Tessaro. The equivalence of the ran-
dom oracle model and the ideal cipher model, revisited, 2010. Available on arXiv.org.
[KOS10] Eike Kiltz, Adam O’Neill, and Adam Smith. Instantiability of rsa-oaep under chosen-
plaintext attack. In Advances in Cryptology — CRYPTO 2009, volume 6223 of Lecture
Notes in Computer Science, pages 295–313, 2010.
[KSS00] Jeff Kahn, Michael E. Saks, and Clifford D. Smyth. A dual version of reimer’s inequality
and a proof of rudich’s conjecture. In IEEE Conference on Computational Complexity,
pages 98–103, 2000.
[Kün09] Robin Künzler. Are the random oracle and the ideal cipher models equivalent? Master’s
thesis, ETH Zurich, Switzerland, 2009. Available on http://www.complexity.ethz.
ch/.
[LR88] Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from
pseudorandom functions. SIAM J. Comput., 17(2):373–386, 1988.
[LZ09] Yehuda Lindell and Hila Zarosim. Adaptive zero-knowledge proofs and adaptively
secure oblivious transfer. In Theory of Cryptography Conference — TCC 2009, volume
5444 of Lecture Notes in Computer Science, pages 183–201, 2009.
[Mau02] Ueli Maurer. Indistinguishability of random systems. In Advances in Cryptology —

EUROCRYPT 2002, volume 2332 of Lecture Notes in Computer Science, pages 110–
132, 2002.
[Mer89] Ralph C. Merkle. A certified digital signature. In Advances in Cryptology — CRYPTO

’89, volume 435 of Lecture Notes in Computer Science, pages 218–238, 1989.
[MRH04] Ueli Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, impossibility
results on reductions, and applications to the random oracle methodology. In Theory
of Cryptography Conference — TCC 2004, volume 2951 of Lecture Notes in Computer
Science, pages 21–39, February 2004.
[Rud89] Steven Rudich. Limits on the Provable Consequences of One-way Functions. PhD
thesis, 1989.
[Seu09] Yannick Seurin. Primitives et protocoles cryptographiques à sécurité prouvée. PhD

thesis, Université de Versailles Saint-Quentin-en-Yvelines, UFR de Sciences - École
doctorale SoFt - Laboratoire PRiSM, 2009.
[Sho04] Victor Shoup. Sequences of games: A tool for taming complexity in security proofs,
2004.
38
A Detailed Definition of the Simulator of Coron et al.
We proceed to provide the full definition of the simulator in [CPS08c]. In particular, for ease
of reference, we stick to the same variable naming used within their work, even though this is
inconsistent with the notation used in the rest of this paper.
As sketched in the simulator overview, S keeps a history of the function values it has defined
up to the current point of execution, which consist of sets H(Fi ) of pairs (x, Fi (x)). With some
abuse of notation, and to improve readability, we denote as Fi := {x|(x, Fi (x)) ∈ H(Fi )} the set of
Fi -queries whose values have been defined. We define the history H := {(x, Fi (x), i)|(x, Fi (x)) ∈
H(Fi ) for some i}.
Also, if the history size gets too big, i.e. |H(Fi )| > hmax for some Fi and a value hmax depending
only on the number of distinguisher queries q, the simulator aborts.
Procedures Query and ChainQuery. Upon a query x for Fk issued by D, the simulator S
executes the following prodecure Query(x, k):
1 procedure Query(x, k):
2 if x ∈ Fk then
3 return Fk (x) from H(Fk )
4 else
5 Fk (x) ←R {0, 1}n
6 ChainQuery(x, k)
7 return Fk (x) from H(Fk )
Procedure ChainQuery checks if 3-chains as defined in Fig. 3 w.r.t. query x occur. Note that this
is only a selection of all possible chains one might consider. Observe that the chain sets for F1 , F2
and F3 are defined symmetrically to those of F4 , F5 and F6 . In particular, the sets F∗6 and F∗1 are
Query to Chain Sets

C(−, R, 1) = (S, A) ∈ (F6 , F5 ) | P−1 (S||A ⊕ F6 (S))|

F1 2=R
F2 C(+, X, 2) = (Y, Z) ∈ (F3 , F4 ) | X = F3 (Y ) ⊕ Z
C(−, X, 2) = (R, S) ∈ (F1 , F∗6 (X)) | P(X ⊕ F1 (R)||R)|

1 =S
F3 C(+, Y, 3) = (Z, A) ∈ (F4 , F5 ) | Y = F4 (Z) ⊕ A
F4 C(−, Z, 4) = (Y, X) ∈ (F3 , F2 ) | Z = F3 (Y ) ⊕ X
C(+, A, 5) = (S, R) ∈ (F6 , F∗1 (A)) | P−1 (S||A ⊕

F5 F6 (S))|2 = R
C(−, A, 5) = (Z, Y ) ∈ (F4 , F3 ) | A = F4 (Z) ⊕ Y
F6 C(+, S, 6) = (R, X) ∈ (F1 , F2 ) | P(X ⊕ F1 (R)||R)|1 = S
Figure 3: Chains to be considered by Procedure ChainQuery.
defined as follows for the understood parameters X and A:
F∗6 (X) := F6 ∪ S|∃(R0 , X 0 ) ∈ (F1 , F2 \ {X}), P(X 0 ⊕ F1 (R0 )||R0 )|1 = S

F∗1 (A) := F1 ∪ R|∃(S 0 , A0 ) ∈ (F6 , F5 \ {A}), P−1 (S 0 ||A0 ⊕ F6 (S 0 ))|2 = R

The chains that are considered additionally when using the sets F∗i instead of Fi in the cases of
(F2 , −) and (F5 , +) chains are called virtual chains. These chains do not consist of history values
exclusively. If such a chain occurs, the simulator first defines the three values that constitute the
3-chain that are not yet in the history and then completes it. The intuition15 why such virtual
15
This intuition comes from studying the proof in [CPS08b]
39
chains are considered in addition is as follows: Every time the sets C(−, R, 1) for some R and
symmetrically C(+, S, 6) for some S are computed, it will not be possible that more than one such
chain is found. Note that it is not clear at this point if this goal can indeed be achieved. Intuitively,
such a fact might simplify (or even make possible) the analysis of the recursions of the simulator.
The procedure ChainQuery now handles the recursions. We still consider the chains in Fig. 3.
If such 3-chains occur, ChainQuery calls a further procedure, called CompleteChain, to com-
plete these chains, i.e. it consistently (with P) fills in the remaining values for each 3-chain. Then,
ChainQuery is called recursively for the values defined during the completions of chains:
8 procedure ChainQuery(x, k):
9 if k ∈ {1, 2, 5, 6} then XorQuery1 (x, k)
10 if k ∈ {1, 3, 4, 6} then XorQuery2 (x, k)
11 if k ∈ {3, 4} then XorQuery3 (x, k)
12 U := ∅
13 if k ∈ {2, 3, 5, 6} then
14 forall (y, z) ∈ C(+, x, k) do
15 U := U ∪ CompleteChain(+, x, y, z, k)
16 if k ∈ {1, 2, 4, 5} then
17 forall (y, z) ∈ C(−, x, k) do
18 U := U ∪ CompleteChain(−, x, y, z, k)
19 forall (x0 , k 0 ) ∈ U do
20 ChainQuery(x0 , k 0 )
The first three lines of ChainQuery make calls to the so-called XorQuery procedures: they
perform additional ChainQuery(x0 , k 0 ) executions for values x0 other than x that fullfil certain
properties. This ensures that for the values x0 , we are always sure that ChainQuery(x0 , k 0 ) occurs
before the chains for ChainQuery(x, k) are completed. To understand S one can ignore, for the
moment, the details about the XorQuery procedures: We first detail CompleteChain and only
subsequently address the XorQuery procedures.
Procedure CompleteChain. Procedure CompleteChain completes a chain (x, y, z), given

direction d and the index k of Fk according to the following table.
Query x to Fk Dir d (y, z) in History Additionally Compute Adapt (Fj , Fj+1 )

set Fi
F1 − (F6 , F5 ) F4 S||T (F2 , F3 )
F2 + (F3 , F4 ) F1 L||R (F5 , F6 )
− (F1 , F6 ) F3 L||R (F4 , F5 )
F3 + (F4 , F5 ) F6 S||T (F1 , F2 )
F4 − (F3 , F2 ) F1 L||R (F5 , F6 )
F5 + (F6 , F1 ) F4 S||T (F2 , F3 )
− (F4 , F3 ) F6 S||T (F1 , F2 )
F6 + (F1 , F2 ) F3 L||R (F4 , F5 )
In detail this looks as follows:

21 procedure CompleteChain(d, x, y, z, k):
22 U := ∅
23 if there was a CompleteChain−execution w.r.t.˜values x, y, z before then
40
24 return U
25 else
26 if (d, k) = (−, 2) and z ∈ / F6 then
27 F6 (z) ←R {0, 1}n
28 U := U ∪ {(z, 6)}
29 if (d, k) = (+, 5) and z ∈ / F1 then
30 F1 (z) ←R {0, 1} n
31 U := U ∪ {(z, 1)}
32 compute xi (i according to the table, additional ’set’)
33 if xi ∈/ Fi then
34 Fi (xi ) ←R {0, 1}n
35 U := U ∪ {(xi , i)}
36 if Compute L||R (according to the table) then
37 compute L||R
38 compute S||T := P(L||R)
39 if Compute S||T (according to the table) then
40 compute S||T
41 compute L||R := P−1 (S||T )
42 now all inputs (x1 , x2 , . . . , x6 ) to (F1 , F2 , . . . , F6 ) of the completion of (x, y, z) are known
43 compute x0 := L, x7 := T
44 if xj ∈ Fj or xj+1 ∈ Fj+1 then
45 abort
46 else (adapt according to the table)
47 Fj (xj ) := xj−1 ⊕ xj+1
48 Fj+1 (xj+1 ) := xj ⊕ xj+2
49 U := U ∪ {(xj , j), (xj+1 , j + 1)}
50 return U
Lines 2 and 3 need further explanation. We assume that the simulator keeps track of the 6-tuples
(R, X, Y, Z, A, S) of values that were defined in any CompleteChain-execution up to the current
point of execution. In line 2, CompleteChain checks whether the values x, y, z for given k, d are
part of such a 6-tuple of values that were defined in some earlier CompleteChain-execution. If
so, the empty set is returned. For example, if in ChainQuery(R0 , 1) we find (S 0 , A0 ) ∈ C(−, R0 , 1),
then CompleteChain(−, R0 , S 0 , A0 , 1) occurs and line 2 checks if there is a 6-tuple (R, X, Y, Z, A, S)
from an earlier CompleteChain-execution where R = R0 , S = S 0 and A = A0 . If so, the chain
(S 0 , A0 ) is not completed again and the empty set is returned in line 3 immediately. Note that
steps 2 and 3 were not included in the simulator definition in [CPS08c]. But if these steps are not
performed, the simulator trivially aborts as soon as a recursive CompleteChain call occurs in
ChainQuery. (In the above example of (S 0 , A0 ), if the values (R0 , X, Y, Z, A0 , S 0 ) were defined in
an earlier CompleteChain-execution, the simulator would abort at step 29 of CompleteChain,
since both Y ∈ F3 and X ∈ F2 already.) Furthermore, note that lines 5 to 11 are used to define
missing function values for virtual chains.
Fig. 4 illustrates how the simulator S completes 3-chains.
The XorQuery procedures. As mentioned earlier, the procedures XorQuery1 , XorQuery2 ,

and XorQuery3 perform additional calls to ChainQuery before the chains for ChainQuery(x, k)
are completed.
The idea behind XorQuery1 is the following: We consider the execution of ChainQuery(X, 2)
41
figCCSv2
Figure 4: An illustration of how S completes 3-chains
for some X and in this execution a recursive call to ChainQuery(Y, 3) that occurs for some Y .
For ChainQuery(Y, 3), XorQuery1 should ensure that for any (F3 , +) chain (Y, Z, A), X :=
F3 (Y )⊕Z is not in F2 . The same property should be ensured symmetrically for ChainQuery(A, 5).
51 procedure XorQuery1 (x, k):
52 if k = 5 then
53 A0 := {x ⊕ R1 ⊕ R2 ∈ / F5 |R1 , R2 ∈ F1 , R1 6= R2 }
55 A0 := {A ⊕ x ⊕ R2 ∈ / F5 |A ∈ F5 , R2 ∈ F1 }
56 if k = 5 or k = 1 then
57 forall A0 ∈ A0 do
58 if ∃R0 ∈ F1 , ∃S 0 ∈ F6 : P−1 (S 0 ||F6 (S 0 ) ⊕ A0 )|2 = R0 then
59 F5 (A0 ) ←R {0, 1}n
60 ChainQuery(A0 , 5)
61 if k = 2 then
62 X 0 := {x ⊕ S1 ⊕ S2 ∈ / F2 |S1 , S2 ∈ F6 , S1 6= S2 }
64 X 0 := {X ⊕ x ⊕ S2 ∈ / F2 |X ∈ F2 , S2 ∈ F6 }
65 if k = 2 or k = 6 then
66 forall X 0 ∈ X 0 do
67 if ∃S 0 ∈ F6 , ∃R0 ∈ F1 : P(F1 (R0 ) ⊕ X 0 ||R0 )|1 = S 0 then
68 F2 (X 0 ) ←R {0, 1}n
69 ChainQuery(X 0 , 2)
XorQuery2 and XorQuery3 are used as follows: Consider the execution of ChainQuery(Y, 3)
for some Y and in this execution a recursive call to ChainQuery(X, 2). These two procedures
should ensure that, under certain assumptions, the simulator does not abort in the next two recur-
42
sion levels, and after these two levels certain properties hold. The same holds symmetrically for
ChainQuery(A, 5) for some A. Again, this is just an intuition and it is not clear at this point if
these goals are achievable with XorQuery2 and XorQuery3 .
71 M := {(L, R, Z, A, S)|P−1 (S||A ⊕ F6 (S)) = L||R,
72 R∈ / F1 ,
73 A ∈ F5 ,
74 S ∈ F6 ,
75 Z = F5 (A) ⊕ S}
76 forall (L, R, Z, A, S) ∈ M do
77 if k = 6 and ∃Z 0 ∈ F4 \ {Z} : P(L ⊕ Z ⊕ Z 0 ||R)|1 = x or
78 k = 3 and ∃S 0 ∈ F6 : P(L ⊕ x ⊕ Z||R)|1 = S 0 then
79 F1 (R) ←R {0, 1}n
80 ChainQuery(R, 1)
81 M := {(S, T, R, X, Y )|P(X ⊕ F1 (R)||R) = S||T,
82 S∈ / F5 ,
83 X ∈ F2 ,
84 R ∈ F1 ,
85 Y = F2 (X) ⊕ R}
86 forall (S, T, R, X, Y ) ∈ M do
87 if k = 1 and ∃Y 0 ∈ F3 \ {Y } : P−1 (S||T ⊕ Y ⊕ Y 0 )|2 = x or
88 k = 4 and ∃R0 ∈ F1 , : P−1 (S||T ⊕ x ⊕ Y )|2 = R0 then
89 F6 (S) ←R {0, 1}n
90 ChainQuery(S, 6)
91
92

94 R := {(Y, R1 , R2 )|P−1 (S1 ||A1 ⊕ F6 (S1 )) = L1 ||R1 ,
95 P−1 (S2 ||A2 ⊕ F6 (S2 )) = L2 ||R2 ,
96 Y ∈ / F3 ,
97 S 1 ∈ F6
98 Z1 = F5 (A1 ) ⊕ S1 , Z1 ∈ F4 ,
99 A1 = F4 (Z1 ) ⊕ Y, A1 ∈ F5
100 S 2 ∈ F6
101 Z2 = F5 (A2 ) ⊕ S2 , Z2 ∈ F4 ,
102 A2 = F4 (Z2 ) ⊕ Y, A2 ∈ F5 }
103 if k = 3 and ∃(Y, R1 , R2 ) ∈ R : Y = x ⊕ R1 ⊕ R2 then
104 F3 (Y ) ←R {0, 1}n
105 ChainQuery(Y, 3)
106 S := {(Z, S1 , S2 )|P(F1 (R1 ) ⊕ X1 ||R1 ) = S1 ||T1 ,
107 P(F1 (R2 ) ⊕ X2 ||R2 ) = S2 ||T2 ,
108 Z∈ / F4 ,
109 R1 ∈ F1
110 Y1 = F2 (X1 ) ⊕ R1 , Y1 ∈ F3 ,
111 X1 = F3 (Y1 ) ⊕ Z, X1 ∈ F2
112 R2 ∈ F1
113 Y2 = F2 (X2 ) ⊕ R2 , Y2 ∈ F3 ,
43
114 X2 = F3 (Y2 ) ⊕ Z, X2 ∈ F2 }
115 if k = 4 and ∃(Z, S1 , S2 ) ∈ S : Z = x ⊕ S1 ⊕ S2 then
116 F4 (Z) ←R {0, 1}n
117 ChainQuery(Z, 4)
Illustrations describing the XorQuery procedures. We provide illustrations to better de-

scribe procedures XorQuery1 , XorQuery2 , and XorQuery3 .
Fig. 5 illustrates how XorQuery1 works. In the figure, the values that are required to be in
the history are marked with boxes, and the value x that XorQuery1 is called upon is marked with
a circle. We abbreviate ChainQuery by CQ.
For example, the left upper quarter of Fig. 5 describes calls to XorQuery1 (A, 5) for some A.
Upon such a call, S computes the values A0 for any pairs R1 , R2 in F1 where R1 6= R2 . Now if some
A0 is not in F5 (in the figure, there is no box around A0 ), then S checks if there is a 3-chain (A0 , S 0 , R0 )
for some S 0 ∈ F6 and R0 ∈ F1 (in the figure, there are boxes around these values). If such a chain
figXorQuery1
is found, S calls ChainQuery(A0 , 5). In the figure, we write XorQuery1 (A, 5) → CQ(A0 , 5) to
say this.
Figure 5: An illustration for XorQuery1
Fig. 6 provides an illustration of XorQuery2 . The notation is the same as in the illustration
for XorQuery1 .
For XorQuery3 we provide Fig. 7 to faciliate the understanding.
Here is a description of XorQuery3 for the case of k = 3: Upon query (x, 3) where x = Ȳ the
procedure sets F3 (Y ) ←R {0, 1}n and calls ChainQuery(Y, 3) for any Y ∈ / F3 if there are 3-chains
(Z1 , A1 , S1 ) and (Z2 , A2 , S2 ) (as in the figure) in the history and the corresponding R1 and R2 are
XorQueries
such that Ȳ = Y ⊕ R1 ⊕ R2 .
44
figXorQuery2
B Detailed Analysis of the Attack against the Simulator of Coron

et al.
Formally, the distinguisher D is defined as follows. (The distinguisher’s output bit is irrelevant,
since its goal is to let the simulator abort.)
XorQueries
1 Distinguisher D
2 X ←R {0, 1}n , R2 ←R {0, 1}n , R3 ←R {0, 1}n
3 L2 := F1 (R2 ) ⊕ X, L3 := F1 (R3 ) ⊕ X
4 S2 kT2 := P(L2 kR2 ), S3 kT3 := P(L3 kR3 )
5 A2 := F6 (S2 ) ⊕ T2 , A3 := F6 (S3 ) ⊕ T3
6 R1 := R2 ⊕ A2 ⊕ A3
7 L1 := F1 (R1 ) ⊕ X
8 S1 kT1 := P(L1 kR1 )
9 A1 := F6 (S1 ) ⊕ T1
10 Ā := A1 ⊕ R1 ⊕ R2
11 query F5 (Ā)
Implementing P. The distinguisher makes 7 < 23 queries to F and three permutation queries.
Assume without loss of generality that at most B := 250 queries are made to the permutation P (or
its inverse P−1 ) by the simulator or by the distinguisher. Once more than B P queries are made,
we assume that the simulator S aborts. By Lemma 1 in [CPS08c], the probability that abort occurs
in the original experiment (where no limit on the number of P queries made by the simulator is
imposed) is at most 255 /2n = O(2−n ) lower than in the version where the query number is bounded
by B. Note that, while large, B is constant, and although it could be made significantly smaller
for the purposes of this section, we use the larger value to rely on the analysis of [CPS08c].
45
figXorQuery3
It is convenient to think of P as being implemented as follows: Initially, two lists L↓ and L↑ of

B uniformly distributed, but distinct, 2n-bit values are generated. Then, each time a P query is
issued with input x, we first check if P(x) is defined (in which case we simply return the previously
defined value), or if P−1 (y) = x (in which case we return y.) Otherwise, we assign to P(x) the first
value y in L↓ such that P−1 (y) is undefined, and let P−1 (y) := x. Also, P−1 queries are answered
symmetrically. It is not hard to verify that this gives rise to a uniform random permutation as
long as at most B queries are made: Each forward query P(x) assigns a value from L↓ which is
uniformly distributed among all values for which P−1 (y) is not defined, and, if x ∈ L↑ , ensures that
x ∈ L↓ cannot be used as an answer to a query to P−1 .
For simplicity, denote as L1 and L2 the lists containing the first and second halves, respectively,
of the elements of L := L↓ kL↑ . (Here, k denotes list concatenation.)
Initialization. We consider the interaction of D and S, and show that the latter aborts with
overwhelming probability. Before executing Line 11, it is clear that no additional Fi (x) entry is
defined by one ofXorQueries
the XorQuery calls, since only XorQuery1 and XorQuery2 can be called
when answering queries to either of F1 or F6 , but the histories of F2 , F3 , F4 , F5 are all empty. Thus
when F5 (Ā) is called, only the values R1 , R2 , R3 , S1 , S2 , S3 are in the history of S, and consequently,
no 3-chain exists so far. Also, the first three elements of L are S1 kT1 , S2 kT2 , and S3 kT3 .
The following definitions introduce bad events: Their definition is tailored at what is needed
later, and may appear confusing at first. (We invite the reader to skip their definition, and come
back later.)
Definition B.1. The event BadP occurs if one of the following is true:
(i) There exists a collision among the first or second halves of the elements of L;
(ii) L2 ∩ {R1 , R2 , R3 } =
6 ∅, that is, the second half of some element of L is in {R1 , R2 , R3 };
(iii) There exists R, R0 ∈ L2 such that R1 ⊕ R2 = R ⊕ R0 .
Definition B.2. The event Bad1 occurs if one of the following is true:
(i) Two elements among R1 , R2 , R3 collide;
(ii) A ⊕ F6 (S) ∈ L2 for (A, S) ∈ (F5 ∪ {Ā}) × F6 \ {(Ai , Si ) | i = 1, 2, 3};
46
(iii) There exists (i, j) ∈ {(1, 3), (2, 3)} and k ∈ {1, 2, 3} such that for A0 := Ā ⊕ Ri ⊕ Rj ∈
/ F5 we
0
have F6 (Sk ) ⊕ A ∈ L2 ;
(iv) There exist i, j, k, ` ∈ {1, 2, 3}, i 6= j, such that for A00 := A` ⊕ Ri ⊕ Rj ∈

/ F5 we have
00
F6 (Sk ) ⊕ A ∈ L2 ;
(v) Ri ⊕ Rj ⊕ Aj ⊕ A = 0n for i 6= j, A ∈ {Ā, A1 , A2 , A3 }, and (i, j, A) ∈

/ {(i, i, Ai ) | i = 1, 2, 3} ∪
{(1, 2, A3 ), (2, 1, Ā)}.
♦
The following two lemmas upper bound the probability of these events occurring.
Lemma B.3. Pr[BadP ] = O(B 2 · 2−n ).
Proof. For (i), note that for any two i, j ∈ {1, . . . , 2B}, i 6= j, and h ∈ {1, 2},
2n · (2n − 1)
Pr[Vi |h = Vj |h ] = 2n · = O(2−n )
22n · (22n − 1)
and Pr[Vi |h ∈ {R1 , R2 , R3 }] ≤ 3 · 2−n . The bound follows by the union bound. Finally, an upper
n n −1)
bound of the probability of (iii) is B 2 · 2n 222n·(2
(22n −1)
= O(B 2 · 2−n ).
Lemma B.4. Pr[Bad1 ] = O(B · 2−n ).

Proof. For (i), we observe that the random variable R1 is uniform and independent of R2 and R3 ,
since A2 and A3 are independent of R2 and R3 due to F6 (S2 ) and F6 (S3 ) being chosen uniformly
and independently. Thus, the probability that R1 = R2 , R2 = R3 or R1 = R3 is at most 3 · 2−n .
It is also easy to verify that the value T 0 := A ⊕ F6 (S) is uniformly distributed and independent
of L for (A, S) ∈ (F5 ∪{Ā})×F6 \{(Ai , Si ) | i = 1, 2, 3}, and therefore T 0 ∈ L2 holds with probability
at most 2B · 2−n ; an upper bound on the probability of (ii) follows by the union bound.
To bound (iii), we use the fact that for all (i, j) ∈ {(1, 3), (2, 3)} and k ∈ {1, 2, 3} the value
T := F6 (Sk ) ⊕ A0 equals
0
F6 (Sk ) ⊕ F6 (S1 ) ⊕ T1 ⊕ R1 ⊕ R2 ⊕ Ri ⊕ Rj
and is hence uniformly distributed and independent of L. Therefore, (iii) occurs with probability
at most 2B · 2−n . Similarly, to bound (iv), we observe that for all i 6= j, and k, ` ∈ {1, 2, 3} the
value T 00 := F6 (Sk ) ⊕ A00 equals
F6 (Sk ) ⊕ F6 (S` ) ⊕ T` ⊕ Ri ⊕ Rj
and is therefore uniformly distributed, and independent of L.

In (v) we see that in all cases, substituting Ā with A1 ⊕ R1 ⊕ R2 , Ai with F6 (Si ) ⊕ Ti , and R1
with R2 ⊕ A2 ⊕ A3 , we end up in one of the follwing two cases: Either the given sum still contains
at least one term which is uniformly distributed and independent of the other terms, and thus the
sum equals 0n with probability 2−n . Or, the resulting equation is R2 = R3 , which does not hold
by the choice of these values by D. The actual bound follows by a union bound over all possible
combinations.
From now on, the analysis assumes that neither of BadP and Bad1 has occurred. Before we
proceed in analyzing the rest of the execution, we prove the following lemmas, which will be useful
to simplify the analysis below, and rely on the assumptions that the above events do not occur.
47
Lemma B.5. As long as F1 = {R1 , R2 , R3 } and F6 = {S1 , S2 , S3 }, no XorQuery1 (Ai , 5) (for
i = 1, 2, 3) call results in a recursive ChainQuery call.
Proof. For the if statement within XorQuery1 (Ai , 5) call to be satisfied, there must exist A00 =
Ai ⊕ Ri ⊕ Rj such that Ri 6= Rj and P−1 (S 0 kF(S 0 ) ⊕ A00 )|2 ∈ {R1 , R2 , R3 }, where S 0 ∈ {S1 , S2 , S3 }.
/ L2 , as this implies Bad1 , we need to have P−1 (S 0 kF6 (S 0 ) ⊕ A00 ) ∈ L.
However, since F(S 0 ) ⊕ A00 ∈
But then, since P−1 (S 0 kF(S 0 ) ⊕ A00 )|2 ∈ {R1 , R2 , R3 }, we also have BadP .
Lemma B.6. Assume that F1 = {R1 , R2 , R3 } and F6 = {S1 , S2 , S3 }. Then, as long as BadP
holds, a call to XorQuery2 (x, k) for k ∈ {3, 4} and x ∈
/ F7−k does not set any new values and
does not make any new recursive ChainQuery calls.
Proof. Let k = 3 and consider a tuple (L, R, Z, A, S) ∈ M: This means that querying P−1 on
input SkF6 (S) ⊕ A (with S = Si for some i ∈ {1, 2, 3}) returns a pair LkR with R ∈ / {R1 , R2 , R3 }.
This in particular means that A 6= Ai (as otherwise R = Ri ), and also that LkR ∈ L, as otherwise
Si kF6 (Si ) ⊕ A ∈ L, and (ii) for Bad1 would have occurred. However, if the if statement is satisfied,
this also means that P(L ⊕ x ⊕ ZkR)|1 = S 0 ∈ {S1 , S2 , S3 }. But since BadP has not happened, this
means that there has been a previous P−1 query with input S 0 kT 0 which has returned L⊕x⊕ZkR ∈
L. Yet, since L ⊕ x ⊕ Z 6= L (due to x 6= Z, as otherwise x ∈ F4 ), this also means that there has
been a collision on the second half, and BadP has occurred.
The case for k = 4 is fully symmetric.
Added complexity in the execution of S stems from the fact that it tests for so-called “virtual
chains”, and we want to argue that they do not play a role in the upcoming analysis of the attack.
First, note that as long as F2 contains at most one element (this is the case for most of the attack),
F∗6 = F6 . Additionally, when calling ChainQuery(A, 5) for A ∈ {Ā, A1 , A2 , A3 }, in order for
F1 6= F∗1 to occur, we need that there exist (A, S), (A0 , S 0 ) ∈ {Ā, A1 , A2 , A3 } × {S1 , S2 , S2 } such
that A 6= A0 and P−1 (SkF6 (S) ⊕ A)|2 = P−1 (S 0 kF6 (S 0 ) ⊕ A0 ). It is not hard to verify that any
possible case implies BadP or Bad1 , and hence we can safely ignore virtual chains in the following.
(We will indeed need to ignore virtual chains only for as long as the conditions needed for these
arguments hold.)
First phase of the simulator’s execution. From now on, we continue the analysis of the execution
under the assumption that Bad1 , and BadP have not occurred. Upon querying F5 (Ā), the simulator
sets F5 (Ā) ←R {0, 1}n and then first executes XorQuery1 (Ā, 5): Note that A1 = Ā⊕R1 ⊕R2 ∈ / F5
(since, at this point, the history of F5 is empty), and A1 satisfies the if statement (with S 0 = S1
and R0 = R1 ) so that F5 (A1 ) ←R {0, 1}n is set and ChainQuery(A1 , 5) is called. Also, no other
ChainQuery call occurs, as if the condition in the if statement is true for some other value, then
since (ii) in the definition of Bad1 does not occur, this means that, for some input x, P(x) has been
assigned a value from L whose second half is in {R1 , R2 , R3 }, which implies BadP .
Moreover, in the subsequent execution of ChainQuery(A1 , 5) the procedure XorQuery1 also
does not invoke ChainQuery by Lemma B.5. Moreover, C(+, A1 , 5) = {(S1 , R1 )}, since (A1 , Si , Rj )
for (i, j) 6= (1, 1) cannot constitute a chain, as this would either imply (i) in the definition of Bad1
or the fact that BadP occurs. Also, C(−, A1 , 5) = ∅, since no F3 and F4 values have been defined
so far. Therefore, (S1 , R1 ) ∈ C(+, A1 , 5) is found and gets completed by CompleteChain to the
tuple (R1 , X, Y1 , Z1 , A1 , S1 ), by defining
X := F1 (R1 ) ⊕ L1 , Z1 := F5 (A1 ) ⊕ S1 , F4 (Z1 ) ←R {0, 1}n ,
Y1 := F4 (Z1 ) ⊕ A1 , F2 (X) := R1 ⊕ Y1 , F3 (Y1 ) := Z1 ⊕ X.
We consider the following event defined on these new values.
48
Definition B.7. The event Bad2 occurs if one of the following holds:
(i) Y1 = Z1 ;
(ii) Y1 = Z1 ⊕ R1 ⊕ R where R ∈ {R2 , R3 };
(iii) Z1 ⊕ F5 (Ā) ∈ L1 ;
(iv) Z1 ⊕ F5 (Ā) = S1 .
Lemma B.8. Pr[Bad2 ] = O(B · 2−n )
Proof. For (i) and (ii), since Y1 is uniform and independent of Z1 , R1 , and R2 by the fact that
F5 (Y1 ) is set uniformly, the values on both sides are equal with probability 2−n . Furthermore, both
F5 (Ā) and F5 (A1 ) are set uniformly (since A1 6= Ā by Bad1 not occurring), and thus Z1 ⊕ F5 (Ā) =
S1 ⊕ F5 (A1 ) ⊕ F5 (Ā) is uniform and independent of L1 , and is thus in the set with probability
at most 2B · 2−n by the union bound. Similarly, we show that (iv) occurs with probability 2−n
only.
Second phase of the simulator’s execution. Subsequently, the simulator schedules calls, in arbi-
trary16 order, to ChainQuery(X, 2), ChainQuery(Y1 , 3) and ChainQuery(Z1 , 3).
Lemma B.9. No ChainQuery invocation preceding the invocation of ChainQuery(X, 2) issues

a recursive ChainQuery call. Furthermore, XorQuery1 (X, 2) within ChainQuery(X, 2) also
does not trigger a ChainQuery invocation.
Proof. Assume that ChainQuery(X, 2) has not been invoked yet. Calls to XorQuery2 cannot
invoke ChainQuery recursively by Lemma B.6 and the fact that Y1 6= Z1 (using Bad2 ). Also note
that XorQuery3 (Y1 , 3) cannot produce recursive ChainQuery calls: Note that A1 6= Ā (equality
implies (i) in Bad1 ), and therefore any triple (Y, R, R0 ) ∈ R must satisfy R = R0 and Y ∈ / F3 . But
then, we cannot have Y1 = Y ∈ F3 , and thus the if statement is never satisfied. Similarly, the fact
that XorQuery3 (Z1 , 4) does not invoke ChainQuery follows from the fact that both F3 and F2
only contain one single element.
For both possible ChainQuery calls, it also clear that no additional 3-chains to be completed
are found. Namely, within ChainQuery(Y1 , 3), only the chains (R1 , X, Y1 ) and (Y1 , Z1 , A1 ) are
possible, and both have been completed. Moreover, when running ChainQuery(Z1 , 4), the 3-chain
(X, Y1 , Z1 ) has also already been completed, whereas no chain (Z1 , Ā, S1 ) exists, as this would yield
Bad2 .
Finally, when ChainQuery(X, 2) is invoked, we also observe that if the if statement in the
execution of XorQuery1 (X, 2) cannot be true: It would imply that there exists X 0 6= X such that
P(X 0 ⊕ F1 (Ri )kRi )|1 ∈ {S1 , S2 , S3 }, but since F2 (X 0 ) ⊕ Ri 6= Li , this implies BadP (i).
We hence can consider the execution of ChainQuery(X, 2), as any previous ChainQuery
invocation does not affect the history of the simulated round functions. First, note that C(−, X, 2) =
16
In particular, we do not want to make any assumption on the order in which they are called. Of course, it is
easier to provide a proof if a certain processing order is assumed, and this would suffice to give a strong argument
against S. Still, we opt for showing the strongest statement.
49
{(R2 , S2 ), (R3 , S3 )} and C(+, X, 2) = {(Y1 , Z1 )}. The latter chain was already completed, therefore
both negative chains are completed, by defining values
Y2 := F2 (X) ⊕ R2 , F3 (Y2 ) ←R {0, 1}n , Z2 := X ⊕ F3 (Y2 ),

F4 (Z2 ) := Y2 ⊕ A2 , F5 (A2 ) := Z2 ⊕ S2 ,
as well as
Y3 := F2 (X) ⊕ R3 , F3 (Y3 ) ←R {0, 1}n , Z3 := X ⊕ F3 (Y3 ),

F4 (Z3 ) := Y3 ⊕ A3 , F5 (A3 ) := Z3 ⊕ S3 .
In addition, let us introduce the last bad event in this analysis, defined on the newly defined values.
Definition B.10. The event Bad3 occurs if one of the following holds:
(i) F3 ∩ F4 6= ∅;
(ii) Z ⊕ F5 (A) ∈ L1 for (Z, A) ∈ F4 × F5 \ {(Zi , Ai ) | i = 1, 2, 3}.
Lemma B.11. Pr[Bad3 ] ≤ O(2−n )
Proof. For (i), note that the value of Zi is independent of the value of Y1 , Y2 , Y3 for i = 2, 3, and
thus equality only occurs with negligible probability. (Recall that we already assume that Y1 6= Z1 ).
Moreover, the case that Z1 equals Y2 or Y3 is would already imply Bad2 : This is because we would
have, for i = 2, 3,
Z1 = Yi = F2 (X) ⊕ Ri = R1 ⊕ Y1 ⊕ Ri .
For (ii), we claim that Z ⊕ F5 (A) is always uniform and independent of L when it is defined.
If Z = Z1 , then note that F5 (Ā) is set uniformly and independently of Z1 and L1 , whereas
F5 (Ai ) = X ⊕ F2 (Yi ) ⊕ Si for i = 2, 3, where F2 (Yi ) is set independently and uniformly. If Z = Zi
for i = 2, 3, then note that F5 (A1 ) and F5 (Ā) are set uniformly, whereas by the above F5 (A5−i ) is
also independent and uniform.
Final phase of the simulator’s execution. From now on, ChainQuery(Yi , 3), ChainQuery(Zi , 4)
and ChainQuery(Ai , 5) for i = 2, 3 are called, in any order.17 The crucial point is reached as soon
as one of ChainQuery(Y2 , 3) or ChainQuery(A3 , 5) is invoked. However, we need to show that
all calls preceding one of these calls do not start recursions or set additional function values. First,
however, we show that no other chains occur, other than those we expect.
Lemma B.12. Only the 3-chains (Yi , Zi , Ai ) for i = 1, 2, 3, (Y1 , Z2 , A3 ) and (Y2 , Z1 , Ā) exist in
F3 × F4 × F5 . Moreover, only the three 3-chains (Zi , Ai , Si ) for i = 1, 2, 3 exist in F4 × F5 × F6 .
Proof. Such a chain (Yi , Zj , A) implies
Yi ⊕ F4 (Zj ) ⊕ A = Ri ⊕ F2 (X) ⊕ F4 (Zj ) ⊕ A = Ri ⊕ F2 (X) ⊕ Yj ⊕ Aj ⊕ A

= Ri ⊕ Rj ⊕ Aj ⊕ A = 0n ,
and hence Bad1 . The second part of the statement follows from Bad3 not occurring and the fact
that S1 , S2 , S3 ∈ L1 .
17
Once again, we dispense with any assumption on the execution order adopted by the simulator.
50
Lemma B.13. No ChainQuery call preceding the invocation of both ChainQuery(Y2 , 3) and
ChainQuery(A3 , 5) provokes a recursive ChainQuery call. Also, no XorQuery within the
execution of ChainQuery(Y2 , 3) and ChainQuery(A3 , 5) (whichever is executed first) provokes a
recursive ChainQuery call.
Proof. We know, by Lemma B.6 and item (i) in the definition of Bad3 not taking place, that calls
to XorQuery2 (Y3 , 3), XorQuery2 (Zi , 4) for i = 1, 2 do not provoke any recursive ChainQuery
calls. Furthermore, XorQuery3 (Y3 , 3) cannot invoke ChainQuery, as by Lemma B.12, the fact
that only the three chains (Zi , Ai , Si ) for i = 1, 2, 3 exist in F4 × F5 × F6 , the set R must be empty.
Also, XorQuery3 (Zi , 4) cannot invoke ChainQuery by the fact that X is the only element of
F2 .
In addition, none of these ChainQuery invokes CompleteChain because of Lemma B.12.
The fact that XorQuery1 (A2 , 5) in ChainQuery(A2 , 5) does not make any ChainQuery calls
is implied by Lemma B.5, whereas if ChainQuery(Y2 , 3) is invoked first, then XorQuery2 (Y2 , 3)
does not invoke ChainQuery by Lemma B.6, whereas XorQuery3 (Y2 , 3) does not invoke ChainQuery
because of Lemma B.12 as above.
Finally, we can distinguish two cases:

(1) ChainQuery(Y2 , 3) is invoked first. As shown above, no XorQuery call calls ChainQuery
recursively. Then, S now finds and completes the chain (Z1 , Ā) ∈ C(+, Y2 , 3). No other chains
are found by Lemma B.12.
The following values are set:
X 0 := F3 (Y2 ) ⊕ Z1 , S4 := F5 (Ā) ⊕ Z1 ,
n
F6 (S4 ) ←R {0, 1} , L4 kR4 := P−1 (S4 kF6 (S4 ) ⊕ Ā)
F1 (R4 ) := L4 ⊕ X 0 , F2 (X 0 ) := Y2 ⊕ R4 .
In particular, note that since S4 ∈/ L1 (since Bad3 (ii) does not occur), then R4 ∈ L2 . But then
0
R5 := F2 (X ) ⊕ Y1 ∈ / L2 , as otherwise this would imply that BadP (iii) occurs, since
R5 = Y2 ⊕ R4 ⊕ Y1 = F2 (X) ⊕ R2 ⊕ R4 ⊕ Y1 = R1 ⊕ R2 ⊕ R4 .
Recall that we assume that S5 = F5 (A3 ) ⊕ Z2 ∈ / L1 , as this yields Bad3 (ii). But then, at some
point (the latest at the invocation of ChainQuery(X 0 , 2)) the chain going through X 0 , Y1 ,
Z2 , and A3 needs to be completed. However, no completion is possible, because R5 ∈ / L2 and
S5 ∈/ L1 (by Bad3 (ii)). In fact, this holds regardless of which strategy the simulator employs
to complete the chain, and in this concrete case, this is reflected by an abort.
(2) ChainQuery(A3 , 5) is invoked first. The argument is symmetric. First, by Lemma B.13, no
XorQuery calls trigger ChainQuery invocations, and S now finds and completes the chain
(Y1 , Z2 ) ∈ C(−, A3 , 5), and no other chains are found by Lemma B.12. This in particular means
that the following values are set
X 0 := F3 (Y1 ) ⊕ Z2 , S5 := F5 (A3 ) ⊕ Z2 ,
F6 (S5 ) ←R {0, 1} ,n
L5 kR5 := P−1 (S5 kF6 (S5 ) ⊕ A3 )
F1 (R4 ) := L5 ⊕ X 0 , F2 (X 0 ) := Y1 ⊕ R5 .
Once again, we have that R4 := F2 (X 0 )⊕Y2 ∈
/ L2 because of BadP not occurring, since R5 ∈ L2 ,
and
R4 = Y1 ⊕ R5 ⊕ Y2 = R1 ⊕ F2 (X) ⊕ R5 ⊕ F2 (X) ⊕ R2 = R1 ⊕ R2 ⊕ R5 .
51
Also, we have assumed that F6 (S4 ) ⊕ Ā ∈
/ L1 . But now, at some point, the chain going through
0
X , Y2 , Z1 , and Ā has to be completed. However, this is not possible since R4 ∈ / L2 , and
F6 (S4 ) ⊕ Ā ∈
/ L1 .
C A Stronger Attack
We subdivide the distinguisher execution into three phases: chain preparation, computation of
chain values, and consistency check, and its description is best represented by means of the following
tables: Note that if a value in the column Queries to S is named with the letter R (or X, Y, Z, A, S,
respectively), it is issued to F1 (or F2 , F3 , F4 , F5 , F6 , respectively).
Chain Preparation.
Step D computes Queries to S
1 X := X1 = X2 = X3 = X4 u.a.r.
2 R2 , R3 arbitrary s.t. R2 6= R3 R2 , R3
3 S2 ||T2 := P(X ⊕ F1 (R2 )||R2 ) S2
4 S3 ||T3 := P(X ⊕ F1 (R3 )||R3 ) S3
5 A2 := F6 (S2 ) ⊕ T2 , A3 := F6 (S3 ) ⊕ T3
6 R1 := R2 ⊕ A2 ⊕ A3 R1
7 S1 ||T1 := P(X ⊕ F1 (R1 )||R1 ) S1
8 A1 := F6 (S1 ) ⊕ T1
9 A5 := A1 ⊕ R1 ⊕ R2
10 R4 := R3 ⊕ A3 ⊕ A5 R4
11 S4 ||T4 := P(X ⊕ F1 (R4 )||R4 ) S4
12 A4 := F6 (S4 ) ⊕ T4
13 A8 := A4 ⊕ R4 ⊕ R3 A8
Computation of Chain Values.
Step D computes Queries to S
14 X
15 A1 , A2 , A3 , A4
16 Zi := F5 (Ai ) ⊕ Si for i = 1, 2, 3, 4 Z1 , Z2 , Z3 , Z4
17 Yi := F2 (X) ⊕ Ri for i = 1, 2, 3, 4 Y1 , Y2 , Y3 , Y4
18 Y6 := Y1 , Y5 := Y2 , Y8 := Y3 , Y7 := Y4
19 Z5 := Z1 , Z6 := Z2 , Z7 := Z3 , Z8 := Z4
20 A6 := F4 (Z6 ) ⊕ Y6 A6
21 X5 := F3 (Y5 ) ⊕ Z5 , X6 := F3 (Y6 ) ⊕ Z6 X5 , X6
22 R5 := F2 (X5 ) ⊕ Y5 , R6 := F2 (X6 ) ⊕ Y6 R5 , R6
23 S5 ||T5 := P(X5 ⊕ F1 (R5 )||R5 ) S5
24 S6 ||T6 := P(X6 ⊕ F1 (R6 )||R6 ) S6
25 A5
26 X7 := F3 (Y7 ) ⊕ Z7 , X8 := F3 (Y8 ) ⊕ Z8 X7 , X8
27 R7 := F2 (X7 ) ⊕ Y7 , R8 := F2 (X8 ) ⊕ Y8 R7 , R8
28 S7 ||T7 := P(X7 ⊕ F1 (R7 )||R7 ) S7
29 S8 ||T8 := P(X8 ⊕ F1 (R8 )||R8 ) S8
30 A7 := F4 (Z7 ) ⊕ Y7 A7
52
Consistency Check. Check if the following equations hold:
(i) Chain Equalities: for i = 1, 2, . . . , 8 we have:

F1 (Ri ) = Si ⊕ Xi , F2 (Xi ) = Ri ⊕ Yi , F3 (Yi ) = Xi ⊕ Zi ,
F4 (Zi ) = Yi ⊕ Ai , F5 (Ai ) = Zi ⊕ Si , F6 (Si ) = Ai ⊕ Ti
(ii) Equalities: X5 = X6 , X7 = X8 , A7 = A5 , A6 = A3
If all the above equalities hold, output 1, else output 0.
Intuition behind the attack Figure 8 provides a picture of the dependencies between chains
that have to be defined consistently by the simulator. The intuition behind this attack is as follows:
Figure 8: Illustration of the more general attack.
It seems that any simulator that completes chains one after another does not succeed: no matter in
which order it completes the chains, it seems to always end up in a situation where some remaining
chain cannot be completed consistently.
53

The Equivalence of The Random Oracle Model and The Ideal Cipher Model, Revisited

Uploaded by

Copyright:

Available Formats

The Equivalence of The Random Oracle Model and The Ideal Cipher Model, Revisited

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

The Equivalence of The Random Oracle Model and The Ideal Cipher Model, Revisited

Uploaded by

Copyright:

Available Formats

The Equivalence of the Random Oracle Model

and the Ideal Cipher Model, Revisited

October 22, 2018

2 The Six-Round Feistel Construction: An Attack 7

3 Indifferentiability of the Feistel Construction from a Random Permutation 11

A Detailed Definition of the Simulator of Coron et al. 39

B Detailed Analysis of the Attack against the Simulator of Coron et al. 45

Li+1 := Ri , Ri+1 := Li ⊕ Fi+1 (Ri ),

1.2 The Random Oracle and Ideal Cipher Models: Indifferentiability

(2) Conversely, is there C2 such that CR

1.3 Our Contributions

1.4 Sketch of the Previous Problems and the New Proof

1.5 Model and Notational Conventions

2 The Six-Round Feistel Construction: An Attack

2.1 The Simulator of Coron et al.

(ii) If i = 6, x ∈ F5 , y ∈ F6 , z ∈ F1 , and ∃x0 ∈ {0, 1}n : P−1 (ykF6 (y) ⊕ x) = x0 kz;

(iii) If i = 1, x ∈ F6 , y ∈ F1 , z ∈ F2 , and ∃x7 ∈ {0, 1}n : P(z ⊕ F1 (y)ky) = xkx7 .

2.2 A problem in the Proof of [CPS08c]

2.3 The Attack against the Simulator of [CPS08c]

Finally, note that

3 Indifferentiability of the Feistel Construction from a Random

3.1 Simulator Definition

3.1.1 Informal description

3.1.2 The simulator in pseudocode

29 private procedure ForceVal(x, y, `)

53 private procedure Check(x0 , x1 , x14 , x15 )

65 private procedure EvaluateBackward(xk , xk+1 , k, `):

3.2 Proof of Indifferentiability

3.2.1 Replacing the permutation with a random function

Two-sided random function: We replace the random permutation P by a two-sided random

5 public procedure P(x0 , x1 )

12 public procedure P−1 (x14 , x15 )

19 public procedure Check(x0 , x1 , x14 , x15 )

3.2.2 Introducing a Feistel-construction

7 private procedure F(i, xi ):

12 public procedure P(x0 , x1 )

19 public procedure P−1 (x14 , x15 )

26 public procedure Check(x0 , x1 , x14 , x15 )

3.2.3 Removing the simulator

2 · 107 · q 16 8 · 1019 · q 10 1022 · q 16

3.3 Equivalence of the First and the Second Experiment

Experiment E0 : D interacts with P0 (p), which is defined as follows: The procedures

We will show that

Lemma 3.2 then follows immediately, as

≤ Pr[(BadCheck ∨ BadOverwrite ∨ BadBackwardQuery)]

3.4 Complexity of the Simulator

3.5 Equivalence of the Second and the Third Experiment

3.5.1 Partial chains

11 procedure prev(xk , xk+1 , k):

33 procedure vali (C)

Equivalent partial chains We use the concept of equivalent partial chains:

3.5.2 Bad events and good executions

• (↑, x14 , x15 ) ∈ P ,

• After an assignment Gk (xk ) := f (k, xk ) there is a table-defined chain (xk−1 , xk , k − 1) such

Definition 3.14. Let G and P be a set of tables, let xk ∈

• Before the assignment, C and D are not equivalent.

• Before the assignment, valσ` (C) = ⊥ or valρ` (D) = ⊥.

• After the assignment, valσ` (C) = valρ` (D) 6= ⊥.

3.5.3 Bad events are unlikely

Query to Chain Sets