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