schemes [20], and affirm that in this case non-linear characteristics cannot be

joined together. We will demonstrate that GLC can be applied to Feistel ciphers,

which is made possible with our “Bi-Linear Cryptanalysis” (BLC) attack.

2 Feistel Schemes and Bi-linear Functions

Differential [2] and linear attacks on DES [25,1] have periodic patterns with

invariant equations for some 1, 3 or 8 rounds. In this paper we will present

several new practical attacks with periodic structure for DES, including new

1-round invariants.

2.1 The Principle of the Bi-linear Attack on Feistel Schemes

In one round of a Feistel scheme, one half is unchanged, and one half is linearly

combined with the output of the component connected to the other half. This will

allow bi-linear I/O expressions on the round function to be combined together.

First we will give an example with one product, and extend it to arbitrary bi-

linear expressions. Then in Section 3 we explain the full method in details (with

linear parts present too) for an arbitrary Feistel schemes. Later we will apply it

to get concrete working attacks for DES and other ciphers.

In this paper we represent Feistel schemes in a completely “untwisted” way,

allowing to see more clearly the part that is not changed in one round. As a

consequence, the orientation changes compared to most of the papers and we

obtain an apparent (but extremely useful) distinction between odd and even

rounds of a Feistel scheme. Otherwise, our notations are very similar to these

used for DES in [23,18]. For example denotes a sum (XOR) of some subset

of bits of the left half of the plaintext. Combinations of inputs (or outputs) of

round function number are denoted by (or Our exact

notations for DES will be explained in more details when needed, in Section 6.1.

For the time being, we start with a simple rather self-explaining example (cf.

Figure 1 ) that works for any Feistel cipher.

Proposition 2.1.1 (Combining bi-linear expressions in a Feistel cipher).

For all (even unbalanced) Feistel ciphers operating on bits with arbitrary

round functions we have:

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 25

Fig. 1. Fundamental remark: combining bi-linear expressions in a Feistel cipher

From one product this fundamental result extends immediately, by linearity,

to arbitrary bi-linear expressions. Moreover, we will see that these bi-linear ex-

pressions do not necessarily have to be the same in every round, and that they

can be freely combined with linear expressions (BLC contains LC).

3 Bi-linear Characteristics

For simplicity let In this section we construct a completely general

bi-linear characteristic for one round of a Feistel cipher. Then we show how it

combines for the next round. Here we study bits locally and denote them by

etc. Later for constructing attacks for many rounds of practical Feistel

ciphers we will use (again) the notations (cf. Section 6.1).

3.1 Constructing a Bi-linear Characteristic for One Round

Let be a homogeneous bi-linear Boolean function

Let

Let be the round function of a Feistel cipher. We assume that there exist

two linear combinations and such that the function:

is biased and equal to 0 with some probability with depending

in some way on the round key K.

TEAM LinG

26 Nicolas T. Courtois

We have By bi-linearity (or from Proposition 2.1.1) the fol-

lowing holds:

From this, for the first round, (could be also any odd-numbered round), we

obtain the following characteristic:

Finally, we note that, the part linear in the can be arbitrarily split in two

parts: with for all

All this is summarized on the following picture:

Fig. 2. Constructing a bi-linear characteristic for an odd round of a Feistel cipher

3.2 Application to the Next (Even) Round

The same method can be applied to the next, even, round of a Feistel scheme,

with the only difference that the round function is connected in the inverse

direction. In this case, to obtain a characteristic true with probability we

need to have a bias in the function:

Fig. 3. Constructing a bi-linear characteristic for an even round of a Feistel cipher

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 27

3.3 Combining Approximations to Get a Bi-linear Attack

for an Arbitrary Number of Rounds

It is obvious that such I/O sums as specified above can be combined for an

arbitrary number of rounds (contradicting [20] page 226). To combine the two

characteristics specified above, we require the following three conditions:

1. We need

2. We need

3. We need the homogenous quadratic parts et to be correlated (seen as

Boolean functions). They do not have to be the same (though in many

cases they will). In linear cryptanalysis (LC), a correlation between two

linear combinations means that these linear combinations have to be the

same. In generalized linear cryptanalysis (GLC) [9], and in particular here,

for bi-linear I/O sums, it is no longer true. Correlations between quadratic

Boolean functions are frequent, and does not imply that For these

reasons the number of possible bi-linear attacks is potentially very large.

Summary: We observe that bi-linear characteristics combine exactly as in LC

for their linear parts, and that their quadratic parts should be either identical

(with orientation that changes in every other round), or correlated.

4 Predicting the Behaviour of Bi-linear Attacks

The behaviour of LC is simple and the heuristic methods of Matsui [25] are

known to be able to predict the behaviour of the attacks with good precision

(see below). Some attacks work even better than predicted. As already suggested

in [9,20] the study of generalised linear cryptanalysis is much harder.

4.1 Computing the Bias of Combined Approximations

A bi-linear attack will use an I/O sum for the whole cipher, being a sum of I/O

sums for each round of the cipher such that the terms in the internal variables do

cancel. To compute the probability the resulting equation is true, is in general not

obvious. Assuming that the I/O sum uses balanced Boolean functions, (otherwise

it will be even harder to analyse) one can apply the Matsui™s Piling-up Lemma

from [25]. This however can fail. It is known from [9] that a sum of two very

strongly biased characteristics can have a bias much weaker than expected. The

resulting bias can even be exactly zero: an explicit example can be found in

Section 6.1. of [9]. Such a problem can arise when the connecting characteristics

are not independent. This will happen more frequently in BLC than in LC:

two linear Boolean functions are perfectly independent unless equal, for non-

linear Boolean functions, correlations are frequent. Accordingly, we do not sum

independent random variables and the Matsui™s lemma may fail.

At this stage there are two approaches: one can try to define a class of

attacks that can be proved to work, and restrict oneself only to studying such

TEAM LinG

28 Nicolas T. Courtois

attacks, or try to explore all possible attacks, including those that do work

experimentally without proof. This first approach is adopted in [9]: the Lemma

6 gives a sufficient condition to guarantee that the Piling-up lemma will apply.

For this the probability, that the characteristic is true, for a random partial key,

should be independent of the input (e.g. the input of the whole round). This

explains why Matsui™s attacks indeed work well. In [9] it allows to prove that the

proposed family of GLC attacks based on homomorphic properties will work as

predicted. We will also use this argument in Section 5.

In this paper we frequently adopt rather the second approach: try find as

many working attacks as possible, even if current theory does not allow to pre-

dict their behaviour with accuracy. A price to pay for this is that each application

of Matsui™s Lemma will be systematically questioned and confronted to experi-

mental results.

4.2 Key Dependence in Bi-linear Attacks

Another important property of bi-linear cryptanalysis is that the existence of

a bias for one characteristic does frequently depend on the key. This does not

really happen for LC applied DES, because in DES all key bits are combined

linearly and a linear equation will be true with probability either or

depending on the key. However it will happen for LC and other ciphers, if key

bits are involved in a more complex way, for example for ICE [22].

In bi-linear cryptanalysis, the behaviour becomes complex already when the

key bits are combined linearly as in DES. Adding a constant (a key bit) to

an input of an S-box, does not only modify the constant part in a bi-linear

characteristic, but also the linear part. (We note that for DES only the linear

part in the output variables will be modified when the key changes). From this,

quite frequently two bi-linear characteristics for two parts of a cipher (e.g. for

S-boxes) will only connect together for some keys. Such attacks are still very

interesting and frequently also do work, with only a slightly weaker bias, for all

the other keys. For simplicity, no key bits are displayed in bi-linear characteristics

for one or several rounds of a cipher that are studied/displayed in this paper.

The values of biases we will present (unless otherwise stated) are given for the

reference key being zero. Yet typically we observed that they exist, and slightly

vary in value, also for any other key (chosen at random). In rare cases, the bias

works well only for a fraction of keys (e.g. 25 %): this happens in Appendix B.1.

4.3 Exploring Bi-linear Cryptanalysis

There are different approaches to finding interesting bi-linear attacks to block

ciphers. In few cases one can construct attacks that will provably or arguably

work (see [9] and later Section 5). Another method is to construct characteristics

“by hand” around some particularly strong bias found for one S-box.

We noted the two major difficulties: predicting the bias of combined charac-

teristics, and huge number of possible characteristics (including fragmentation

due to the fact they the bias does in general depend on the key). These make

it very difficult to have a systematic method (a computer program) that would

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 29

compute the best bi-linear characteristic for a given cipher. To check if an attack

indeed works requires to be able to generate as many plaintexts as for the real

attack. To find the best attack is even much harder. It requires to exhaustively

search and reject lots of other combinations that should work well but they don™t.

Each of them has to be tested on an equally large set of plaintexts.

5 The Killer Example for Bi-linear Cryptanalysis

We will construct a practical cipher that is very secure w.r.t. all known attacks

for block ciphers, in particular for LC, yet broken by BLC. It mixes two group

operations: the XOR and the multiplication in e.g. or 64. It uses

the inverse in (cf. Rijndael): let in when

and 0 otherwise. We build a Feistel cipher with the round function

being:

with being the partial key, and G being some function with S-boxes and

arbitrary components . In order to get an insecure cipher, we

need to assume that some linear combination of outputs of G is biased. For

example, let with probability 3/4. Building a cipher with G alone

would be insecure for LC, however here G is composed by a group operation ·

with Inv(X). The Inv(X) assures global diffusion and very high non-linearity

(cf. [3]). Accordingly our round function has very good resistance to linear and

differential cryptanalysis for most G, even when G = 0. But not against BLC.

First, we can consider a bi-linear attack with bi-linear equations over

Let with From (2), or if we prefer,

directly from Proposition 2.1.1 and by symmetry we get:

Now, with probability We rewrite it:

Then we use the linear output bias of with probability 3/4.

TEAM LinG

30 Nicolas T. Courtois

The last expression is equal to come constant denoted with probability

3/4. Finally, we combine with (3) (or equivalently sum these bi-linear expressions

over the whole cipher with rounds).

What we obtained is a biased bi-linear I/O sum for the whole cipher. We can

distinguish this cipher from a random permutation given about plaintexts.

For example 16 rounds will be broken on a laptop PC.

Does it work as predicted? In general, as we explain in Section 4.1, it is hard

to predict accurately the behaviour of a composed bi-linear attack. However we

have little doubt it will work: the Inv(X) should render possible correlation

between approximations being combined negligible. In some case we can even

prove that this attack works: when G = 0, and also when one fixed linear com-

bination of output bits of G is 0, (the other parts can be arbitrary functions). In

these cases, dependencies cannot be a problem: we add equations (5) true with

probability 1 to get the equation (6) true with probability 1.

Related work: Similar results were previously obtained for some substitution-

permutation network (SPN) ciphers. In [9] Harpes, Kramer and Massey give

an example of 8-bit SPN that is secure against LC and DC, but insecure for

generalised linear cryptanalysis due to a probabilistic homomorphic property of

each round relative to quadratic residuosity function modulo The Jakobsen

attack for substitution ciphers that uses probabilistic univariate polynomials

from [15] can also be seen as a special case of GLC. However, it is the first time

that GLC allows to break a Feistel cipher, which contradicts the impossibility

professed by Knudsen and Robshaw [20]. This cipher is built with state-of-art

components (inverse in and can in addition incorporate any additional

fashionable component with lots of theory and designer tricks, as a part of G.

Due to G it will not have homomorphic properties. Moreover, by adjusting the

bias in G, the security of this cipher against BLC will be freely adjusted between

(nearly) zero and infinity. It can therefore be arbitrarily weak for BLC, and this

even for a very large number of rounds. Yet, the security against the usual attacks

(LC, DC) should remain equally good (due to the big Inv S-box).

6 Bi-linear Attacks on DES

6.1 Notation

We ignore the initial and final permutations of DES that have no incidence on the

attacks. We use the “untwisted method” of representing DES, as on the right-

hand figure, page 254 in [28]. The bit numbering is compatible with the FIPS

standard [8], and [23,18], and differs from Biham, Shamir [2] or Matsui [25,27].

We denote the bits of the left hand side of the plaintext by The

bits of the right hand side are Similarly, as in other papers, the

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 31

plaintext after rounds will be except that we felt it necessary to have our

notations completely “untwisted” which implies that our and for an odd

will be inversed compared to [23, 18, 28], Then, we apply the popular

convention being For example is

the XOR of 4 bits of the left half of the plaintext that are added to the outputs

of S1 in the first round. We denote the input bits to the round function by

Similarly the output bits will be

For odd we have and

For even we have and

For individual S-boxes, we will denote the inputs/outputs by respectively

and with being directly the numbers 1..32 in the round function

of DES. For example O[8],O[14],O[25],O[3] are the outputs of S-box S5, and

J[16], . . . , J[21] are the inputs of this S-box S5. Depending on the key in round

we have or For better readability, we will avoid

naming precisely the key bits involved.

First Example of Bi-linear Cryptanalysis of DES

6.2

Our simulations on DES S-boxes (cf. Appendix A) show that the following two

bi-linear characteristics exist for DES S-boxes S1 and S5:

From these, acting as if all the key bits were zero we deduce

the following bi-linear characteristic for two rounds:

The explanation is given on the following picture:

Fig. 4. Our first example - an invariant bi-linear attack on DES

TEAM LinG

32 Nicolas T. Courtois

We verified this bias experimentally, and the probability is (we were lucky)

equal to the probability that is predicted by Matsui™s Piling-Up Lemma.

Key Dependence: Very surprisingly, the above equation is biased, not only

when all key bits are 0, but for every DES key. This can be seen to come from

a couple of other (different) bi-linear characteristics from Appendix A.

More rounds: It is easy to see from the picture, and we verified it experimen-

tally, that is also biased for 1,2,3,4,5,6,7,8,9,10,11,... rounds of DES, and

all this happens to work about equally well for an arbitrary key.

Relation to LC: The bias of is closely related to some prominent equations

of Matsui, see the extended version of this paper.

6.3 Invariant Attacks on DES

The equation is an invariant equation, i.e. the input and the output bi-linear

expressions are the same. We have found a simple invariant bi-linear I/O sum

for DES that is biased for any key and for any number of rounds. For LC and

DES, such simple invariant characteristics do exist, have been found by Biham

(page 347 in [1]) in close relation to Davies-Murphy attack. The example

above is one of the best we found for DES, and so far it also the only known

non-linear 1-round invariant attack on DES that works really well in practice.

Our invariant on DES is stronger than Biham™s. We recall that Biham uses a

bias on a sum of some outputs for two successive DES S-boxes. The best bias

obtained by Biham (also exhibited by Matsui in [26] and contained unnoticed in

the earlier Davies-Murphy attack [6,7]) is equal to (35/64 “ 1/2) for 2 rounds

and for S-boxes S7-S8. This gives for 12 rounds. Instead, gives

experimentally only about Accordingly, is the strongest known

1-round invariant attack on DES.

To break full DES requires a bias for 14 rounds (Matsui™s 2R method) and

the Biham™s invariant requires then plaintexts. Our invariant attack requires

about plaintexts (the bias of for 14 rounds is expected to be about

we did not dispose of a sufficient computing power to compute it exactly).

6.4 How Good Is Our First Example, BLC vs. LC

These new properties of DES give a chosen-plaintext attack on an arbitrary

number of rounds of DES, somewhat simpler than Matsui™s laborious search

for the best linear characteristic. If we try here to predict the resulting bias

for 14 rounds by applying the Matsui™s Piling-up formula, we would get for 14

rounds the bias of: which means an attack on full DES with only

known plaintexts (!?). Unfortunately, unlike for LC in DES, such predictions are

frequently not valid for BLC. Starting from 3 rounds, the bias of our invariant

does not follow the prediction at all, yet remains significative. For example if we

apply Matsui™s Piling-Up Lemma to predict the bias for 4 rounds as 2+2 rounds,

we obtain while in practice it is about Our invariant attack

seems very bad for 4 rounds, and unfortunately with we never get a bias better

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 33

than obtained by Matsui. Yet, it is the best invariant attack on DES known, and

for more than 4 rounds the results are again not so bad. Only slightly worse

than Matsui. For example for 12 rounds the best result of Matsui from [25] gives

while for and a random key our simulation gives To

break full DES Matsui requires about plaintexts, and with we also need

about (and both are related). In the full version of this paper we give a

heuristic argumentation why for DES (but not in general !) the complexity of

the best bi-linear attack should be roughly the same than for LC.

For DES and 1-round invariants attacks extended to an arbitrary number of

rounds, BLC gives strictly better results than LC. It is also so for more complex

periodic constructions and we are going to see that BLC attacks can also be

strictly better than any existing linear attack.

6.5 Second Example of Bi-linear Cryptanalysis of DES

In order to exhibit biases really better than Matsui we looked what is the best

bi-linear characteristic that exists in DES:

for S5 with probability 61/64.

We note that this equation can be seen as “causing” the existence of the

Matsui™s best equation (A) for S5: their difference is highly biased. Based mainly

on this, we constructed a periodic characteristic for 3,7, 11 and more rounds that

is strictly better than the best results of Matsui for the same number of rounds.

Proposition 6.5.1 (Our Best Attack on 11 Rounds of DES). For all keys,

the following equation is biased for 11 rounds of DES:

The exact construction to achieve this is a bit complicated. (cf. Appendix

B). The bias of this equation is strictly better than the best linear characteristic

for 11 rounds obtained by Matsui (which gives for 11 rounds). It has

been verified by computer simulations at every stage. We note also that both

are closely related: their difference, is a biased Boolean function.

Our second example allows us to give an attack strictly better than Matsui

for 11+2=13 rounds of DES. For the full 16-round DES our results are roughly

as good as Matsui (but we hope to improve this soon too). For 17 rounds of

DES, as the construction of our second example is periodic, we expect that

for 11+4=15 rounds it should also be better than the best bias of Matsui, which

would allow to break 15+2=17 rounds of DES faster than by LC. We do not

dispose of a sufficient computing power to fully confirm this fact.

7 Conclusion

It was stated that for Feistel ciphers non-linear characteristics cannot be joined

together for several rounds, see [20]. In this paper we show that generalised linear

TEAM LinG

Nicolas T. Courtois

34

cryptanalysis (GLC) is in fact possible for Feistel schemes. To achieve this goal,

we introduced bi-linear cryptanalysis (BLC). It gives a new (and the fastest

known) 1-round invariant attack on DES. Though more powerful, generalized

linear cryptanalysis is unfortunately much harder to study than LC. At present

heuristic constructions, to be confirmed (or not) by computer simulations are

the only method known to explore it. BLC is related to LC in multiple important

ways. It contains LC as a sub-set. LC can be used to construct good bi-linear

characteristics and vice-versa. BLC also contains LC as an extension: a combi-

nation of biased bi-linear characteristics may extend a concrete combination of

biased linear characteristics by adding quadratic polynomials. Yet BLC can be

strictly better than any (existing) linear attack. This was demonstrated for 3, 7,

11 and more rounds of DES, and also for

In this paper we only initiate the study of bi-linear cryptanalysis. BLC and

GLC extend the role of LC as an essential tool to evaluate the real-life security

of many practical ciphers. An interesting contribution of this paper is to point

out that, though GLC is excessively general to be systematically explored, the

properties of the top-level structure of a cryptographic scheme (e.g. being a

Feistel scheme) will determine the type of the attacks (e.g. BLC) that may indeed

work. Our new attack can be quite devastating: we constructed a large family of

practical ciphers based on big Rijndael-type S-box, that are strongly resistant

against LC and all previously known attacks on Feistel ciphers, yet can be broken

in practice with BLC for an important number of rounds. Fortunately, for DES,

BLC gave only slight improvements over LC and does not cause excessive trouble.

References

1. Eli Biham: On Matsui™s Linear Cryptanalysis, Eurocrypt™94, LNCS 950, Springer-

Verlag pp. 341-355, 1994.

2. Eli Biham and Adi Shamir, Differential Cryptanalysis of DES-like Cryptosystems.

Journal of Cryptology, vol. 4, pp. 3-72, IACR, 1991.

3. Anne Canteaut, Marion Videau: Degree of composition of highly nonlinear func-

tions and applications to higher order differential cryptanalysis, Eurocrypt 2002,

LNCS 2332, Springer, 2002.

4. Anne Tardy-Corfdir, Henri Gilbert: A Known Plaintext Attack of FEAL-4 and

FEAL-6, Crypto™91, LNCS 576, Springer, pp. 172-181, 1992.

5. Nicolas Courtois, Guilhem Castagnos and Louis Goubin: What do DES S-boxes

Say to Each Other ? Available on eprint.iacr.org/2003/184/.

6. D.W. Davies, Some Regular Properties of the Data Encryption Standard,

Crypto™82, pp. 89-96, Plenum Press, New-York, 1982.

7. D. Davies and S. Murphy, Pairs and Triplets of DES S-Boxes, Journal of Cryptol-

ogy, vol. 8, Nb. 1, pp. 1-25, 1995.

8. Data Encryption Standard (DES), Federal Information Processing Standards Pub-

lication (FIPS PUB) 46-3, National Bureau of Standards, Gaithersburg, MD

(1999). http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf

9. C. Harpes, G. Kramer, and J. Massey: A Generalization of Linear Cryptanaly-

sis and the Applicability of Matsui™s Piling-up Lemma, Eurocrypt™95, LNCS 921,

Springer, pp. 24-38. http://www.isi.ee.ethz.ch/ harpes/GLClong.ps

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 35

10. Carlo Harpes: Cryptanalysis of iterated block ciphers, PhD thesis, No 11625, Swiss

Federal Int. of Tech., ETH Series in Information Processing, Ed. J. L. Massey,

Hartung-Gorre Verlag Konstanz, 1996, ISBN 3-89649-079-6, ISSN 0942-3044.

11. Carlo Harpes: Partitioning Cryptanalysis, Post-Diploma Thesis, Signal and Infor-

mation Processing Lab., Swiss Federal Institute of Technology, Zurich, March 1995.

http://www.isi.ee.ethz.ch/˜harpes/pc.ps

12. Thomas Jakobsen, Carlo Harpes: Non-Uniformity Measures for Generalized Linear

Cryptanalysis and Partitioning Cryptanalysis, Pragocrypt™96, 1996.

13. Thomas Jakobsen: Correlation Attacks on Block Ciphers, Master™s Thesis, Dept.

of Mathematics, Technical University of Denmark, January 1996.

14. Thomas Jakobsen: Higher-Order Cryptanalysis of Block Ciphers. Ph.D. thesis,

Dept. of Math., Technical University of Denmark, 1999.

15. Thomas Jakobsen: Cryptanalysis of Block Ciphers with Probabilistic Non-Linear

Relations of Low Degree, Crypto 98, LNCS 1462, Springer, pp. 212-222, 1998.

16. Pascal Junod: On the complexity of Matsui™s attack, Selected Areas in Cryptog-

raphy (SAC™01), Toronto, Canada, LNCS 2259, pp. 199-211, Springer, 2001.

17. Burton S. Kaliski Jr, and M.J.B. Robshaw. Linear Cryptanalysis Using Multiple

Approximations, Crypto™94, LNCS, Springer, pp. 26-39, 1994.

18. Toshinobu Kaneko and Takeshi Shimoyama: Quadratic Relation of S-box and Its

Application to the Linear Attack of Full Round DES, In Crypto 98, LNCS 1462,

p. 200-211, SPringer, 1998.

19. Kwangjo Kim. Sangjin Lee, Sangjoon Park, Daiki Lee: Securing DES S-boxes

against Three Robust Cryptanalysis, SAC™95, pp.145-157, 1995.

20. Lars R. Knudsen, Matthew J. B. Robshaw: Non-Linear Characteristics in Linear

Cryptoanalysis. Eurocrypt™96, LNCS 1070, Springer, pp. 224-236, 1996.

21. Lars R. Knudsen, John Erik Mathiassen: A Chosen-Plaintext Linear Attack on

DES. FSE™2000, LNCS 1978, Springer, pp. 262-272, 2001.

22. Matthew Kwan: The Design of the ICE Encryption Algorithm, FSE™97, 4th Inter-

national Workshop, Haifa, Israel, Springer, LNCS 1267, pp. 69-82, 1997.

Available from http://www.darkside.com.au/ice/ice.ps.gz.

23. Susan K. Langford, Martin E. Hellman: Differential-linear cryptanalysis, Crypto

94, LNCS 839, pp. 17-25, Springer, 1994.

24. Michael Luby, Charles W. Rackoff, How to construct pseudorandom permutations

from pseudorandom functions, SIAM Journal on Computing, vol. 17, n. 2, pp.

373-386, April 1988.

25. M. Matsui: Linear Cryptanalysis Method for DES Cipher, Eurocrypt™93, LNCS

765, Springer, pp. 386-397, 1993.

26. M. Matsui, On correlation between the order of S-boxes and the strength of DES,

Eurocrypt™94, LNCS 950, pp. 366-375, Springer, 1995.

27. M.Matsui: The First Experimental Cryptanalysis of the Data Encryption Stan-

dard, Crypto™94, LNCS 839, Springer, pp. 1-11, 1994.

28. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied

Cryptography; CRC Press, 1996.

29. J. Patarin, How to construct pseudorandom and super pseudorandom permutations

from one single pseudorandom function. Eurocrypt™92,Springer, pp. 256-266, 1992.

30. Adi Shamir: On the security of DES, Crypto™85, LNCS 218, Springer, pp. 280-281,

1985.

TEAM LinG

36 Nicolas T. Courtois

A Selected Bi-linear Characteristics of DES S-Boxes

In this section we give some bi-linear characteristics for DES S-boxes. Our results

are not exhaustive: the number of possible bi-linear characteristics is huge and

we do not have a fast method to find all interesting characteristics. Accordingly

we are not certain to have found the best existing characteristics. It is certain

that there is no characteristics true with probability 1, as these are easy to check

algebraically. Otherwise we explored all cases that use up to two products and

we conjecture that the other does not have practical relevance for the security

of DES. We give here some interesting results we have found. More will appear

in the extended version of this paper.

B Improved Bi-linear Attacks for DES

The goal of this section is to find or construct examples where bi-linear crypt-

analysis gives strictly better bias on DES than the best Matsui™s result.

We look at the best Matsui™s characteristic on 3 rounds given at the last

page of [25]. By itself, it can be considered as very good, even compared to

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 37

other Matsui™s characteristics: it uses twice the best element (A) of Matsui, and

nothing between them. Moreover, this element (A) is in itself the best linear

characteristic that exist in DES, first described by Shamir in [30]:

From this we get immediately, using Matsui™s Piling-Up Lemma from [25],

that for 3 rounds, and for any key, the following equation is biased:

We call Matsui-3 this equation.

B.1 Improving on Matsui-3

We will show that with bi-linear characteristics, there are strictly better equa-

tions than Matsui-3. Our simulations looking for the best bi-linear characteristics

for DES S-boxes (cf. Appendix A), showed that the best one is the following:

Remark: It is clearly related to, and can be seen as “causing” the existence of

the Matsui™s equation (A): their difference is naturally biased.

We will use this characteristic. Let KS5 denote the combination of the S-box

S5 and the key bits XORed to its inputs. It is easy to see that for KS5, if we

denote by K[sth] some constant linear combination of key bits, for any key, one

of the following equations is always strongly biased:

In our construction, we will use one of the above, and we will also use another,

naturally biased equation, which will be one of the following:

Now we are ready to construct characteristics for 3 rounds of DES.

TEAM LinG

38 Nicolas T. Courtois

Fig. 5. Combining a1-b-a1 to get a characteristic for 3 rounds of DES

Fig. 6. Combining a2-c-a1 to get a characteristic for 3 rounds of DES

As one should expect, our construction goes as follows:

In round 1 and 3, depending on the key either a1 or a2 is strongly biased.

To connect a1 to a1, or a2 with a2, we can use b, as in Figure 5.

To connect a1 with a2 and the reverse, we use c, as in Figure 6.

For 3 rounds and for any key, we always have a strong bias on one of the

four possibilities: a1-b-a1, a1-c-a2, a2-c-a1, a2-b-a2.

TEAM LinG

Feistel Schemes and Bi-linear Cryptanalysis 39

From Matsui™s Piling-Up Lemma, we expect that the whole characteristic

will be true with probability Our simulations show that it is

between and

Since, the choice of a1/a2 depends on a linear combination of key bits, We

can combine all these into one equation and we get the following result:

Proposition B.1.1 (Our Best Attack on 3 Rounds of DES). For all keys,

the following equation is biased for 3 rounds of DES:

In comparison, Matsui-3 gives Bi-linear cryptanalysis works

better than LC. In the next section we will extend this result (and again beat

Matsui) to 7, 11 and more rounds.

Remark: The equation above can be seen as 4 different equations, each of them

is highly biased for 1/4 of all keys. We observed that each of the 4 equations

is also biased for all DES keys, except that for 3/4 of them the bias is much

weaker, we get about

B.2 Extending the Result for 7, 11 and More Rounds

The idea is to find an element (maybe not very good in itself) that will allow to

connect together our (very good) characteristics on 3 rounds. For example, to

connect Figure 5 with Figure 6 we use the following element:

Fig. 7. Connecting the output of a1 to the input of a2

Simulations show that, for any key, this characteristic is true with probability

about 1/2 ± 0.8/64. The explanation is as follows: the bias is due to to the

combination of Matsui™s equation (C)

and of the fact that I[3] · O[16, 17, 20] is naturally biased. The same element

(Figure 7) does also work to connect a2 to a1.

It remains to be seen how the connection between a1 and a1 or a2 and a2.

This is done in a very similar way: we combine (C) with

that is also naturally biased.

TEAM LinG

40 Nicolas T. Courtois

Summary: In every of 4 possible cases, there is a connecting element based

on (C). This means that, also for 7 rounds and for any key, again one of the

four possibilities is quite biased: a1-b-a1, a1-c-a2, a2-c-a1, a2-b-a2. Again we

can recompose it in a single attack:

Proposition B.2.1 (Extension to 7 Rounds of DES). For all keys, the

following equation is biased for 7 rounds of DES:

This bias is, depending on the key, sometimes better, sometimes worse than

Matsui-7 that gives

Finally, it is now obvious, that our construction works also for 11, 15, 19

rounds etc. We verified experimentally that for 11 rounds we have:

Proposition B.2.2 (Our Best Attack on 11 Rounds of DES). For all

keys, the following equation is biased for 11 rounds of DES:

For a few different keys we have tried (long computation on a PC) the bias

was always strictly better than Matsui-11 that gives

Remark: The best characteristics found by Matsui for 3 and 11 rounds [25]

are closely related to those presented here: their difference is a biased Boolean

function. BLC contains LC not only as a subset, but also as an extension allowing

to strictly improve the best linear attacks on DES by adding higher degree

monomials.

B.3 Beyond Bi-linear Attacks: Using Cubic Equations

We observed that, for 3 rounds, even better results can be achieved using cu-

bic partially bi-linear characteristics, instead of quadratic bi-linear (**) from

Proposition B.1.1. Our simulations show that, for an important fraction of keys:

The explanation why this works is quite similar. Though the non-linear part

of this equation is not bi-linear, it is well correlated with a truly bi-linear func-

tion:

Unfortunately, the bias of is worse for other keys. On average, the

best bias we know for 3 rounds remains from Proposition B.1.1. We also

observed that that works for any number of DES rounds and for any key,

but again the results are not as good as with

TEAM LinG

Short Group Signatures

Dan Boneh1,*, Xavier Boyen2, and Hovav Shacham3

1

Stanford University

dabo@cs.stanford.edu

2

Voltage Security

xb@boyen.org

3

Stanford University

hovav@cs.stanford.edu

Abstract. We construct a short group signature scheme. Signatures

in our scheme are approximately the size of a standard RSA signa-

ture with the same security. Security of our group signature is based

on the Strong Diffie-Hellman assumption and a new assumption in bilin-

ear groups called the Decision Linear assumption. We prove security of

our system, in the random oracle model, using a variant of the security

definition for group signatures recently given by Bellare, Micciancio, and

Warinschi.

1 Introduction

Group signatures, introduced by Chaum and van Heyst [14], provide anonymity

for signers. Any member of the group can sign messages, but the resulting signa-

ture keeps the identity of the signer secret. In some systems there is a third party

that can trace the signature, or undo its anonymity, using a special trapdoor.

Some systems support revocation [12,4, 29,15] where group membership can be

selectively disabled without affecting the signing ability of unrevoked members.

Currently, the most efficient constructions [2,12,4] are based on the Strong-RSA

assumption introduced by Baric and Pfitzman [5].

In the last two years a number of projects have emerged that require the

properties of group signatures. The first is the Trusted Computing effort [28]

that, among other things, enables a desktop PC to prove to a remote party

what software it is running via a process called attestation. Group signatures

are needed for privacy-preserving attestation [17, Sect. 2.2]. Perhaps an even

more relevant project is the Vehicle Safety Communications (VSC) system from

the Department of Transportation in the U.S. [18]. The system embeds short-

range transmitters in cars; these transmit status information to other cars in

close proximity. For example, if a car executes an emergency brake, all cars in

its vicinity are alerted. To prevent message spoofing, all messages in the system

are signed by a tamper-resistant chip in each car. (MACs were ruled out for this

many-to-many broadcast environment.) Since VSC messages reveal the speed

and location of the car, there is a strong desire to provide user privacy so that

Supported by NSF and the Packard Foundation.

*

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 41“55, 2004.

© International Association for Cryptologic Research 2004

TEAM LinG

42 Dan Boneh, Xavier Boyen, and Hovav Shacham

the full identity of the car sending each message is kept private. Using group

signatures, where the group is the set of all cars, we can maintain privacy while

still being able to revoke a signing key in case the tamper resistant chip in a car

is compromised. Due to the number of cars transmitting concurrently there is a

hard requirement that the length of each signature be under 250 bytes.

The two examples above illustrate the need for efficient group signatures.

The second example also shows the need for short group signatures. Currently,

group signatures based on Strong-RSA are too long for this application.

We construct short group signatures whose length is under 200 bytes that

offer approximately the same level of security as a regular RSA signature of the

same length. The security of our scheme is based on the Strong Diffie-Hellman

(SDH) assumption [8] in groups with a bilinear map. We also introduce a new as-

sumption in bilinear groups, called the Linear assumption, described in Sect. 3.2.

The SDH assumption was recently used by Boneh and Boyen to construct short

signatures without random oracles [8]. A closely related assumption was used by

Mitsunari et al. [22] to construct a traitor-tracing system. The SDH assumption

has similar properties to the Strong-RSA assumption. We use these properties

to construct our short group signature scheme. Our results suggest that systems

based on SDH are simpler and shorter than their Strong-RSA counterparts.

Our system is based on a new Zero-Knowledge Proof of Knowledge (ZKPK)

of the solution to an SDH problem. We convert this ZKPK to a group signature

via the Fiat-Shamir heuristic [16] and prove security in the random oracle model.

Our security proofs use a variant of the security model for group signatures

proposed by Bellare, Micciancio, and Warinschi [6].

Recently, Camenisch and Lysyanskaya [13] proposed a signature scheme with

efficient protocols for obtaining and proving knowledge of signatures on commit-

ted values. They then derive a group signature scheme using these protocols as

building blocks. Their signature scheme is based on the LRSW assumption [21],

which, like SDH, is a discrete-logarithm-type assumption. Their methodology

can also be applied to the SDH assumption, yielding a different SDH-based

group signature.

The SDH group signature we construct is very flexible and we show how to

add a number of features to it. In Sect. 7 we show how to apply the revocation

mechanism of Camenisch and Lysyanskaya [12]. In Sect. 8 we briefly sketch how

to add strong exculpability.

2 Bilinear Groups

We first review a few concepts related to bilinear maps. We follow the notation

of Boneh, Lynn, and Shacham [9]:

1. and are two (multiplicative) cyclic groups of prime order

2. is a generator of and is a generator of

3. is a computable isomorphism from to with and

4. is a computable map with the following properties:

Bilinearity: for all and

Non-degeneracy:

TEAM LinG

Short Group Signatures 43

Throughout the paper, we consider bilinear maps where

all groups are multiplicative and of prime order One could set

However, we allow for the more general case where so that

our constructions can make use of certain families of non-supersingular elliptic

curves defined by Miyaji et al. [23]. In this paper we only use the fact that

can be of size approximately elements in are 171-bit strings, and that

discrete log in is as hard as discrete log in where is 1020 bits. We will

use these groups to construct short group signatures. We note that the bilinear

groups of Rubin and Silverberg [25] can also be used.

We say that two groups as above are a bilinear group pair if the

group action in and the map and the bilinear map are all efficiently

computable.

The isomorphism is only needed for the proofs of security. To keep the

discussion general, we simply assume that exists and is efficiently computable.

(When are subgroups of the group of points of an elliptic curve the

trace map on the curve can be used as this isomorphism. In this case,

and

3 Complexity Assumptions

3.1 The Strong Diffie-Hellman Assumption

Let be cyclic groups of prime order where possibly Let

be a generator of and a generator of Consider the following problem:

Diffie-Hellman Problem. The problem in is de-

fined as follows: given a as input,

output a pair where An algorithm has advantage

in solving in if

where the probability is over the random choice of in and the random

bits of

Definition 1. We say that the assumption holds in if

no algorithm has advantage at least in solving the problem in

Occasionally we drop the and and refer to the assumption rather

than the assumption. The assumption was recently used by

Boneh and Boyen [8] to construct a short signature scheme without random

oracles. To gain confidence in the assumption they prove that it holds in generic

groups in the sense of Shoup [27]. The assumption has similar properties

to the Strong-RSA assumption [5]. We use these properties to construct our

short group signature scheme.

TEAM LinG

44 Dan Boneh, Xavier Boyen, and Hovav Shacham

3.2 The Linear Diffie-Hellman Assumption

With as above, along with arbitrary generators and of

consider the following problem:

Decision Linear Problem in Given as input, out-

put yes if and no otherwise.

One can easily show that an algorithm for solving Decision Linear in gives

an algorithm for solving DDH in The converse is believed to be false. That

is, it is believed that Decision Linear is a hard problem even in bilinear groups

where DDH is easy. More precisely, we define the advantage of an algorithm

in deciding the Decision Linear problem in as

The probability is over the uniform random choice of the parameters to and

over the coin tosses of We say that an algorithm Decision

Linear in if runs in time at most and is at least

Definition 2. We say that the Linear Assumption (LA) holds in

if no algorithm has advantage at least in solving the Decision Linear

problem in

In the full version of the paper we show that the Decision Linear Assumption

holds in generic bilinear groups.

Linear Encryption. The Decision Linear problem gives rise to the Linear

encryption (LE) scheme, a natural extension of ElGamal encryption. Unlike

ElGamal encryption, Linear encryption can be secure even in groups where a

DDH-deciding algorithm exists. In this scheme, a user™s public key is a triple

of generators her private key is the exponents such that

To encrypt a message choose random values and

output the triple To recover the message from an encryption

, the user computes By a natural extension of the proof

of security of ElGamal, LE is semantically secure against a chosen-plaintext

attack, assuming Decision-LA holds.

4 A Zero-Knowledge Protocol for SDH

We are now ready to present the underlying building block for our group sig-

nature scheme. We present a protocol for proving possession of a solution to

an SDH problem. The public values are and Here

for some (secret) The protocol proves possession of a pair

where and such that Such a pair satisfies

We use a standard generalization of Schnorr™s protocol for

proving knowledge of discrete logarithm in a group of prime order [26].

TEAM LinG

Short Group Signatures 45

Protocol 1. Alice, the prover, selects exponents and computes a

Linear encryption of A:

She also computes two helper values and

Alice and Bob then undertake a proof of knowledge of values

satisfying the following five relations:

This proof proceeds as follows. Alice picks blinding values and

at random from She computes five values based on all these:

She then sends to the verifier. Bob, the verifier,

sends a challenge value chosen uniformly at random from Alice computes

and sends back and

Finally, Bob verifies the following five equations:

Bob accepts if all five hold.

Theorem 1. Protocol 1 is an honest-verifier zero-knowledge proof of knowledge

of an SDH pair under the Decision Linear assumption.

The proof of the theorem follows from the following lemmas that show that

the protocol is (1) complete (the verifier always accepts an interaction with

an honest prover), (2) zero-knowledge (can be simulated), and (3) a proof of

knowledge (has an extractor).

Lemma 1. Protocol 1 is complete.

Proof. If Alice is an honest prover in possession of an SDH pair she follows

the computations specified for her in the protocol. In this case,

TEAM LinG

46 Dan Boneh, Xavier Boyen, and Hovav Shacham

so (1) holds. For analogous reasons (2) holds. Further,

so (4) holds. For analogous reasons (5) holds. Finally,

so (3) holds.

Lemma 2. Transcripts of Protocol 1 can be simulated, under the Decision Lin-

ear assumption.

Proof. We describe a simulator that outputs transcripts of Protocol 1.

Pick and Set and

Assuming the Decision Linear assumption holds on the tuples

generated by the simulator are drawn from a distribution that is indistinguish-

able from the distribution output by any particular prover.

The remainder of this simulator does not assume knowledge of A, or

so it can also be used when and are pre-specified. When the pre-

specified are a random Linear encryption of some A, the remainder

of the transcript is simulated perfectly.

Now choose a challenge Select and set Then

(1) is satisfied. With and fixed, a choice for either of or determines

the other, and a uniform random choice of one gives a uniform random choice

of the other. Therefore and are distributed as in a real transcript. Choose

and analogously.

Select and set and Again, all

the computed values are distributed as in a real transcript. Finally set

This satisfies (3), and it, too, is properly distributed.

The transcript output is

As argued above, this transcript is distributed identically to transcripts of Pro-

tocol 1, assuming the Decision Linear assumption holds.

Lemma 3. There exists an extractor for Protocol 1.

Proof. Suppose that an extractor can rewind a prover in the protocol above to

the point just before the prover is given a challenge At the first step of the

protocol, the prover sends and Then, to challenge

TEAM LinG

Short Group Signatures 47

value the prover responds with and To challenge value

the prover responds with and If the prover is convincing,

all five verification equations (1“5) hold for each set of values.

For brevity, let and similarly for

and

Now consider (1) above. Dividing the two instances of this equation, we

obtain The exponents are in a group of known prime order, so we

can take roots; let Then Similarly, from (2), we obtain

such that

Consider (4) above. Dividing the two instances gives Substi-

tuting gives or Similarly, from (5) we

deduce that

Finally, dividing the two instances of (3), we obtain

Taking roots, and letting we obtain

This can be rearranged as

or, letting

Thus the extractor obtains an SDH tuple (Ã, Moreover, the Ã in this SDH

tuple is, perforce, the same as that in the Linear encryption

5 SDH Signatures of Knowledge

Armed with Theorem 1, we obtain from Protocol 1 a signature scheme secure in

the random oracle model by applying the Fiat-Shamir heuristic [16]. Signatures

obtained from a proof of knowledge via the Fiat-Shamir heuristic are often called

signatures of knowledge. We use a variant of the Fiat-Shamir heuristic, used also

by Ateniese et al. [2], where the challenge rather than the values is

transmitted in the signature; the output of the random oracle acts as a checksum

for those values not transmitted.

The signature scheme is defined as follows. The public key contains a hash

function (viewed as a random oracle) groups and with

respective generators and as in Sect. 2, the random generators and

of and where is chosen at random in The private key

TEAM LinG

48 Dan Boneh, Xavier Boyen, and Hovav Shacham

is an SDH pair i.e., a pair such that Any such pair is a valid

private key.

The signer signs a message using the private key as follows.

She first undertakes the computation specified in the first round of Protocol 1

to obtain She obtains the challenge by giving M

and her first-round values to the random oracle:

She then undertakes the computation specified in the third round of the protocol

using the challenge value to obtain Finally, she outputs the

signature computed as

The verifier uses equations (1“5) to re-derive and

He then checks that these, along with the other first-round messages included

in give the challenge i.e., that

He accepts if this check succeeds.

The Fiat-Shamir heuristic shows that this signature scheme is secure against

existential forgery in the random oracle model [1]. Note that a signature com-

prises three elements of and six of

6 Short Group Signatures from SDH

The signature scheme presented in Sect. 5 is, in fact, also a group signature

scheme. In describing the scheme, we follow the definitions given by Bellare

et al. [6].

Consider bilinear groups and with respective generators and

as in Sect. 2. Suppose further that the SDH assumption holds on

and the Linear assumption holds on The scheme employs a hash function

treated as a random oracle in the proof of security.

This randomized algorithm takes as input a parameter the

number of members of the group, and proceeds as follows. Select

and and set such that Select

and set Using generate for each user

an SDH tuple select and set The group

public key is The private key of the group manager

(the party able to trace signatures) is Each user™s private

key is her tuple No party is allowed to possess it is only

known to the private-key issuer.

TEAM LinG

Short Group Signatures 49

Given a group public key a

user™s key and a message compute and out-

put a signature of knowledge as in the

scheme of Sect. 5 (Equation (7)).

Given a group public key a mes-

sage M, and a group signature verify that is a valid signature of knowl-

edge in the scheme of Sect. 5 (Equation (8)).

This algorithm is used for tracing a signature to a

signer. It takes as input a group public key and

the corresponding group manager™s private key together

with a message M and a signature to

trace, and proceeds as follows. First, verify that is a valid signature on M.

Second, consider the first three elements as a Linear encryption,

and recover the user™s A as following the decryption

algorithm given at the end of Sect. 3.2. If the group manager is given the

elements of the users™ private keys, he can look up the user index

corresponding to the identity A recovered from the signature.

Signature Length. A group signature in the system above comprises three ele-

ments of and six elements of Using any of the families of curves described

in [9], one can take to be a 170-bit prime and use a group where each ele-

ment is 171 bits. Thus, the total group signature length is 1533 bits or 192 bytes.

With these parameters, security is approximately the same as a standard 1024-

bit RSA signature, which is 128 bytes.

Performance. The pairings and can be precomputed

and cached by both signers and verifiers. The signer can cache and, when

signing, compute without evaluating a pairing. Accordingly, creating a

group signature requires eight exponentiations (or multi-exponentiations) and

no pairing computations. The verifier can derive efficiently by collapsing the

and pairings into a single term. Thus verifying a

group signature requires six multi-exponentiations and one pairing computation.

With parameters selected as above, the exponents are in every case 170-bit

numbers. For the signer, all bases for exponentiation are fixed, which allows

further speedup by precomputation.

6.1 Group Signature Security

We now turn to proving security of the system. Bellare et al. [6] give three

properties that a group signature scheme must satisfy:

correctness, which ensures that honestly-generated signatures verify and

trace correctly;

full-anonymity, which ensures that signatures do not reveal their signer™s

identity; and

full-traceability, which ensures that all signatures, even those created by the

collusion of multiple users and the group manager, trace to a member of the

forging coalition.

TEAM LinG

50 Dan Boneh, Xavier Boyen, and Hovav Shacham

For the details of the definitions, see Bellare et al. [6]. We prove the security

of our scheme using a variation of these properties. In our proofs, we relax the

full-anonymity requirement. As presented [6, Sect. 2], the full-anonymity exper-

iment allows the adversary to query the opening (tracing) oracle before and

after receiving the challenge In this respect, the experiment mirrors the indis-

tinguishability experiment against an adaptive CCA2 adversary. We therefore

rename this experiment CCA2-full-anonymity. We define a corresponding exper-

iment, CPA-full-anonymity, in which the adversary cannot query the opening

oracle. We prove privacy in this slightly weaker model.

Access to the tracing functionality will likely be carefully controlled when

group signatures are deployed, so CPA-full-anonymity is a reasonable model to

consider. In any case, anonymity and unlinkability, the two traditional group

signature security requirements implied by full anonymity [6, Sect. 3], also fol-

low from CPA-full-anonymity. Thus a fully-traceable and CPA-fully-anonymous

group signature scheme is still secure in the traditional sense.

In the statements of the theorem, we use big-O notation to elide the specifics

of additive terms in time bounds, noting that, for given groups and

operations such as sampling, exponentiation, and bilinear map evaluation are all

constant-time.

Theorem 2. The SDH group signature scheme is correct.

Proof. For any group public key and for any user with

key the key generation algorithm guarantees that

so is an SDH tuple for A correct group signature is a

proof of knowledge, which is itself a transcript of the SDH protocol given in

Sect. 4. Verifying the signature entails verifying that the transcript is correct;

thus Lemma 1 shows that will always be accepted by the verifier.

Moreover, an honest signer outputs, as the first three components of any

signature values for some These

values form a Linear encryption of under public key which the group

manager, possessing the corresponding private key can always recover.

Therefore any valid signature will always be opened correctly.

Theorem 3. If Linear encryption is secure on then the

SDH group signature scheme is where and

Here is the number of hash function queries made by the

adversary and is the number of members of the group.

Proof. Suppose is an algorithm that the anonymity of the

group signature scheme. We show how to construct a algorithm

that breaks the semantic security of Linear encryption (Sect. 3.2) with advantage

at least

Algorithm is given a Linear encryption public key It generates the

remaining components of the group signature public key by following the group

signature™s key generation algorithm. It then provides to the group public

key and the users™ private keys

TEAM LinG

Short Group Signatures 51

At any time, can query the random oracle H. Algorithm responds with

elements selected uniformly at random from making sure to respond identi-

cally to repeated queries.

Algorithm requests its full-anonymity challenge by providing two indices,

and and a message M. Algorithm in turn, requests its indistinguishabil-

ity challenge by providing the two user private keys and as the messages

whose Linear encryption it must distinguish. It is given a Linear encryption

of where bit is chosen by the Linear encryption challenger.

Algorithm generates from this Linear encryption a protocol transcript

by means of the simulator of

Lemma 2. This simulator can generate a trace given even though

does not know or Since is a random Linear encryption of

the remainder of the transcript is distributed exactly as in a real protocol

with a prover whose secret A is

Algorithm then patches H at to equal

It encounters a collision only with negligible probability. In case of a collision,

declares failure and exits. Otherwise, it returns the valid group signature

to

Finally, outputs a bit Algorithm returns as the answer to its own

challenge. Since the encryption of is turned by into a group signature by

user answers its challenge correctly whenever does.

The keys given to and the answers to queries, are all valid and properly

distributed. Therefore succeeds in breaking the anonymity of the group signa-

ture with advantage and succeeds in distinguishing the Linear encryption

with the same advantage.

Algorithm running time exceeds by the amount it takes to answer

queries. Each hash query can be answered in constant time, and there are at

most of them. Algorithm can also create the challenge group signature

in constant time. If runs in time runs in time

The following theorem proves full traceability of our system. The proof is

based on the forking lemma [24] and is given in the full version of the paper.

Theorem 4. If SDH is on then the SDH group signature

scheme is where

and Here is the number of hash function queries made by the

adversary, is the number of signing queries made by the adversary, and is

the number of members of the group.

7 Revocation

We now discuss how to revoke users in the SDH group signature scheme of

Sect. 6. A number of revocation mechanisms for group signatures have been

proposed [4,12]. All these mechanisms can be applied to our system. Here we

describe a revocation mechanism along the lines of [12].

Recall that the group™s public key in our system is where

for random and random User private key

is a pair where

TEAM LinG

52 Dan Boneh, Xavier Boyen, and Hovav Shacham

Now, suppose we wish to revoke users without affecting the signing

capability of other users. To do so, the Revocation Authority (RA) publishes

a Revocation List (RL) containing the private keys of all revoked users. More

precisely, where Note that

Here the SDH secret is needed to compute the In the case

where equals then and consequently the Revocation List can be

derived directly from the private keys of revoked users without having to use

The list RL is given to all signers and verifiers in the system. It is used to

update the group public key used to verify signatures. Let

The new public key is where and

We show that, given RL, anyone can compute this new public key,

and any unrevoked user can update her private key locally so that it is well

formed with respect to this new public key. Revoked users are unable to do so.

We show how to revoke one private key at a time. By repeating the process

times (as the revocation list grows over time) we can revoke all private keys on

the Revocation List. We first show how given the public key

and one revoked private key anyone can construct the new public

key where and This

new public key is constructed simply as:

then and

as required.

Next, we show how unrevoked users update their own private keys. Con-

sider an unrevoked user whose private key is Given a revoked private

key, the user computes and sets his new

private key to be Then, indeed,

as required. Hence, is a valid private key with respect to

By repeating this process times (once for each revoked key in RL) anyone

can compute the updated public key defined above. Similarly,

an unrevoked user with private key can compute his updated private key

where We note that it is possible to process the entire

RL at once (as opposed to one element at a time) and compute

directly; however this is less efficient when keys are added to RL incrementally.

A revoked user cannot construct a private key for the new public key

In fact, the proof of Theorem 4 shows that, if a revoked user can generate

signatures for the new public key then that user can be used

to break the SDH assumption. Very briefly, the reason is that given an SDH

challenge one can easily generate a public key tuple along with

the private key for a revoked user Then an algorithm that can forge

signatures given these two tuples can be used to solve the SDH challenge.

TEAM LinG

Short Group Signatures 53

Brickell [11] proposes an alternate mechanism where revocation messages are

only sent to signature verifiers, so that there is no need for unrevoked signers to

update their keys. Similar mechanisms were also considered by Ateniese et al. [4]

and Kiayias et al. [19]. We refer to this as Verifier-Local Revocation (VLR) group

signatures. Boneh and Shacham [10] show how to modify our group signature

scheme to support this VLR revocation mechanism.

8 Exculpability

In Bellare et al. [6], exculpability (introduced by Ateniese and Tsudik [3]) is

informally defined as follows: No member of the group and not even the group

manager “ the entity that is given the tracing key “ can produce signatures on

behalf of other users. Thus, no user can be framed for producing a signature

he did not produce. They argue that a group signature secure in the sense of

full-traceability also has the exculpability property. Thus, in the terminology of

Bellare et al. [6], our group signature has the exculpability property.

A stronger notion of exculpability is considered in Ateniese et al. [2], where

one requires that even the entity that issues user keys cannot forge signatures

on behalf of users. Formalizations of strong exculpability have recently been

proposed by Kiayias and Yung [20] and by Bellare, Shi, and Zhang [7].

To achieve this stronger property the system of Ateniese et al. [2] uses a

protocol (called JOIN) to issue a key to a new user. At the end of the protocol,

the key issuer does not know the full private key given to the user and therefore

cannot forge signatures under the user™s key.

Our group signature scheme can be extended to provide strong exculpabil-

ity using a similar mechanism. Instead of simply giving user the private key

the user and key issuer engage in a JOIN protocol where at the end

of the protocol user has a triple such that for some

public parameter The value is chosen by the user and is kept secret from

the key issuer. The ZKPK of Sect. 4 can be modified to prove knowledge of such a

triple. The resulting system is a short group signature with strong exculpability.

9 Conclusions

We presented a group signature scheme based on the Strong Diffie-Hellman

(SDH) and Linear assumptions. The signature makes use of a bilinear map

When any of the curves described in [9] are used, the

group has a short representation and consequently we get a group signature

whose length is under 200 bytes “ less than twice the length of an ordinary RSA

signature (128 bytes) with comparable security. Signature generation requires no

pairing computations, and verification requires a single pairing; both also require

a few exponentiations with short exponents.

Acknowledgments

The authors thank the anonymous referees for their valuable feedback.

TEAM LinG

Dan Boneh, Xavier Boyen, and Hovav Shacham

54

References

1. M. Abdalla, J. An, M. Bellare, and C. Namprempre. From identification to sig-

natures via the Fiat-Shamir transform: Minimizing assumptions for security and

forward-security. In L. Knudsen, editor, Proceedings of Eurocrypt 2002, volume

2332 of LNCS, pages 418“33. Springer-Verlag, May 2002.

2. G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably

secure coalition-resistant group signature scheme. In M. Bellare, editor, Proceedings

of Crypto 2000, volume 1880 of LNCS, pages 255“70. Springer-Verlag, Aug. 2000.

3. G. Ateniese and G. Tsudik. Some open issues and directions in group signatures. In

Proceedings of Financial Cryptography 1999, volume 1648, pages 196“211. Springer-

Verlag, Feb. 1999.

4. G. Ateniese, G. Tsudik, and D. Song. Quasi-efficient revocation of group signatures.

In M. Blaze, editor, Proceedings of Financial Cryptography 2002, Mar. 2002.

5. N. Baric and B. Pfitzman. Collision-free accumulators and fail-stop signature

schemes without trees. In Proceedings of Eurocrypt 1997, pages 480“494. Springer-

Verlag, May 1997.

6. M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures:

Formal definitions, simplified requirements, and a construction based on general

assumptions. In E. Biham, editor, Proceedings of Eurocrypt 2003, volume 2656 of

LNCS, pages 614“29. Springer-Verlag, May 2003.

7. M. Bellare, H. Shi, and C. Zhang. Foundations of group signatures: The case

of dynamic groups. Cryptology ePrint Archive, Report 2004/077, 2004. http:

//eprint.iacr.org/.

8. D. Boneh and X. Boyen. Short signatures without random oracles. In C. Cachin

and J. Camenisch, editors, Proceedings of Eurocrypt 2004, LNCS, pages 56“73.

Springer-Verlag, May 2004.

9. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing.

In Proceedings of Asiacrypt 2001, volume 2248 of LNCS, pages 514“32. Springer-

Verlag, Dec. 2001. Full paper: http://crypto.stanford.edu/˜dabo/pubs.html.

10. D. Boneh and H. Shacham. Group signatures with verifier-local revocation, 2004.

Manuscript.

11. E. Brickell. An efficient protocol for anonymously providing assurance of the con-

tainer of a private key, Apr. 2003. Submitted to the Trusted Computing Group.

12. J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to ef-

ficient revocation of anonymous credentials. In M. Yung, editor, Proceedings of

Crypto 2002, volume 2442 of LNCS, pages 61“76. Springer-Verlag, Aug. 2002.

13. J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials

from bilinear maps. In M. Franklin, editor, Proceedings of Crypto 2004, LNCS.

Springer-Verlag, Aug. 2004.

14. D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, editor, Proceedings

of Eurocrypt 1991, volume 547 of LNCS, pages 257“65. Springer-Verlag, 1991.

15. X. Ding, G. Tsudik, and S. Xu. Leak-free group signatures with immediate revo-

cation. In T. Lai and K. Okada, editors, Proceedings of ICDCS 2004, Mar. 2004.

16. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification

and signature problems. In A. M. Odlyzko, editor, Proceedings of Crypto 1986,

volume 263 of LNCS, pages 186“194. Springer-Verlag, Aug. 1986.

17. T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum, and D. Boneh. Terra: A virtual

machine-based platform for trusted computing. In Proceedings of SOSP 2003, pages

193“206, Oct. 2003.

TEAM LinG

Short Group Signatures 55

18. IEEE P1556 Working Group, VSC Project. Dedicated short range communications

(DSRC), 2003.

19. A. Kiayias, Y. Tsiounis, and M. Yung. Traceable signatures. In C. Cachin and

J. Camenisch, editors, Proceedings of Eurocrypt 2004, volume 3027 of LNCS, pages

571“89. Springer-Verlag, May 2004.

20. A. Kiayias and M. Yung. Group signatures: Efficient constructions and anonymity

from trapdoor-holders. Cryptology ePrint Archive, Report 2004/076, 2004. http:

//eprint.iacr.org/.

21. A. Lysyanskaya, R. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In H. Heys

and C. Adams, editors, Proceedings of SAC 1999, volume 1758 of LNCS, pages

184“99. Springer-Verlag, Aug. 1999.

22. S. Mitsunari, R. Sakai, and M. Kasahara. A new traitor tracing. IEICE Trans.

Fundamentals, E85-A(2):481“4, Feb. 2002.

23. A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic

curve traces for FR-reduction. IEICE Trans. Fundamentals, E84-A(5):1234“43,

May 2001.

24. D. Pointcheval and J. Stern. Security arguments for digital signatures and blind

signatures. J. Cryptology, 13(3):361“96, 2000.

25. K. Rubin and A. Silverberg. Supersingular Abelian varieties in cryptology. In

M. Yung, editor, Proceedings of Crypto 2002, volume 2442 of LNCS, pages 336“53.

Springer-Verlag, Aug. 2002.

26. C. Schnorr. Efficient signature generation by smart cards. J. Cryptology, 4(3):161“

174, 1991.

27. V. Shoup. Lower bounds for discrete logarithms and related problems. In W. Fumy,

editor, Proceedings of Eurocrypt 1997, volume 1233 of LNCS, pages 256“66.

Springer-Verlag, May 1997.

28. Trusted Computing Group. Trusted Computing Platform Alliance (TCPA) Main

Specification, 2003. Online: www.trustedcomputinggroup.org.

29. G. Tsudik and S. Xu. Accumulating composites and improved group signing. In

C. S. Laih, editor, Proceedings of Asiacrypt 2003, volume 2894 of LNCS, pages

269“86. Springer-Verlag, Dec. 2003.

TEAM LinG

Signature Schemes and Anonymous Credentials

from Bilinear Maps

Jan Camenisch1 and Anna Lysyanskaya2

1

IBM Research, Zurich Research Laboratory, CH“8803 Rüschlikon

jca@zurich.ibm.com

2

Computer Science Department, Brown University, Providence, RI 02912, USA

anna@cs.brown.edu

Abstract. We propose a new and efficient signature scheme that is prov-

ably secure in the plain model. The security of our scheme is based on a

discrete-logarithm-based assumption put forth by Lysyanskaya, Rivest,

Sahai, and Wolf (LRSW) who also showed that it holds for generic groups

and is independent of the decisional Diffie-Hellman assumption. We prove

security of our scheme under the LRSW assumption for groups with bi-

linear maps. We then show how our scheme can be used to construct

efficient anonymous credential systems as well as group signature and

identity escrow schemes. To this end, we provide efficient protocols that

allow one to prove in zero-knowledge the knowledge of a signature on a

committed (or encrypted) message and to obtain a signature on a com-

mitted message.

1 Introduction

Digital signatures schemes, invented by Diffie and Hellman [20], and formalized

by Goldwasser, Micali and Rivest [26], not only provide the electronic equivalent

of signing a paper document with a pen but also are an important building block

for many cryptographic protocols such as anonymous voting schemes, e-cash, and

anonymous credential schemes, to name just a few.

Signature schemes exists if and only if one-way functions exist [32,35]. How-

ever, the efficiency of these general constructions, and also the fact that these

signature schemes require the signer™s secret key to change between invocations

of the signing algorithm, makes these solutions undesirable in practice.

Using an ideal random function (this is the so-called random-oracle model),

several, much more efficient signature schemes were shown to be secure. Most

notably, those are the RSA [34], the Fiat-Shamir [21], and the Schnorr [36]

signature schemes. However, ideal random functions cannot be implemented in

the plain model [13,25], and therefore in the plain model, these signature schemes

are not provably secure.

Over the years, many researchers have come up with signature schemes that

are efficient and at the same time provably secure in the plain model. The most

efficient ones provably secure in the standard model are based on the strong RSA

assumption [23,19,22,10]. However, no scheme based on an assumption related

to the discrete logarithm assumption in the plain (as opposed to random-oracle)

model comes close to the efficiency of these schemes.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 56“72, 2004.

© International Association for Cryptologic Research 2004

TEAM LinG

Signature Schemes and Anonymous Credentials from Bilinear Maps 57

In this paper, we propose a new signature scheme that is based on an assump-

tion introduced by Lysyanskaya, Rivest, Sahai, and Wolf [30] and uses bilinear

maps. This assumption was shown to hold for generic groups [30], and be in-

dependent of the decisional Diffie-Hellman assumption. Our signature scheme™s

efficiency is comparable to the schemes mentioned above that are based on the

Strong RSA assumption.

We further extend our basic signature scheme such that it can be used as a

building block for cryptographic protocols. To this end, we provide protocols to

prove knowledge of a signature on a committed message and to obtain a signa-

ture on a committed message. These protocols yield a group signature scheme

[17] or an anonymous credential system [14] (cf. [10]). That is, we obtain the

first efficient and secure credential system and group signature/identity escrow

schemes [28] that are based solely on discrete-logarithm-related assumptions.

We should mention that an anonymous credential system proposed by Verheul

[38] is also only based on discrete logarithm related assumptions; however, the

scheme is not proven secure. Also note that the recent scheme by Ateniese and de

Medeiros [2] requires the strong RSA assumption although no party is required

to know an RSA secret key during the operation of the system.

Note that not only are our group signature and anonymous credential schemes

interesting because they are based on a different assumption, but also because

they are much more efficient than any of the existing schemes. All prior schemes

[1,9,10,2] required proofs of knowledge of representations over groups modulo

large moduli (for example, modulo an RSA modulus, whose recommended length

is about 2K Bits).

Recently, independently from our work, Boneh and Boyen [4] put forth a

signature scheme that is also provably secure under a discrete-logarithm-type

assumption about groups with bilinear maps. In contrast to their work, our

main goal is not just an efficient signature scheme, but a set of efficient pro-

tocols to prove knowledge of signatures and to issue signatures on committed

(secret) messages. Our end goal is higher-level applications, i.e., group signature

and anonymous credential schemes that can be constructed based solely on an

assumption related to the discrete logarithm assumption.

In another recent independent work, Boneh, Boyen, and Shacham [5] con-

struct a group signature scheme based on different discrete-logarithm-type as-

sumptions about groups with bilinear pairings. Their scheme yields itself to the

design of a signature scheme with efficient protocols as well. In §5 we describe

their scheme and its connection to our work in more detail.

Outline of the Paper. In §2 we give our notation and some number-theoretic

preliminaries, including bilinear maps and the LRSW assumption. In §3, we

give our signature scheme and prove it secure. In §4 we show how our signature

yields itself to the design of an anonymous credential system: we give protocols

for obtaining a signature on a committed value, and for proving knowledge of a

signature on a committed value. In the end of that section, we show how to realize

a group signature scheme based on our new signature. Finally, in Section 5, we