and linear cryptanalysis.” Fast Software Encryp-

n cryptanalysis, with applications against RC5P

tion, Third International Workshop, Cambridge,

and M6.” Fast Software Encryption, Sixth Inter-

UK, February 1996, Lecture Notes in Computer

national Workshop, Rome, Italy, March 1999, Lec-

Science, vol. 1039, ed. D. Gollman. Springer-Verlag,

ture Notes in Computer Science, vol. 1636, ed. L.

Berlin, 205“218.

Knudsen. Springer-Verlag, Berlin, 139“155.

[33] Matsui, M. (1997). “New block encryption algo-

[20] Kilian, J. and P. Rogaway (1996). “How to protect

rithm MISTY.” Fast Software Encryption, Fourth

DES against exhaustive key search.” Advances in

International Workshop, Haifa, Israel, January

Cryptology”CRYPTO™96, Lecture Notes in Com-

1997, Lecture Notes in Computer Science, vol.

puter Science, vol. 1109, ed. Neal Koblitz. Springer-

1267, ed. E. Biham. Springer-Verlag, Berlin, 54“

Verlag, London, 252“267.

68.

[21] Knudsen, L.R. (1994). “Block Ciphers”Analysis,

[34] Matsui, M. and A. Yamagishi (1992). “A new

Design and Applications.” PhD Thesis, Aarhus

method for known plaintext attack of FEAL ci-

University, Denmark.

pher.” Advances in Cryptology”EUROCRYPT™92,

[22] Knudsen, L.R. (1995). “Truncated and higher order

Lecture Notes in Computer Science, vol. 658, ed.

differentials.” Fast Software Encryption”Second

R. Rueppel. Springer-Verlag, Berlin, 81“91.

International Workshop, Leuven, Belgium, Lec-

[35] National Bureau of Standards (1977). “Data en-

ture Notes in Computer Science, vol. 1008, ed. B.

cryption standard.” Federal Information Process-

Preneel. Springer-Verlag, Berlin, 196“211.

ing Standard (FIPS), Publication 46, National Bu-

[23] Knudsen, L.R. and W. Meier (2001). “Correla-

reau of Standards, U.S. Department of Commerce,

tions in RC6 with a reduced number of rounds.”

Washington, DC.

Fast Software Encryption, 7th International Work-

[36] National Bureau of Standards (1980). “DES modes

shop, FSE 2000, New York, USA, April 2000, Lec-

of operation.” Federal Information Processing

ture Notes in Computer Science, vol. 1978, ed.

Standard (FIPS), Publication 81, National Bu-

B. Schneier. Springer-Verlag, Berlin, 94“108.

reau of Standards, U.S. Department of Commerce,

[24] Knudsen, L.R. and M.P.J. Robshaw (1996). “Non-

Washington, DC.

linear approximations in linear cryptanalysis.” Ad-

[37] National Institute of Standards and Technology.

vances in Cryptology”EUROCRYPT™96, Lecture

Advanced encryption algorithm (AES) develop-

Notes in Computer Science, vol. 1070, ed. U.

ment effort. http://www.nist.gov/aes

Maurer. Springer-Verlag, Berlin, 224“236.

[38] NIST (2001). “Advanced encryption standard.”

[25] Knudsen, L.R. and D. Wagner (2001). “Integral

FIPS 197, US Department of Commerce, Washing-

cryptanalysis.” FSE 2002. To appear in proceed-

ton, DC, November 2001.

ings from Springer-Verlag, Berlin.

48 Blow¬sh

32 bits 32 bits

[39] Nyberg, K. (1993). “Differentially uniform map-

pings for cryptography.” Advances in Cryptology” Pi

EUROCRYPT™93, Lecture Notes in Computer Sci-

S-box 1

ence, vol. 765, ed. T. Helleseth. Springer-Verlag,

Berlin, 55“64.

[40] Nyberg, K. and L.R. Knudsen (1993). “Provable S-box 2

32 bits

security against differential cryptanalysis.” Ad-

vances in Cryptology”CRYPTO™92, Lecture Notes S-box 3 32 bits

in Computer Science, vol. 740, ed. E.F. Brickell.

Springer-Verlag, Berlin, 566“574.

S-box 4

[41] Nyberg, K. and L.R. Knudsen (1995). “Provable se-

curity against a differential attack.” The Journal

of Cryptology, 8 (1), 27“38.

[42] Preneel, B. (1993). “Analysis and Design of Crypto-

graphic Hash Functions.” PhD Thesis, Katholieke

Universiteit Leuven.

[43] Shannon, C.E. (1949). “Communication theory of

secrecy systems.” Bell System Technical Journal,

28, 656“715. Fig. 1. One round of Blow¬sh

[44] Stinson, D.R. (1995). Cryptography”Theory and

Practice. CRC Press, Inc., Boca Raton, FL. into two 32-bits words. First, a round key is XORed

[45] Tuchman, W. (1979). “Hellman presents no short- to the left word. The result is then input to four

cut solutions to DES.” IEEE Spectrum, 16 (7), 40“

key-dependent 8 — 32-bit S-boxes, yielding a 32-

41.

bit output word which is XORed to the right word.

[46] van Oorschot, P.C. and M.J. Wiener (1996).

Both words are swapped and then fed to the next

“Improving implementable meet-in-the-middle at-

iteration.

tacks of orders of magnitude.” Advances in

The use of key-dependent S-boxes distinguishes

Cryptology”CRYPTO™96, Lecture Notes in Com-

Blow¬sh from most other ciphers, and requires

puter Science, vol. 1109, ed. Neal Koblitz. Springer-

a rather complex key-scheduling algorithm. In

Verlag, Berlin, 229“236.

[47] Vaudenay, S. (1995). “An experiment on DES” a ¬rst pass, the lookup tables determining the

S-boxes are ¬lled with digits of π, XORed with

Statistical cryptanalysis.” Proceedings of the 3rd

ACM Conferences on Computer Security, New bytes from a secret key which can consist of 32“

Delhi, India. ACM Press, New York, 139“147. 448 bits. This preliminary cipher is then used to

[48] Vaudenay, S. (1998). “Provable security for block ci-

generate the actual S-boxes. Although Blow¬sh

phers by decorrelation.” STACS™98, Lecture Notes

is one of the faster block ciphers for suf¬ciently

in Computer Science, vol. 1373, eds. M. Morvan,

long messages, the complicated initialization pro-

C. Meinel, and D. Krob. Springer-Verlag, Berlin,

cedure results in a considerable ef¬ciency degra-

249“275.

dation when the cipher is rekeyed too frequently.

[49] Vaudenay, S. (1999). “Resistance against general

The need for a more ¬‚exible key schedule was one

iterated attacks.” Advances in Cryptology”EURO-

of the factors that in¬‚uenced the design of Two¬sh,

CRYPT™99, Lecture Notes in Computer Science,

vol. 1592, ed. J. Stem. Springer-Verlag, Berlin. an Advanced Encryption Standard (see Rijndael/

[50] Wagner, D. (1999). “The boomerang attack.” Fast AES) ¬nalist which was inspired by Blow¬sh.

Software Encryption, Sixth International Work- Since the publication of Blow¬sh, only a few

shop, Rome, Italy, March 1999, Lecture Notes in cryptanalytical results have been published. A

Computer Science, vol. 1636, ed. L.R. Knudsen.

¬rst analysis was made by Vaudenay [4], who re-

Springer-Verlag, Berlin 156“170.

vealed classes of weak keys for up to 14 rounds

of the cipher. Rijmen [2] proposed a second-

order differential attack on a four-round variant of

Blow¬sh. In a paper introducing slide attacks [1],

BLOWFISH Biryukov and Wagner highlighted the importance

of XORing a different subkey in each round of

Blow¬sh [3] is a 64-bit block cipher designed by

Blow¬sh.

Bruce Schneier and published in 1994. It was in-

tended to be an attractive alternative to DES (see Christophe De Canni` re

e

Data Encryption Standard) or IDEA. Today, the

References

Blow¬sh algorithm is widely used and included

in many software products.

Blow¬sh consists of 16 Feistel-like iterations. [1] Biryukov, A. and D. Wagner (1999). “Slide attacks.”

Each iteration operates on a 64-bit datablock, split Proceedings of Fast Software Encryption”FSE™99,

BLS short digital signatures 49

Output (g, y, H) as the public key and (g, ±, H)

Lecture Notes in Computer Science, vol. 1636, ed.

L.R. Knudsen. Springer-Verlag, Berlin, 245“259. as the private key.

Signing. To sign a message m ∈ {0, 1}— using the

[2] Rijmen, V. (1997). “Cryptanalysis and Design of It-

private key (g, ±, H) output H(m)± ∈ G as the

erated Block Ciphers.” PhD Thesis, Katholieke Uni-

versiteit Leuven. signature.

[3] Schneier, B. (1994). “Description of a new variable-

Verifying. To verify a message/signature pair

length key, 64-bit block cipher (Blow¬sh).” Fast

(m, s) ∈ {0, 1}— — G using the public key

Software Encryption, FSE™93, Lecture Notes in

(g, y, H) test if e(g, s) = e(y, H(m)). If so, accept

Computer Science, vol. 809, ed. R.J. Anderson.

the signature. Otherwise, reject.

Springer-Verlag, Berlin, 191“204.

For a valid message/signature pair (m, s)

[4] Vaudenay, S. (1996). “On the weak keys of Blow¬sh.”

we have that s = H(m)± and therefore e(g, s) =

Fast Software Encryption, FSE™96, Lecture Notes

e(g, H(m)± ) = e(g±, H(m)) = e(y, H(m)). The second

in Computer Science, vol. 1039, ed. D. Gollmann.

Springer-Verlag, Berlin, 27“32. equality follows from the bilinearity of e(, ). Hence,

a valid signature is always accepted. As mentioned

above, the system is existentially unforgeable un-

der a chosen message attack in the random or-

BLS SHORT DIGITAL acle model, assuming the computational Dif¬e“

SIGNATURES Hellman assumption holds in G. Observe that a

signature is a single element in G whereas DSS

signatures are pairs of elements. This explains the

It is well known that a digital signature scheme

reduction in signature length compared to DSS.

that produces signatures of length can have se-

Recently, Boneh and Boyen [1] and Zhang

curity at most 2 . In other words, it is possible to

et al. [4] describe a more ef¬cient system produc-

forge a signature on any message in time O(2 ) just

ing signatures of the same length as BLS. How-

given the public key. It is natural to ask whether

ever, security is based on a stronger assumption.

we can construct signatures with such security,

Key generation is identical to the BLS system, ex-

i.e., signatures of length where the best algo-

cept that the hash function used is H : {0, 1}— ’

rithm for creating an existential forgery (with con-

Zq . A signature on a message m ∈ {0, 1}— is s =

stant success probability) under a chosen message

g1/(±+H(m)) ∈ G. To verify a message/signature pair

attack takes time O(2 ). Concretely, is there a sig-

(m, s) test that e(yg H(m) , s) = e(g, g). We see that

nature scheme producing 80-bit signatures where

signature length is the same as in BLS signatures.

creating an existential forgery (with probability

1/2) takes time approximately 280 ? However since e(g, g) is ¬xed, signature veri¬ca-

tion requires only one computation of the bilin-

DSS signatures and Schnorr signatures provide

ear map as opposed to two in BLS. Security of

security O(2 ) with signatures that are 4 -bits

the system in the random oracle model is based

long. These signatures can be shortened [3] to

on a nonstandard assumption called the t-Dif¬e“

about 3.5 -bits without much affect on security.

Hence, for concrete parameters, = 80, shortened Hellman-inversion assumption. Loosely speaking,

the assumption states that no ef¬cient algorithm

DSS signatures are 280-bits long. 2 t

given g, g x , g(x ) , . . . , g(x ) as input can compute

Boneh et al. [2] describe a short signature

g1/x . Here t is the number of chosen message

scheme where 170-bit signatures provide approx-

imately 280 security, in the random oracle model. queries that the attacker can make. Surprisingly,

Hence, for = 80, these signatures are approxi- a variant of this system can be shown to be existen-

tially unforgeable under a chosen message attack

mately half the size of DSS signatures with com-

without the random oracle model [1].

parable security. The system makes use of a group

G where (i) the computational Dif¬e“Hellman

Dan Boneh

problem is intractable, and (ii) there is an ef¬-

ciently computable, nondegenerate, bilinear map

References

e : G — G ’ G1 for some group G1 . There are sev-

eral examples of such groups from algebraic ge-

[1] Boneh, Dan and Xavier Boyen (2004). “Short sig-

ometry where the bilinear map is implemented

natures without random oracles.” Proceedings of

using the Weil pairing. Given such a group G of Eurocrypt 2004, Lecture Notes in Computer Sci-

prime order q, the digital signature scheme works ence, vol. 3027, eds. C. Cachin and J. Camenisch.

as follows: Springer-Verlag, Berlin, 56“73.

Key Generation. [2] Boneh, Dan, Ben Lynn, and Hovav Shacham (2004).

1. Pick an arbitrary generator g ∈ G. “Short signatures from the Weil pairing.” J. of

2. Pick a random ± ∈ {1, . . . , q} and set y = g± ∈ G. Cryptology. Extended abstract in Proceedings of

3. Let H be a hash function H : {0, 1}— ’ G. ASIACRYPT 2001, Lecture Notes in Computer

50 Blum“Blum“Shub pseudorandom bit generator

p = q = 3 mod 4. Set N = pq ∈ Z. Integers N of

Science, vol. 2248, ed. C. Boyd. Springer-Verlag,

Berlin. this type (where both prime factors are distinct

[3] Naccache, David and Jacques Stern (2000). “Signing and are 3 mod 4) are called Blum integers. Next

pick a random y in the group Z— and set s =

on a postcard.” Proceedings of Financial Cryptogra-

N

phy 2000. —

y ∈ Z N. The secret seed is (N, s). As we will see

2

[4] Zhang, Fangguo, Reihaneh Safavi-Naini, and Willy

below, there is no need to keep the number N

Susilo (2004). “An ef¬cient signature scheme from

secret.

bilinear pairings and its applications.” Proceedings

Generate. Given an input ∈ Z and a seed (N, s)

of PKC 2004.

we generate a pseudorandom sequence of length