<<

. 4
( 19)



>>

assumption holds, namely the existence of a one-way permutation with expo-
nential security.
Definition 27 (Very strong one-way permutation).7 A family of polyno-
mial time computable functions is a very strong one-way
permutation if there exists a constant such that for every algorithm A
with running time at most the inverting probability
is at most for all but finitely many

Proving that no such functions exist would be a breakthrough in complexity
theory. Furthermore, Gennaro and Trevisan show in [GT00] that in relativized
worlds such functions exist, and thus our results exclude a relativizing hard-
core result for any bilinear function which does not satisfy the conditions of
Corollary 26 unconditionally.
As a first step, we show that it is impossible to use a bilinear function to
extract hard bits from Such a lemma was already hinted at in [GL89].
Lemma 28. Let be a regular bilinear function
with If a very strong one-way permutation exists, then is not a
strong hard-core function.
7
We use permutations for the sake of simplicity. It is easy to see that arbitrary one-way
functions with exponential security suffice to prove Theorem 30.

TEAM LinG
90 Thomas Holenstein, Ueli Maurer, and Johan Sjödin

Proof. Since and is regular, there exists a polynomial-time com-
putable function with for infinitely many
We define a one-way function for which it is easy to
give a distinguisher for For this purpose, let be
a very strong one-way permutation. On input split the input into
two parts, and The output of is then
concatenated with We see that is a one-way function, since an algorithm A
which inverts in with non-negligible success probability can be
used to invert in time with probability for infinitely many
Furthermore, for any with it is easy to distinguish
from a random string, given and First, we find from Since
we see that for fixed and only a subspace of dimension at
most is possible as output value for Also, it is easy to check whether
a given value is within this subspace or not. Since a random value will be in the
subspace with probability at most cannot be a hard-core function.
Using basically the same technique, we can now show that only functions
with nearly full rank can be used as hard-core functions.
Lemma 29. Let be a regular bilinear function
with and If a very strong one-way permutation
exists, then is not a strong hard-core function.
Proof. Since is regular and there exists a function such that
and for infinitely many
As in the proof of Lemma 28, we construct a one-way function
by embedding a preimage of size to a very strong one-
way permutation Consider an for which For such an it
is easy to find a linear map to embed the preimage to such that for some
the value of does not depend on the input to As in the
proof of Lemma 28 it follows immediately that is a one-way function, and
since only depends on a part of which can be found by a linear
transformation of the output, cannot be a hard-core function.
Together, this implies the following theorem.
Theorem 30. Let be a regular bilinear function,
and assume the existence of a very strong one-way permutation. Then is a
strong hard-core function if and only if and
Proof. If and then is a hard-core function
according to Corollary 26. If and then is not
a hard-core function according to Lemma 29. If then is not a
hard-core function according to Lemma 28.

Acknowledgments
We would like to thank Gustav Hast and Johan Håstad for helpful discussions.
This research was supported by the Swiss National Science Foundation, project
no. 2000-066716.01/1.
TEAM LinG
Complete Classification of Bilinear Hard-Core Functions 91

References
[ACGS88] Werner Alexi, Benny Chor, Oded Golreich, and Claus P. Schnorr. RSA
and Rabin functions: Certain parts are as hard as the whole. Siam Journal
on Computation, 17(2): 194“209, 1988.
[AGS03] Adi Akavia, Shafi Goldwasser, and Samuel Safra. Proving hard-core pred-
icates using list decoding. In The 44th Annual Symposium on Foundations
of Computer Science, pages 146“157, 2003.
Manuel Blum and Silvio Micali. How to generate cryptographically
[BM84]
strong sequences of pseudo-random bits. Siam Journal on Computation,
13(4):850“864, 1984.
[GL89] Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way
functions. In Proceedings of the Twenty First Annual ACM Symposium on
Theory of Computing, pages 25“32, 1989.
Oded Goldreich. Basic Tools. Foundations of Cryptography. Cambridge
[Gol01]
University Press, first edition, 2001. ISBN 0-521-79172-3.
[GRS00] Oded Goldreich, Ronitt Rubinfeld, and Madhu Sudan. Learning polyno-
mials with queries: The highly noisy case. Siam Journal on Discrete Math-
ematics, 13(4):535“570, 2000.
[GT00] Rosario Gennaro and Luca Trevisan. Lower bounds on the efficiency of
generic cryptographic constructions. In The 41st Annual Symposium on
Foundations of Computer Science, pages 305“313, 2000.
[Has03] Gustav Hast. Nearly one-sided tests and the Goldreich-Levin predicate. In
Eli Biham, editor, Advances in Cryptology ” EUROCRYPT 2003, volume
2656 of Lecture Notes in Computer Science, pages 195“210, 2003. Extended
version to appear in Journal of Cryptology.
[HILL99] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby.
A pseudorandom generator from any one-way function. Siam Journal on
Computation, 28(4): 1364“1396, 1999.
[Lev87] Leonid A. Levin. One-way functions and pseudorandom generators. Com-
binatorica, 7(4):357“363, 1987.
[Lub96] Michael Luby. Pseudorandomness and Cryptographic Applications. Prince-
ton University Press, first edition, 1996. ISBN 0-691-02546-0.
[N¤s95] Mats N¤slund. Universal hash functions & hard core bits. In Louis C. Guil-
lou and Jean-Jacques Quisquater, editors, Advances in Cryptology ” EU-
ROCRYPT ™95, volume 921 of Lecture Notes in Computer Science, pages
356“366, 1995.
[N¤s96] Mats N¤slund. All bits in are hard. In Neal Koblitz, editor,
Advances in Cryptology ” CRYPTO ™96, volume 1109 of Lecture Notes in
Computer Science, pages 114“128, 1996. Extended Abstract.
[STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom genera-
tors without the XOR lemma. Journal of Computer and System Sciences,
62(2):236“266, 2001.
[Sud00] Madhu Sudan. List decoding: Algorithms and applications. SIGACTN:
SIGACT News (ACM Special Interest Group on Automata and Computabil-
ity Theory), 31(1):16“27, 2000.
[Yao82] Andrew C. Yao. Theory and applications of trapdoor functions (extended
abstract). In The 23rd Annual Symposium on Foundations of Computer
Science, pages 80“91, 1982.


TEAM LinG
Finding Collisions on a Public Road,
or Do Secure Hash Functions Need Secret Coins?

Chun-Yuan Hsiao and Leonid Reyzin
Boston University Computer Science
111 Cummington Street
Boston MA 02215 USA
{cyhsiao,reyzin}@cs.bu.edu




Abstract. Many cryptographic primitives begin with parameter gener-
ation, which picks a primitive from a family. Such generation can use pub-
lic coins (e.g., in the discrete-logarithm-based case) or secret coins (e.g.,
in the factoring-based case). We study the relationship between public-
coin and secret-coin collision-resistant hash function families (CRHFs).
Specifically, we demonstrate that:
there is a lack of attention to the distinction between secret-coin
and public-coin definitions in the literature, which has led to some
problems in the case of CRHFs;
in some cases, public-coin CRHFs can be built out of secret-coin
CRHFs;
the distinction between the two notions is meaningful, because in
general secret-coin CRHFs are unlikely to imply public-coin CRHFs.
The last statement above is our main result, which states that there is no
black-box reduction from public-coin CRHFs to secret-coin CRHFs. Our
proof for this result, while employing oracle separations, uses a novel ap-
proach, which demonstrates that there is no black-box reduction without
demonstrating that there is no relativizing reduction.


1 Introduction
1.1 Background
Collision-Resistant Hashing. Collision-resistant (CR) hashing is one of the
earliest primitives of modern cryptography, finding its first uses in digital signa-
tures [Rab78,Rab79] and Merkle trees [Mer82,Mer89]. A hash function, of course,
maps (potentially long) inputs to short outputs. Informally, a hash function is
collision-resistant if it is infeasible to find two inputs that map to the same
output.
It is easy to see there is no meaningful way to formalize the notion of collision-
resistance for a single fixed-output-length hash function. Indeed, at least half of
the possible 161-bit inputs to SHA-1 [NIS95] have collisions (because SHA-1
has 160-bit outputs). Hence, an algorithm finding collisions for SHA-1 is quite
simple: it just has, hardwired in it, two 161-bit strings that collide. It exists,
even if no one currently knows how to write it down.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 92“105, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
Finding Collisions on a Public Road 93

Due to this simple observation, formal definitions of collision-resistant hash-
ing (first given by Damgård [Dam87]) usually speak of collision-resistant function
families (CRHFs)1. A hash function family is collision-resistant if any adversary,
given a function chosen randomly from the family, is unable to output a collision
for it.

How to Choose from a Family? Most definitions of CRHFs do not dwell on
the issue of how a hash function is to be chosen from a family. In this paper, we
point out that this aspect of the definition is crucial. Indeed, in any application
of collision-resistant hashing, some party P must choose a function from the
family by flipping some random coins to produce the function description. As
we demonstrate, it is important to distinguish between two cases. In the public-
coin case these random coins can be revealed as part of the function description.
In the secret-coin case, on the other hand, knowledge of the random coins may
allow one to find collisions, and thus P must keep the coins secret after the
description is produced. (For examples of both cases, see Section 2.) We note
that the original definition of [Dam87] is secret-coin, and that the secret-coin
definition is more general: clearly, a public-coin CRHF will also work if one
chooses to keep the coins secret.

1.2 Initial Observations
Importance of the Distinction. The distinction between public-coin and
secret-coin CRHFs is commonly overlooked. Some works modify the secret-coin
definition of [Dam87] to a public-coin definition, without explicitly mentioning
the change (e.g., [BR97,Sim98]). Some definitions (e.g., [Mir01]) are ambiguous
on this point. This state of affairs leads to confusion and potential problems, as
discussed in three examples below.
Example 1. Some applications use the wrong definition of CRHF. For in-
stance, in Zero-Knowledge Sets of Micali, Rabin and Kilian [MRK03], the
prover uses a hash function to commit to a set. The hash function is chosen
via a shared random string, which is necessary because the prover cannot be
trusted to choose his own hash function (since a dishonest prover could ben-
efit from finding collisions), and interaction with the verifier is not allowed at
the commit stage (indeed, the prover does not yet know who the verifier(s)
will be). In such a setting, one cannot use secret-coin CRHFs (however, in
an apparent oversight, [MRK03] defines only secret-coin CRHFs). A clear
distinction between public-coin and secret-coin CRHFs would make it easier
to precisely state the assumptions needed in such protocols.
Example 2. The result of Simon [Sim98] seems to claim less than the proof
implies. Namely, the [Sim98] theorem that one-way permutations are unlikely
to imply CRHFs is stated only for public-coin CRHFs, because that is the
1
It is possible to define a single hash function (with variable output-length; cf. previous
paragraph) instead of a collection of them. In this case, it can be collision-resistant
only against a uniform adversary.

TEAM LinG
94 Chun-Yuan Hsiao and Leonid Reyzin

definition [Sim98] uses. It appears to hold also for secret-coin CRHFs, but
this requires re-examining the proof. Such re-examination could be avoided
had the definitional confusion been resolved.
Example 3. The original result of Goldwasser and Kalai [GK03] on the
security of the Fiat-Shamir transform without random oracles has a gap
due to the different notions of CRHF (the gap was subsequently closed,
see below). Essentially, the work first shows that if no secret-coin CRHFs
exist, then the Fiat-Shamir transform can never work. It then proceeds to
show, in a sophisticated argument, that if public-coin CRHFs exist, then it
is possible to construct a secure identification scheme for which the Fiat-
Shamir transform always results in an insecure signature scheme. This gap
in the result would be more apparent with proper definitions.
Let us elaborate on the third example, as it was the motivating example for our
work. It is not obvious how to modify the [GK03] proof to cover the case when
secret-coin CRHFs exist, but public-coin ones do not. Very recently, Goldwasser
and Kalai [GK] closed this gap by modifying the identification scheme of the
second case to show that the Fiat-Shamir transform is insecure if secret-coin
(rather than public-coin) CRHFs exist. Briefly, the modification is to let the
honest prover choose the hash function during key generation (instead of the
public-coin Fiat-Shamir verifier choosing it during the interaction, as in the
earlier version).
Despite the quick resolution of this particular gap, it and other examples
above demonstrate the importance of distinguishing between the two types of
collision-resistant hashing. Of course, it is conceivable that the two types are
equivalent, and the distinction between them is without a difference. We there-
fore set out to discover whether the distinction between public-coin and secret-
coin hashing is real, i.e., whether it is possible that public-coin CRHFs do not
exist, but secret-coin CRHFs do.

1.3 Our Results
Recall that public-coin hashing trivially implies secret-coin hashing. We prove
the following results:
1. Dense2 secret-coin CRHFs imply public-coin CRHFs; but
2. There is no black-box reduction from secret-coin CRHFs to public-coin
CRHFs.
The first result is quite simple. The second, which is more involved, is obtained by
constructing oracles that separate secret-coin CRHFs from public-coin CRHFs.
Our technique for this oracle separation is different from previous separations
(such as as explained below. We note
that our second result, as most oracle separations, applies only to uniform ad-
versaries (a notable exception to this is [GT00]).
2
A CRHF is dense if a noticeable subset of all keys of a particular length is secure;
see Section 3.

TEAM LinG
Finding Collisions on a Public Road 95

Our results suggest that a gap between secret-coin and public-coin CRHFs
exists, but only if no dense secret-coin CRHFs exist. They highlight the impor-
tance of distinguishing between the two definitions of CRHFs.
In addition to these main results, Section 5 addresses secret vs. public coins
in other cryptographic primitives.

1.4 On Oracle Separations
Usually when one constructs a cryptographic primitive P (e.g., a pseudorandom
generator [BM84]) out of another cryptographic primitive Q (e.g., a one-way
permutation), P uses Q as a subroutine, oblivious to how Q implemented. The
security proof for P usually constructs an adversary for Q using any adversary
for P as a subroutine. This is known as a “black-box reduction from P to Q.”
Note that to show that no general reduction from P to Q exists requires
proving that Q does not exist, which is impossible given the current state of
knowledge. However, it is often possible to show that no black-box reduction
from P to Q exists; this is important because most cryptographic reductions are
black-box.
The first such statement in cryptography is due to Impagliazzo and
Rudich [IR89]. Specifically, they constructed an oracle relative to which key
agreement does not exist, but one-way permutations do. This means that any
construction of key agreement from one-way permutations does not relativize
(i.e., does not hold relative to an oracle). Hence no black-box reduction from key
agreement to one-way permutations is possible, because black-box reductions
relativize.
The result of [IR89] was followed by other results about “no black-box
reduction from P to Q exists,” for a variety of primitives P and Q (e.g.,
Most of them, except [GMR01], actually
proved the slightly stronger statement that no relativizing reduction from P
to Q exists, by using the technique of constructing an oracle.
Our proof differs from most others in that it directly proves that no black-box
reduction exists, without proving that no relativizing reduction exists. We do so
by constructing different oracles for the construction of P from Q and for the
security reduction from adversary for P to adversary for Q. This proof technique
seems more powerful than the one restricted to a single oracle, although it proves
a slightly weaker result. The weaker result is still interesting, however, because it
still rules out the most common method of cryptographic reduction. Moreover,
the stronger proof technique may yield separations that have not been achievable
before.
We note that [GMR01] also directly prove that no black-box reduction exists,
without proving that no relativizing reduction exists. Our approach is different
from [GMR01], whose approach is to show that for every reduction, there is an
oracle relative to which this reduction fails.
For a detailed discussion on black-box reductions, see [RTV04]. All reductions
in this paper are what they refer to as fully black-box reductions.

TEAM LinG
96 Chun-Yuan Hsiao and Leonid Reyzin

2 Definitions of Public-Coin and Secret-Coin CRHFs
Examples. Before we define public-coin and secret-coin hashing formally, con-
sider the following two example hash function families. The first one, keyed by
a prime with a large prime and two elements of order
computes where and are two halves of (here we
3
think of as an element of . The second one, keyed by a product of
two primes and and a value computes
4
.
The first hash function family is secure as long as discrete logarithm is hard.
Thus, if one publishes the random coins used to generate and the hash
function remain secure (as long as the generation algorithm doesn™t do anything
esoteric, such as computing as a random power of On the other hand, the
second hash function family is secure based on factoring, and is entirely insecure
if the factors of are known. Thus, publishing the random coins used to generate
and renders the hash function insecure, and the coins must be kept secret5.

Definitions. We say that a function is negligible if it vanishes faster than any
inverse polynomial. We let PPTM stand for a probabilistic polynomial-time Tur-
ing machine. We use to denote an oracle Turing machine, and to denote
M instantiated with oracle A.
Let be the security parameter, and let be a (length) function that does
not expand or shrink its input more than a polynomial amount. Below we de-
fine two kinds of CRHFs: namely, secret-coin and public-coin. The secret-coin
CRHFs definition is originally due to Damgård [Dam87], and the definition here
is adapted from [Rus95].
Definition 1. A Secret-Coin Collision Resistant Hash Family is a collection
of functions for some index set where
and
1. There exists a PPTM GEN, called the generating algorithm, so that

2. There exists a PPTM EVA, called the function evaluation algorithm, so that
and
3. For all PPTM ADV, the probability that outputs a pair such
that is negligible in where the probability is taken over the
random choices of GEN in generating and the random choices of ADV.
3
This family is derived from Pedersen commitments [Ped91].
4
This is essentially the construction of [Dam87] based on the claw-free permutations
of [GMR88].
5
It should be noted, of course, whether it is secure to publish the coins depends not
only on the family, but also on the key generating algorithm itself: indeed, the first
family can be made insecure if the coins are used to generate as a power of
rather than pick directly. Likewise, the second family could be made secure if it
were possible to generate “directly,” without revealing and (we are not aware
of an algorithm to do so, however).

TEAM LinG
Finding Collisions on a Public Road 97

Definition 2. A Public-Coin Collision Resistant Hash Family is a collection of
functions where and

1. A PPTM GEN on input outputs a uniformly distributed string of length

2. There exists a PPTM EVA, called the function evaluation algorithm, so that
and
3. For all PPTM ADV, the probability that outputs a pair such
that is negligible in where the probability is taken over the
random choices of GEN in generating and the random choices of ADV.

A pair such that is called a collision for

Remarks. The generating algorithm in the public-coin case is trivially satisfied.
We keep it here for comparison with the secret-coin case. Note that in both
GEN outputs a function that maps
cases, on security parameter
to This may seem restrictive as the hash functions only compress one
bit. However, it is easy to see that can be extended to for any and
remain collision-resistant with outputs, by the following construction:
where
denotes the bit of the input string


3 Dense Secret-Coin CRHFs Imply Public-Coin CRHFs

The notion of dense public-key cryptosystems was introduced by De Santis and
Persiano in [DP92]. By “dense” they mean that a uniformly distributed string,
with some noticeable probability, is a secure public key. We adapt the notion of
denseness in public-key cryptosystems from [DP92] to the context of CRHFs.
Informally, a secret-coin CRHF is a secret-coin CRHF with the following
additional property: if we pick a string at random, then we have probability
of picking an index for a collision-resistant function6.
at least
Note that, for example, the factoring-based secret-coin CRHF from Section 2
is dense, because the proportion of integers that are products of two equal-
length primes is In fact, we are not aware of any natural examples of
secret-coin CRHFs that are not dense (artificial examples, however, are easy to
construct).
Given a secret-coin CRHF, if we pick strings of length at
random, then with high probability, at least one of them defines a collision-
resistant hash function.
Hence, we can build a public-coin CRHF from such dense secret-coin CRHF
as follows.
6
Confusingly, sometimes the term dense is used to denote a function family where
each function has a dense domain, e.g., [Hai04]. This is unrelated to our use of the
term.

TEAM LinG
98 Chun-Yuan Hsiao and Leonid Reyzin

1. Generate random strings, independently. These strings specify
hash functions in the secret-coin CRHF (strictly speak-
ing, some strings may not define functions at all, because they are not pro-
duced by GEN ; however, simply define if does not
produce an output of length in the requisite number of steps).
2. Through the construction described in Section 2, extend the domain of each
of these function to binary strings of length Let the resulting
functions be
3. On an input of length output concatenation of


The resulting hash maps binary strings of length to binary
strings of length and is collision-resistant because at least one of
is. (If an adversary could find a collision in the resulting hash
function, then the same collision would work for collision-resistant hash function
among immediately leading to a contradiction.)
The above discussion yields the following theorem.
Theorem 1. The existence of dense secret-coin CRHF implies the existence of
public-coin CRHF.


4 Separating Public-Coin CRHFs
from Secret-Coin CRHFs
4.1 Black-Box Reductions
Impagliazzo and Rudich [IR89] provided an informal definition of black-box re-
ductions, and Gertner et al. formalized it. We recall their formaliza-
tion.
Definition 3. A black-box reduction from primitive P to primitive Q consists
of two oracle PPTMs M and satisfying the following two conditions:
If Q can be implemented, so can P: (not necessarily PPTM) imple-
menting Q, implements P; and
If P is broken, so is Q: (not necessarily PPTM) breaking (as an
implementation of P), breaks N (as an implementation of Q).

The first condition is only a functional requirement; i.e., the term “implement”
says nothing about security, but merely says an algorithm satisfies the syntax of
the primitive.

4.2 The Main Result
Theorem 2. There is no black-box reduction from public-coin CRHF to secret-
coin CRHF.
TEAM LinG
Finding Collisions on a Public Road 99

Proof. The following proposition is at the heart of our approach: it shows that
it is sufficient to construct different oracles F and G, such that G is used in the
implementations, while F and G are used for the adversaries. This is in contrast
to the single-oracle approach usually taken to prove black-box separations.
Proposition 1. To show that there is no black-box reduction from public-coin
collision resistant hashing (P) to secret-coin collision resistant hashing (Q), it
suffices to construct two oracles F and G such that,
1. there is an oracle PPTM L such that implements secret-coin hash-
ing;
2. for all oracle PPTM M, if implements public-coin hashing, then there
exists a probabilistic polynomial time adversary A such that finds
a collision for
3. there is no oracle PPTM B such that finds a collision for N.
Proof. To show that there is no black-box reduction from public-coin collision
resistant hashing (P) to secret-coin collision resistant hashing (Q), we need to
negate the definition of black-box reduction from Section 2; i.e., we need to show
that for every oracle PPTMs M and
Q can be implemented: that implements Q, and if implements P,
then
P can be broken, without breaking Q: that breaks (as an imple-
mentation of P), while does not break N (as an implementation of
Q).
Recall that “implement” here has only functional meaning.
The first condition clearly implies that Q can be implemented. The second
condition also clearly implies that P can be broken: one simply observes that
and L is a PPTM; hence, writing is equivalent to writing
The third condition implies that P can be broken without breaking Q,
essentially because Q can never be broken. More precisely, the third condition
is actually stronger than what we need: all we need is that for each there is
that breaks while does not break N. Instead, we will show that
a single essentially works for all namely, for a fixed oracle
F and a polynomial-time A. Such breaks however, as condition 3 in
the proposition statement implies, will be unable to break N, because
for some oracle PPTM B.

Remarks. Note that if the implementation has access to not only G but also
F, it becomes the usual single-oracle separation. The reason why we do not give
the implementation access to F is to avoid “self-referencing” when defining F.
To see this, note that F is the “collision finder” and is defined according to the
oracles that the implementation has access to7.
7
Similar concern occurs in [Sim98], where constructing the collision-finder requires
more careful design.

TEAM LinG
100 Chun-Yuan Hsiao and Leonid Reyzin

The rest of this section is devoted to constructing such F and G and proving
that they work.

The Oracles F and G
4.3
In constructing F and G, we will use the Borel-Cantelli Lemma (see, e.g., [AG96]),
which states that if the sum of the probabilities of a sequence of events converges,
then the probability that infinitely many of these events happen is zero. Formally,
Lemma 1 (Borel-Cantelli Lemma). Let be a sequence of
events on the same probability space. Then implies

We first construct “random” F (collision-finder) and G (secret-coin hash),
and then use the above lemma to show that at least one pair of F and G works.
Intuitively, we want F to break any public-coin hashing but not break some
secret-coin hashing. More precisely, F will find a collision if it is supplied with
the coins of the generating algorithm and will refuse to do so without the coins.
G consists of two collections of functions and where
each is a random function from to We will call a binary
string valid if it is in the range of and invalid if not. Each is a random
function from to if is valid, and is a constant function
if is invalid. We will call queries to valid (resp. invalid) if is valid
(resp. invalid).
F takes a deterministic oracle machine and as input, and outputs a
collision of length for if satisfies the following conditions.
1. maps to
2. never queries for some not obtained by previously querying
I.e., whenever queries this is the answer to some that
has previously asked.
When both conditions hold, F picks a random from that has a
collision, then a random that collides to (i.e.,
Otherwise F outputs
and outputs
Observe that when F outputs not only but also is uniformly
distributed over all points that have a collision. Indeed, let C be the to-
tal number of points that have a collision, and suppose has colli-
sions then


Remarks. The reason for being length-doubling is to have a “sparse” function
family. More specifically, it should be hard to get a value in the range of without
applying it.
As in [Sim98], there are various ways of constructing F (the collision-finding
oracle): one can choose a random pair that collides, or a random then a ran-
dom (possibly equal to that collides to The second construction has the
advantage, in analysis, that both and are uniformly distributed but does
not always give a “correct” collision, like the first one does. Our F has both
properties.
TEAM LinG
Finding Collisions on a Public Road 101

Secret-Coin Collision-Resistant Hash Family Based on G
4.4
In this section we construct a secret-coin CRHF. The construction is straight-
forward given the oracle G: the generating algorithm uses and the hashing
uses More precisely, on input the generating algorithm picks a random
seed and outputs The hash function is Note that the
adversary A (who is trying to find a collision) is given only but not We will
show that for measure one of oracles F and G, the probability over and A™s
coin tosses that A finds a collision for is negligible. Recall that A has access
to both F and G.
Define D as the event that A outputs a collision for in the following
experiment:

And in the same experiment, define B as the event that during its computation,
A queries F on where is some deterministic oracle machine that queries
its oracle on a preimage of under (i.e., intuitively, has hardwired in it).
Suppose A™s running time is bounded by for some constant The probability
that B happens is at most the probability of inverting the random function
If has a unique preimage, this is at most the probability that has two
or more preimages is at most (because it™s the probability that collides
with another value under hence The probability that
D happens conditioned on is at most the probability of finding a collision
for random function which is bounded by Recall that A can be
randomized. We thus have




By the Markov inequality, Since
converges, the Borel-Cantelli lemma implies that for only measure zero
of F and G, can there be infinitely many for which event D happens with prob-
ability (over and A™s coins) greater than or equal to This implies
that for measure one of F and G, event D happens with probability (over and
A ™s coins) smaller than (a negligible function) for all large enough
There are only countably many adversaries A, so we have the following lemma.
Lemma 2. For measure one of F and G, there is a CRHF using G, which is
secure against adversaries using G and F.

No Public-Coin Collision-Resistant Hash Family Based on G
4.5
In this section we show that any implementation of public-coin hashing using
oracle G cannot be collision-resistant against adversaries with oracle access to
TEAM LinG
102 Chun-Yuan Hsiao and Leonid Reyzin

both F and G 8. More precisely, let be the public randomness used
by the generating algorithm for a family of hash functions, and let be the
evaluation algorithm. I.e., is the hash function specified by Assume
that maps to where is a function that
does not expand or shrink the input by more than a polynomial amount. We
will show how to find and of length such that
An immediate attempt is to query but notice that may
9
, which prevents F from finding a collision for us.
query for arbitrary
However, these are likely to be invalid, and hence oracle answers to these
queries are likely to be So we can construct a machine that behaves
“similar” to but only after getting from does it query And instead of
finding collision for we find collision for which can be done by simply
querying
Suppose the running time of is bounded by for some constant
Before simulating queries on all inputs of length smaller than or equal
to This takes steps. Now simulates step by step, except
already asked of G
for queries to If is the answer to one of the queries
(either before the beginning of the simulation or when simulating then
actually queries Else it returns as the answer to without querying

the probability, over random G, that
Now fix and For every
is at most the probability, over G, that queries for some valid of
10
length greater than without receiving it from . Consider the very first
time that makes such a “long” valid query. Let be the number of queries
to on inputs longer than and be the number of invalid queries
to prior to this point. Then the probability in question is upper bounded by
For every fixed G and call an “bad”
which is at most
if We have


Next, notice that there are at most half of that have no collisions, and F
would pick its answer uniformly, from those points that have a collision.
So for a fixed G, the probability over F that is bad is at most twice the
probability over random that is bad. Also recall that the
distribution of is the same as So for every


If none of is bad, this pair would be a collision not only for but also
for We have


8
In fact, only F is needed to find a collision.
9
In particular, those not obtained by previously querying
10
Recall that is length-doubling.

TEAM LinG
Finding Collisions on a Public Road 103

then


Since converges, the Borel-Cantelli lemma implies that for only
measure zero of F and G, can we have is not a collision of
In other words, for measure one of F and G,
for infinitely many
is a collision of for all large enough There are only
countably many oracle machines each of which can be collision resistant for
only measure zero of F and G. We conclude the following.

Lemma 3. For measure one of F and G, any implementation of public-coin
hash function families using G cannot be collision-resistant against adversaries
using F.

This concludes the proof of Theorem 2.


5 Public Coins vs. Secret Coins for Other Primitives

Perhaps the lack of attention in the literature to the distinction between secret-
and public-coin primitives is due, in part, to the fact that this distinction is often
not meaningful.
For example, for one-way function families, these two notions are equivalent,
because a secret-coin one-way function family implies a single one-way function
(which trivially implies a public-coin one-way function family). Indeed, take
the generating algorithm and evaluation algorithm and define
this is one-way because an adversary who can come up with
such that and can be directly used to
invert since
On the other hand, for trapdoor permutations (and public-key schemes),
the notion of public-coin generation is meaningless: indeed the trapdoor (or the
secret key) must be kept secret.
However, it seems that this distinction is interesting for some primitives in ad-
dition to collision-resistant hash functions. The relationships between public-coin
and secret-coin versions of one-way permutation families and claw-free permuta-
tion families are unknown11. In particular, claw-free permutations are related to
collision-resistant hashing [Dam87,Rus95], which suggests that the distinction
for claw-free permutations is related to the distinction for CRHFs.
Acknowledgments. We thank Yael Tauman Kalai for many helpful discus-
sions, and Ron Rivest for assistance with the history of hashing. Thanks also to
the anonymous referees for insightful comments. This work was funded in part
by the National Science Foundation under Grant No. CCR-0311485.
11
We believe that the same construction of F and G (up to slight modifications) sepa-
rates public-coin and secret-coin one-way permutation families.

TEAM LinG
Chun-Yuan Hsiao and Leonid Reyzin
104

References

[AG96] Malcolm Adams and Victor Guillemin. Measure Theory and Probability.
Springer Verlag, 1996.
[BM84] M. Blum and S. Micali. How to generate cryptographically strong se-
quences of pseudo-random bits. SIAM Journal on Computing, 13(4) :850“
863, November 1984.
[BR97] Mihir Bellare and Phillip Rogaway. Collision-resistant hashing: Towards
making uowhfs practical. In Burton S. Kaliski, Jr., editor, Advances in
Cryptology”CRYPTO ™97, volume 1294 of Lecture Notes in Computer
Science, pages 470“484. Springer-Verlag, 17“21 August 1997.
[CHL02] Yan-Cheng Chang, Chun-Yun Hsiao, and Chi-Jen Lu. On the imposibili-
ties of basing one-way permutations on central cryptographic primitives.
In Yuliang Zheng, editor, Advances in Cryptology”ASIACRYPT 2002,
volume 2501 of Lecture Notes in Computer Science, pages 110“124, Queen-
stown, New Zealand, 1“5 December 2002. Springer-Verlag.
[Dam87] Ivan Damgård. Collision-free hash functions and public-key signature
schemes. In David Chaum and Wyn L. Price, editors, Advances in
Cryptology”EUROCRYPT 87, volume 304 of Lecture Notes in Computer
Science. Springer-Verlag, 1988, 13“15 April 1987.
Alfredo De Santis and Giuseppe Persiano. Zero-knowledge proofs of knowl-
[DP92]
edge without interaction. In 33rd Annual Symposium on Foundations of
Computer Science, pages 427“436, Pittsburgh, Pennsylvania, 24“27 Octo-
ber 1992. IEEE.
[GK] Shafi Goldwasser and Yael Tauman Kalai. On the (in)security of the Fiat-
Shamir paradigm. Available From http://www.mit.edu/˜tauman/.
[GK03] Shafi Goldwasser and Yael Tauman Kalai. On the (in)security of the
Fiat-Shamir paradigm. In 44th Annual Symposium on Foundations of
Computer Science [IEE03].
Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, and Mahesh
Viswanathan. The relationship between public key encryption and obliv-
ious transfer. In 41st Annual Symposium on Foundations of Computer
Science [IEE00], pages 325“335.
[GMR88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature
scheme secure against adaptive chosen-message attacks. SIAM Journal on
Computing, 17(2):281“308, April 1988.
[GMR01] Yael Gertner, Tal Malkin, and Omer Reingold. On the impossibility of
basing trapdoor functions on trapdoor predicates. In 42nd Annual Sym-
posium on Foundations of Computer Science, Las Vegas, Nevada, October
2001.
[GT00] Rosario Gennaro and Luca Trevisan. Lower bounds on the efficiency of
generic cryptographic constructions. In 41st Annual Symposium on Foun-
dations of Computer Science [IEE00].
[Hai04] Iftach Haitner. Implementing oblivious transfer using collection of dense
trapdoor permutations. In Naor [Nao04], pages 394“409.
[IEE00] IEEE. 41st Annual Symposium on Foundations of Computer Science, Re-
dondo Beach, California, November 2000.
[IEE03] IEEE. 44th Annual Symposium on Foundations of Computer Science,
Cambridge, Massachusetts, October 2003.

TEAM LinG
Finding Collisions on a Public Road 105

[IR89] Russell Impagliazzo and Steven Rudich. Limits on the provable conse-
quences of one-way permutations. In Proceedings of the Twenty First An-
nual ACM Symposium on Theory of Computing, pages 44“61, May 1989.
[Mer82] Ralph C. Merkle. Secrecy, Authentication, and Public Key Systems. UMI
Research Press, 1982.
[Mer89] Ralph C. Merkle. A certified digital signature. In G. Brassard, editor,
Advances in Cryptology”CRYPTO ™89, volume 435 of Lecture Notes in
Computer Science, pages 218“238. Springer-Verlag, 1990, 20“24 August
1989.
[Mir01] Ilya Mironov. Hash functions: From merkle-damgård to shoup. In Joe
Kilian, editor, Advances in Cryptology”CRYPTO 2001, volume 2139 of
Lecture Notes in Computer Science, pages 166“181. Springer-Verlag, Au-
gust 2001.
[MRK03] Silvio Micali, Michael Rabin, and Joe Kilian. Zero-knowledge sets. In 44th
Annual Symposium on Foundations of Computer Science [IEE03], pages
80“91.
[Nao04] Moni Naor, editor. First Theory of Cryptography Conference, volume 2951
of Lecture Notes in Computer Science. Springer-Verlag, February 2004.
[NIS95] FIPS publication 180-1: Secure hash standard, April 1995. Available from
http://csrc.nist.gov/f ips/.
[Ped91] Torben Pryds Pedersen. Non-interactive and information-theoretic se-
cure verifiable secret sharing. In J. Feigenbaum, editor, Advances in
Cryptology”CRYPTO ™91, volume 576 of Lecture Notes in Computer Sci-
ence, pages 129“140. Springer-Verlag, 1992, 11“15 August 1991.
[Rab78] Michael O. Rabin. Digitalized signatures. In Richard A. Demillo, David P.
Dobkin, Anita K. Jones, and Richard J. Lipton, editors, Foundations of
Secure Computation, pages 155“168. Academic Press, 1978.
[Rab79] Michael O. Rabin. Digitalized signatures and public-key functions as
intractable as factorization. Technical Report MIT/LCS/TR-212, Mas-
sachusetts Institute of Technology, Cambridge, MA, January 1979.
[RTV04] Omer Reingold, Luca Trevisan, and Salil Vadhan. Notions of reducibility
between cryptographic primitives. In Naor [Nao04], pages 1“20.
[Rus95] A. Russell. Necessary and sufficient conditions for collision-free hashing.
Journal of Cryptology, 8(2):87“100, 1995.
[Sim98] Daniel R. Simon. Finding collisions on a one-way street: Can secure hash
functions be based on general assumptions. In Kaisa Nyberg, editor, Ad-
vances in Cryptology”EUROCRYPT 98, volume 1403 of Lecture Notes in
Computer Science. Springer-Verlag, May 31“June 4 1998.




TEAM LinG
Security of Random Feistel Schemes
with 5 or More Rounds

Jacques Patarin
Universit© de Versailles
45 avenue des Etats-Unis
78035 Versailles Cedex, France


Abstract. We study cryptographic attacks on random Feistel schemes.
We denote by the number of plaintext/ciphertext pairs, and by the
number of rounds. In their famous paper [3], M. Luby and C. Rackoff have
completely solved the cases m the schemes are secure against
all adaptive chosen plaintext attacks (CPA-2) when and against
all adaptive chosen plaintext and chosen ciphertext attacks (CPCA-2)
when (for this second result a proof is given in [9]).
In this paper we study the cases We will use the “coefficients
H technique” of proof to analyze known plaintext attacks (KPA), adap-
tive or non-adaptive chosen plaitext attacks (CPA-1 and CPA-2) and
adaptive or non-adaptive chosen plaitext and chosen ciphertext attacks
(CPCA-1 and CPCA-2). In the first part of this paper, we will show
that when the schemes are secure against all KPA when
against all CPA-2 when and against all CPCA-2 attacks when
This solves an open problem of [1], [14], and it improves the result
of [14] (where more rounds were needed and was obtained
instead of The number 5 of rounds is minimal since CPA-2
attacks on 4 rounds are known when (see [1], [10]). Further-
more, in all these cases we have always obtained an explicit majoration
for the distinguishing probability. In the second part of this paper, we
present some improved generic attacks. For rounds, we present a
KPA with and a non-adaptive chosen plaintext attack (CPA-
1) with For rounds we also show some improved attacks
against random Feistel generators (with more than one permutation to
analyze and computations).


1 Introduction
A “Luby - Rackoff construction with rounds”, which is also known as a “ran-
dom Feistel cipher” is a Feistel cipher in which the round functions
are independently chosen as truly random functions (see section 2 for precise
definitions).
Since the famous original paper [3] of M. Luby and C. Rackoff, these con-
structions have inspired a considerable amount of research. In [8] and [14] a
summary of existing works on this topic is given.
We will denote by the number of rounds and by the integer such that
the Feistel cipher is a permutation of In [3] it was proved

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 106“122, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 107

that when these Feistel ciphers are secure against all adaptative chosen
plaintext attacks (CPA-2) when the number of queries (i.e. plaintext/ciphertext
pairs obtained) is Moreover when they are secure against all
adaptative chosen plaintext and chosen ciphertext attacks (CPCA-2) when the
number of queries is (a proof of this second result is given in [9]).
These results are valid if the adversary has unbounded computing power as
long as he does only queries.
These results can be applied in two different ways: directly using truly
random functions (that requires significant storage), or in a hybrid
setting, in which instead of using truly random functions we use
pseudo-random functions. These two ways are both interesting for cryptography.
The first way gives “locally random permutations” where we have proofs of
security without any unproven hypothesis (but we need a lot of storage), and the
second way gives constructions for block encryption schemes where the security
can be relied on a pseudo-random number generator, or on any one-way function.
In this paper, we will study security when instead of
for the original paper of M. Luby and C. Rackoff. For this we must have
since for some CPA-2 attacks when exist (see [1], [10]).
Moreover the bound is the larger bound that we can get, since an
adversary with unlimited computing power can always distinguish a
random Feistel scheme from a random permutation with queries and
computations by simply guessing all the round functions (it is also
possible to do less computing with the same number of queries by using collisions,
see [13]).
The bound is called the ˜birthday bound™, i.e. it is about the square
root of the optimal bound against an adversary with unbounded computing
power. In [1] W. Aiello and R. Venkatesan have found a construction of locally
random functions (˜Benes™) where the optimal bound is obtained
instead of the birthday bound. However here the functions are not permutations.
Similarly, in [4], U. Maurer has found some other construction of locally random
functions (not permutations) where he can get as close as wanted to the optimal
bound (i.e. and for all he has a construction). In [8] the
security of unbalanced Feistel schemes is studied and a security proof in
is obtained, instead of but for much larger round functions (from bits
to bits, instead of bits to bits). This bound is basically again the birthday
bound for these functions.
In this paper we will show that 5-round random Feistel schemes resist all
CPA-2 attacks when and that 6-round random Feistel schemes resist all
CPCA-2 attacks when Here we are very near the optimal bound, and we
have permutations. This solves an open problem of [1], [10]. It also significantly
improves the results of [6] in which the security is only obtained when the
number of rounds tends to infinity, and the result of [14] where security
was proved for CPA-2 after 7 rounds (instead of 5 here) and for CPCA-2 after 10
rounds (instead of 6 here). Moreover we will obtain in this paper some explicit
and simple majorations for the distinguishing probabilities. We will also present
some improved generic attacks. All these results are summarized in appendix A.
TEAM LinG
108 Jacques Patarin

2 Notations
General notations
denotes the set of the binary strings of length
The set of all functions from to is Thus
For any denotes the usual composition of functions.
For any will be the string of length of which is the
concatenation of and
For stands for bit by bit exclusive or of and
Let be a function of Let L, R, S and T be four n-bit strings in
Then by definition


Let be functions of Then by definition:


The permutation is called a ˜Feistel scheme with rounds™
or shortly When are randomly and independently chosen in
then is called a ˜random Feistel scheme with rounds™ or a ˜Luby-
Rackoff construction with rounds™.

We will first study 4 rounds (with some limitations on the inputs/outputs),
then prove our cryptographic results by adding one or two rounds.

Notations for 4 rounds
We will denote by the cleartexts. These cleartexts
can be assumed to be pairwise distinct, i.e. or
We call “index” any integer between 1 and
is the output after one round, i.e.


is the output after two rounds, i.e.


is the output after three rounds, i.e.


is the output after 4 rounds, i.e.



Notations for 5 rounds. We keep the same notations for Now
and is still the output: and


TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 109

Part I: Security Results

3 The General Proof Strategy
We will first study the properties of 4-round schemes. Our result on 4-round
schemes for proving KPA security will be:

Theorem 3.1 (4 rounds) For random values
such that the are pairwise distinct, with probability
we have:
1. the number H of such that



satisfies:


2. and can be chosen when

For 5 rounds, we will have:

Theorem 3.2 (5 rounds) There are some values and and there
is a subset such that:
1. for all pairwise distinct and for all sequences
of E the number H of such that


satisfies:


2. and and can be chosen when


Remark
1. Here the set E does not depend on the and it will give security
against CPA-2. If E depends on the we will obtain security against
CPA-1 only.
2. Instead of fixing a set E, as in theorem 3.2, we can formulate a similar
theorem in term of expectancy of the deviation of H from the average value
(see[15]: there is a formulation for CPA-1 and another for CPA-2). From
these formulas we will get security when
For 6 rounds, we will have:
TEAM LinG
110 Jacques Patarin

Theorem 3.3 (6 rounds) There are some values and and there
is a subset such that:
1. for all of E, the number H of
such that



satisfies:


2. For all super distinguishing circuit with oracle gates, the probability that
be in E is when acts on a random
permutation of (here denotes the
successive or that will
appear).
3. and can be chosen when

Now from these theorems and from the general “coefficients H technique”
theorems given in [11], [12], we will get immediately that when is
secure against all KPA, against all CPA-2 and against all CPCA-2.

4 Circles
One of the terms of the the deviation of from random permutations will be
the probability to get “circles” in the variables, as we will explain below.

Definition. We will say that we have ˜a circle in R, X, Y™ if there are indices
with and such that:
1. are pairwise distinct and
we have at least one of the three following conditions:
2.

or
or

Example. If and then we have a circle in R, X, Y. If
then we have a circle in R, X, Y.

We will prove the following theorems.
Theorem 4.1 (For 4 rounds) When are pairwise distinct
and randomly chosen, the probability to obtain a circle in R, X ,Y with at least
one equation in Y when are randomly chosen in satisfies:




TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 111

Theorem 4.2 (For 5 rounds) For all pairwise distinct
and for all value such that and we have: the probability
to obtain a circle in X, Y, Z with at least one equation when
are randomly chosen in satisfies:




Corollary 4.1 From this theorem 4.2 we get immediately that if then
can be chosen such that), is very small. So when the probability
to have a circle in X, Y, Z with at least one equation is negligible.

Remark. In [15] we show that the condition ˜with at least one equation
is important: sometime we cannot avoid some circles in X, Y.
With 6 rounds, we can get a simpler formula:

Theorem 4.3 (For 6 rounds) For all (such that
or the probability to obtain a circle in X, Y, Z with at
least one equation in Z when are randomly chosen in satisfies:




Proof of theorem 4.1, 4.2, 4.3 are given in the extended version of this paper
([15]). A basic tool for these proofs is:

Theorem 4.4 for all pairwise distinct when
is randomly chosen in we have a probability that the number N of
satisfies:




Proof. This result comes immediately from this lemma:

Lemma 4.1 For all (such that
the number of such that is

Proof of lemma 4.1. means This implies
(because and Thus, when is fixed,
the number of such that is exactly if and exactly 0 if
Therefore, since we have at most values
the total number of such that is as claimed.
TEAM LinG
112 Jacques Patarin

5 Properties of H with 4 Rounds
We give here the main ideas. See the extended version of this paper for more
details ([15]). We will first prove that if the are given, (i.e. the
output after 3 rounds), then the variables will look random as long as
(but the variables will not look random in general). Then, with one more
round and the same argument, we will obtain that the variables will look
random as long as We want to evaluate the number H of such
that: with (1).

Remarks
1. If with then So the variables are not perfectly
random in when the are given. However, here we just say that the
must be pairwise distinct, since is a permutation.
2. If is a constant for example), then all the
variables must be pairwise distinct, and in (1) is then fixed on exactly
points. However the probability for to be such that all the are
pairwise distinct is very small. So in this case
3. Let us consider that instead of (1) we had to evaluate the number J of
such that with
(i.e. here we do not have the term Then, for random
and for random we will have about 2 times more collisions
compared with a random variable So if is random, in this
case. For (1) we will prove (among other results) that, unlike here for J,
when the are random, we always have

Analysis of (1). (In appendix B an example is given on what we do here) We
will consider that all the are given (as well as the and we want
to study how H can depend on the values If H has almost always the same
value for all the then (by summation on all the we will get and
for all the will look random, as wanted, when are randomly
chosen in (this is an indirect way to evaluate H).
In (1), when we have a new value whatever is, is exactly fixed
on this point by (1). However if is not a new value, we have
For each equation we will introduce
a value We want to evaluate the number of such
that:
We will fix the points where i.e. we look for solutions
such that exactly on these and, again, we want to evaluate how
the number of can depend on the values (i.e. on the values
We will group the equations (2) by the same i.e. by “blocks in
R, X, Y”: two indices and are in the same block if we can go from to
by equations or or (Since
and from these
relations, we can replace the variable by the variable instead).
TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 113

Finally, the only dependencies on the come when we want to evaluate the
number of such that: are pairwise distinct, where
is the number of that we want pairwise distinct (if wanted we can assume
since variables with no equation in R, X or Y create no problem).
Each has an expression like this: (where is an
expression in of some values), or like this: This gives a
number of solutions for that depends only of the fact that some equations of
degree one in the variables are satisfied or not.
(These equations are where are in the same block
in R, X, Y and are in the same block in R, X, Y, so these equations can be
written only the and variables).

Example. In the example given in appendix B, is one
of these equations, that can be true or not when the values are fixed (here it
comes from

Analysis of the dependencies in the First, we can notice that if the system has
no solution due to an incompatibility (for example if we want
and to be distinct) then we have a circle in R, X, Y with at
least one equation in Y. The probability to get such circles has been evaluated
in section 4 and is negligible if . So we will assume that we have no
incompatibility in the system that says that the variables considered are
pairwise distinct. Let be the number of variables that satisfied at least one
of these equations among the equations considered for the evaluation of
Each of the special values can have at most exceptional relations.
So for a like this, we have: The value can
be but since we have exceptional relations of degree one on variables
the weight of these values (i.e. the number of that give these
values multiplied by the number of these values) satisfies:




(since we have possible equations). We have:




So the weight becomes negligible as soon as

Remark. If these variables generate almost all the possible relations with
these variables, then the weight of these variables is even smaller since we just
have to choose these variables among the variables and then they are fixed
(since almost all the equations are satisfied, many of these equations give equiv-
alent values for the special So we will have a instead of

TEAM LinG
114 Jacques Patarin

Finally we have obtain:

Theorem 5.1 Let be the set of values that we fix: i.e. in we have the values
of the and all the indices where we have all the equations Then
if S and are two sequences of values of such that:
1. (and
2. No circle in R, X, Y can be created from the equalities
and
Then the number of solutions satisfies:



where comes from the with very few special equalities, and is a
very small term related to the weight of the with a lot of special equalities (as
we have seen is negligible when

We can do the same for as we did for So, since by summation,
we must obtain all the with no circles, from theorem 5.1 we will
get our results. Here the set depends on E, so this works for non-adaptive
attacks. For adaptive attacks see [15] (then we have to eliminate some equations
by conditions in independently of or to study the expectancy of
the deviation of H).

Remark. Another possibility is to use the result of [5]: with 2 times more rounds,
security in CPA-1 can be changed in security in CPCA-2. However we would get
like this CPCA-2 for 10 rounds (exactly as in [14]) instead of 6 rounds.


6 Comparing [14] and This Paper
Technically the main differences between [14] and this paper are:

1. Here we introduce a condition: no more than indices
such that (instead of no more than pairwise distinct indices such
that of [14]). this gives us security when
(instead of or of [14]).
2. In [14], 3 rounds are needed for half the variables to look random, and then 4
more rounds for the Here we show that the will look random after
4 rounds even if the are public (with a probability near 1 when
So for the we can use the same result with only one more round. Like
this, we need less rounds in this paper compared with [14].
3. In this paper we study that come for from (or similarly
while in [14] all possible can be fixed.



TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 115

Part II: Best Found Attacks
7 Generic Attacks on
We will present here the two best generic attacks that we have found on
1. A CPA-1 attack on with and computations (This is
an improvement compared with and of [13]).
2. A KPA on with and (This is an
improvement compared with and of [13]).
1. CPA-1 attack on
Let us assume that We will simply
count the number N of such that and
This number N will be about double for compared with a truly random
permutation.
Proof:
If


This will occur if or if these values are
distinct but have the same images by so the probability is about two
times larger.
Remarks
(a) By storing the values and looking for collisions, the complexity
is in
(b) With a single value for we will get very few collisions. However this
attack becomes significant if we have a few values and for all these
values about values
2. KPA on
The CPA attack can immediately be transformed in a KPA: for random
we will simply count the number N of such that
and We will get about such collisions
for and about for a random permutation. This KPA is efficient
when becomes not negligible compared with i.e. when about


Remark. These attacks are very similar with the attacks on 5-round Feistel
schemes described by Knudsen (cf [2]) in the case where (unlike us) and
are permutations (therefore, not random functions). Knudsen attacks are based
on this theorem:
Theorem 7.1 (Knudsen, see [2]) Let and be two inputs of
a 5-round Feistel scheme, and let and be the outputs. Let us
assume that the round functions and are permutations (therefore they are
not random functions of Then, if and it is impossible to
have simultaneously and

TEAM LinG
116 Jacques Patarin

Proof. This comes immediately from (#) above.

Generic Attacks on Generators,
8
has always an even signature. This gives an attack in if we want to dis-
tinguish from random permutations (see [13]) and if we have all the possible
cleartext/ciphertext. In this appendix, we will present the best attacks that we
know when we want to distinguish from random permutations with an even
signature, or when we do not have exactly all the possible cleartext/ciphertext.
1. KPA with even.
Let be two indices, such that and
From [10] or [11] p.146, we know the exact value of H in this case, when
is even. We have:



where


i.e. is the average value of H on two cleartext/ciphertext. So there is a
from the average value.
small deviation, of about
are chosen at random, and if the functions
So in a KPA, when the
with
are chosen at random, we will get slightly more
and from a (with even) than from a truly random
permutation. This can be detected if we have enough cleartext/ciphertext
pairs from many permutations. In first approximation, these relations
will act like independent Bernoulli variables (in reality the equations are
not truly independent, but this is expected to create only a modification of
second order).
If we have N possibilities for and if X is the number of
and we expect to have:



We want in order to distinguish from a random
permutation. So we want
However, if we have available permutations, with about cleartext/ci-
phertext for each of these permutations, then (here we know these
permutations almost on every possible cleartext. If not, will be larger
and we will do more computations). gives This is
an attack with permutations and computations.
2. KPA with odd .
In [15], a KPA with odd is given (it has the same properties as the attack
above for even).

TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 117

9 Conclusion
For a block cipher from we generally want to have no better
attack than attacks with computations. If this block cipher is a Feistel
scheme we then need to have rounds since (as shown in this paper) there is
a generic attack on 5 rounds with computations in CPA-1 and compu-
tations in KPA.
In this paper we have also shown that however, in the model where the
adversaries have unlimited computing power but have access to only cleart-
ext/ciphertext pairs, the maximum possible security (i.e. is obtained
already for 5 rounds for CPA-1 and CPA-2 attacks. This solves an open prob-
lem of [1] and [14]. Moreover 6-round Feistel schemes can resist all CPCA-1
and CPCA-2 attacks when (For CPCA-1 or CPCA-2 the case
rounds is still unclear: we only know that the security is between and
When is small (for example to generate 1000 pseudorandom per-
mutations with an even signature of then more than 6 rounds
are needed. In this paper we have studied such attacks, and we have extended
the “coefficients H technique” to various cryptographic attacks.
We think that our proof strategy is very general and should be also efficient in
the future to study different kinds of functions or permutation generators, such
as, for example, Feistel schemes with a different group law than or unbalanced
Feistel schemes.


References
1. W. Aiello and R. Venkatesan. Foiling Birthday Attacks in Length-Doubling
Transformations-Benes: A Non-Reversible Alternative to Feistel. EUROCRYPT
™96 (Lecture Notes in Computer Science 1070), pp. 307“320, Springer-Verlag.
2. L. R. Knudsen. DEAL - A 128 bit Block Cipher. Technical Report #151, Univer-
sity of Bergen, Departement of Informatics, Norway, February 1998.
3. M. Luby and C. Rackoff. How to construct pseudorandom permutations from
pseudorandom functions. SIAM Journal on Computing, vol. 17, no 2, pp. 373“
386, April 1988.
4. U. Maurer. A simplified and generalized treatment of Luby-Rackoff pseudorandom
permutation generators. EUROCRYPT ™92, pp. 239“255, Springer-Verlag.
5. U. Maurer. Indistinguishability of Random Systems. EUROCRYPT ™02 (Lecture
Notes in Computer Science 2332), pp. 110“132, Springer-Verlag.
6. U. Maurer and K. Pietrzak. The security of Many-Round Luby-Rackoff Pseudo-
Random Permutations. EUROCRYPT ™03, pp. “, Springer-Verlag.
7. V. Nachev. Random Feistel schemes for available from the author at:
Valerie.nachef@math.u-cergy.fr.
8. M. Naor and O. Reingold. On the Construction of pseudo-random perlutations:
Luby-Rackoff revisited. Journal of Cryptology, vol. 12, 1999, pp. 29“66. Extended
abstract was published in Proc. 29th Ann. ACM Symp. on Theory of Computing,
1997, pp. 189“199.
9. J. Patarin. Pseudorandom Permutations based on the DES Scheme. Eurocode ™90,
LNCS 514, pp. 193“204, Springer-Verlag.

TEAM LinG
Jacques Patarin
118

10. J. Patarin. New results on pseudorandom permutation generators based on the
DES scheme. Crypto ™91,pp. 301“312, Springer-Verlag.
11. J. Patarin. Etude des g©n©rateurs de permutations bas©s sur le sch©ma du DES.
Ph. D. Thesis, Inria, Domaine de Voluceau, Le Chesnay, France, 1991.
12. J. Patarin. About Feistel Schemes with 6 (or More) Rounds. Fast Software En-
cryption 1998, pp. 103“121.
13. J. Patarin. Generic Attacks on Feistel Schemes. Asiacrypt ™01 (Lecture Notes in
Computer Science 2248), pp. 222“238, Springer-Verlag.
14. J. Patarin. Luby-Rackoff: 7 Rounds are Enough for Security. Crypto ™03
(Lecture Notes in Computer Science 2729), pp.513“529, Springer-Verlag.
15. J. Patarin. Extended version of this paper, avaible from the author.
16. B. Schneier and J. Kelsey. Unbalanced Feistel Networks and Block Cipher Design.
FSB ™96 (Lecture Notes in Computer Science 1039), pp. 121“144, Springer-Verlag.




Appendices

A Summary of the Known Results
on Random Feistel Schemes

KPA denotes known plaintext attacks. CPA-1 denotes non-adaptive chosen plain-
text attacks. CPA-2 denotes adaptive chosen plaintext attacks. CPCA-1 denotes
non-adaptive chosen plaintext and ciphertext attacks. CPCA-2 denotes adaptive
chosen plaintext and chosen ciphertext attacks. Non-Homogeneous properties are
defined in [12].
This figure 1 present the best known results against unbounded adversaries
limited by oracle queries.




Fig. 1. Minimum number of queries to distinguish from a random permutation
of For simplicity we denote for i.e. when we have security as long
as means best security proved.
* comes from [13] and comes from [7].
** with even and with exceptional equations, so if we need more than
one permutation for this property.

TEAM LinG
Security of Random Feistel Schemes with 5 or More Rounds 119




Fig. 2. Minimum number of computations needed to distinguish a generator
(with one or many such permutations available) from random permutations with an
even signature of For simplicity we denote for means best known
attack.
* If these attacks analyze about permutations of the generator and if
only one permutation is needed.

History for For the best results of security against CPA-2 was:
In 1988: (cf [3]).
In 1998: (cf [12]).
In 2003: (cf [13]).
In 2004: (cf this paper).
However CPCA-2 for is still unclear: so far we only have the original result
of Luby and Rackoff

B Example for Theorem 3.1
We will illustrate here theorem 3.1 on a small toy example. Let 1,2,3,4,5,6,7
be our indices Let us assume that is fixed such that
and are our only equations Let us assume that the
are given, and that and are the only equations
Then we want to show that and look random, where
and when are randomly chosen. For this, we fix and
and we look for the number H of that give these values.
We want to prove that this number H does not depend significantly on and
(except for well detected values of small weight). H is the number of
such that (here we put only pairwise distinct variables):
and (these
1.
two equations do not create any problem: they just fix on two points).
2. Block




TEAM LinG
120 Jacques Patarin

Block




Block


Let us assume that, for example, all the are pairwise distinct. Then
we want to evaluate the number of functions such that all the are pairwise
distinct. These conditions are more difficult to analyze since here we do not want
equalities, but non equalities.
If or we have no solution (these values
give a circle in R, X, Y).
For the to be pairwise distinct, we must choose such that:
is not in A, where A is a set of 9 values (or less if we have collisions):


In the proof of theorem 3.1, we analyze the possible dependencies of with
the values.

C Examples of Unusual Values of H for

<<

. 4
( 19)



>>