<<

. 2
( 19)



>>

At Eurocrypt™96 Knudsen and Robshaw consider applying GLC to Feistel
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

<<

. 2
( 19)



>>