[4] Karnin, E.D., J.W. Greene, and M.E. Hellman

(1983). “On secret sharing systems.” IEEE Trans-

In the late 1990™s it was realized that by mak-

actions on Informatiom Theory, 29 (1), 231“

241. ing a somewhat stronger intractability assump-

[5] Capocelli, R.M., A. De Santis, L. Gargano, and U. tion than RSA (see RSA problem), it is possible to

Vaccaro (1993). “On the size of shares for secret devise digital signature schemes that are fairly ef-

sharing schemes.” Journal of Cryptology, 6, 157“ ¬cient, and at the same time have a rigorous proof

167.

of security (without resorting to the random-oracle

[6] Brickell, E.F. and D.M. Davenport (1991). “On

heuristic). The intractability assumption states

the classi¬cation of ideal secret sharing schemes.”

that given a modulus n (see modular arithmetic)

Journal of Cryptology, 4, 123“134.

of unknown factorization and an element x in the

[7] Blakley, G.R. and G.A. Kabatianski (1997). “Gener-

—

ring Zn , it is hard to come up with an exponent

alized ideal secret sharing schemes and matroids.”

—

e ≥ 2 and an element y in Zn , such that ye = x

Problems of Information Transmission, 33 (3), 102“

(mod n). This assumption, ¬rst used by Bari´ and c

110.

[8] Kurosawa, K., K. Okada, K. Sakano, W. Ogata, P¬tzmann in the context of fail-stop signatures

and S. Tsujii (1993). “Nonperfect secret sharing [1], is called the strong RSA assumption (or the

schemes and matroids.” Advances in Cryptology” ¬‚exible RSA assumption).

EUROCRYPT™93, Lecture Notes in Computer Sci- A simple way of using this assumption for signa-

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

tures was described by Gennaro et al. [7]. In their

Berlin, 126“141.

construction, the public key (see public key crypto-

[9] Jackson, W.-A. and K.M. Martin (1998). “Combina-

graphy) is a triple (n, x, H), where n is product of

torial models for perfect secret sharing schemes.”

two “quasi-safe primes”, x is a random element in

Journal of Combinatorial Mathematics and Com-

—

Zn , and H is a hash function, mapping strings to

binatorial Computing, 28, 249“265.

odd integers. The secret key consists of the fac-

[10] Welsh, D.J.A. (1976). Matroid Theory. Academic

torization of n. To sign a message m, the signer

Press, New York.

picks a random string r, computes e ← H(m, r ),

[11] Csirmaz, L. (1995). “The size of a share must be

large.” Advances in Cryptology”EUROCRYPT™94, and then, using the factorization of n, ¬nds an el-

—

Lecture Notes in Computer Science, vol. 950, ed. A. ement y ∈ Zn such that ye = x (mod n). To verify a

De Santis. Springer-Verlag, Berlin, 13“22. signature (r, y) on message m, the veri¬er checks

[12] Blakley, G.R. and G.A. Kabatianski (1994). “Linear

that y H(m,r ) = x (mod n).

algebra approach to secret sharing schemes.” Er-

Gennaro et al. proved that this scheme is

ror Control, Cryptology and Speech Compression,

secur”in the sense of existential unforgeability

Lecture Notes in Computer Science, vol. 829, eds.

(see also existential forgery) under an adaptive

A. Chmora, and S.B. Wicker. Springer, Berlin, 33“

chosen message attack (EU-CMA)”under some

40.

conditions on the function H. The ¬rst condi-

[13] van Dijk, M. (1995). “A linear construction of

tion is that H is division intractable. This means

perfect secret sharing schemes.” Advances in

Cryptology”EUROCRYPT™94, Lecture Notes in that it is hard to come up with a list of pairs,

(mi , ri ), i = 1, . . . , t, where the integer H(mt , rt ) di-

Computer Science, vol. 950, ed. A. De Santis.

Springer-Verlag, Berlin, 23“34. t=1

vides the product i=1 H(mi , ri ). The other con-

[14] McEliece, R.J. and D.V. Sarwate (1981). “On se-

dition on H means, informally, that one cannot

cret sharing and Reed“Solomon codes.” Communi-

reduce breaking the strong RSA assumption to

cations of the ACM, 24, 583“584.

“breaking the hash function H”. It is shown in [7]

[15] Ashihmin, A. and J. Simonis (1998). “Almost af¬ne

that hash functions satisfying these conditions ex-

codes.” Designs, Codes and Cryptography, 14 (2),

ist if the strong RSA assumption holds. (It is also

179“197.

shown in [7] that if H is modeled as a random

[16] Massey, J. (1993). “Minilal codewords and se-

oracle, then it satis¬es these conditions, provided

cret sharing.” Proceedings of Sixth Joint Swedish“

Secure signatures from the “strong RSA” assumption 547

that its output is suf¬ciently long. However, Coron scheme maintains in the public key a list of t odd

primes e1 , . . . , et , and can be used to generate upto

and Naccache showed in [2] that the output of

H in this case should be at least as long as the t signatures, using a different prime each time.

modulus n.) The Cramer-Shoup scheme is obtained essentially

Cramer and Shoup [4], followed by Fischlin [6], by letting the signer choose the odd primes “on the

proposed more ef¬cient signatures based on the ¬‚y” instead of committing to them ahead of time

strong RSA assumption. In the Cramer“Shoup in the public key. One pays for this ¬‚exibility by

public key scheme, the public key is a 5-tuple having to make a stronger intractability assump-

(n, h, x, e , H), where n is a product of two “safe tion. Since the attacker can now choose the ex-

primes”, h, x are random quadratic residues in ponent e relative to which it issues the forgery,

—

Zn , e is an odd prime, and H is a hash func- one has to assume the strong RSA assumption

tion, mapping strings to integers. If denotes (whereas the standard RSA assumption suf¬ces

˚

the output length of H, then the prime e must for the Cramer“Damgard scheme.)

be at least ( + 1)-bit long. The secret key con- A curious feature of the Cramer-Shoup and

sists of the factorization of n. To sign a mes- Fischlin schemes (as well as some instances of

sage m, the signer picks a new ( + 1)-bit prime the Gennaro“Halevi“Rabin scheme) is that when

—

e = e and a random quadratic residue y ∈ Zn , sets there is an a-priori polynomial bound on the total

x ← (y )e h’H(m) (mod n), and then, using the fac- number of signatures to be made, the signer can

—

torization of n, ¬nds an element y ∈ Zn such that generate its public/private key pair even without

ye = xh H(x ) (mod n). To verify a signature (e, y, y ) knowing the factorization of the modulus n. (This

on message m, the veri¬er checks that e is an is done using the same strategy as the simulator in

odd ( + 1)-bit number, e = e , sets x ← (y )e h’H(m) the security proof of these schemes.) That makes

(mod n), and checks that ye = xh H(x ) (mod n). it possible in some cases to have many users in a

In the scheme of Fischlin, the public key is a system, all sharing the same modulus n.

5-tuple (n, g, h, x, H), where n, h, x, H are as in

Dan Boneh

the Cramer“Shoup scheme, and g is yet another

—

random quadratic residue in Zn . Again, the se-

References

cret key is the factorization of n, and we use

to denote the output length of H. To sign a mes-

[1] Bari´ , N. and B. P¬tzmann (1997). “Collision-free ac-

c

sage m, the signer picks a new ( + 1)-bit prime e cumulators and fail-stop signature schemes without

and a random -bit string ±, and then, using the trees.” Advances in Cryptology”EUROCRYPT™97,

—

factorization of n, ¬nds an element y ∈ Zn such Lecture Notes in Computer Science, vol. 1233, ed.

that ye = xg± h±•H(m) (mod n). To verify a signature W. Fumy. Springer-Verlag, Berlin, 480“494.

(e, ±, y) on message m, the veri¬er checks that e is [2] Coron, J.S. and D. Naccache (2000). “Security

an odd ( + 1)-bit number, that ± is an -bit string, analysis of the Gennaro“Halevi“Rabin signature

and that ye = xg± h±•H(m) (mod n). Fischlin also scheme.” Advances in Cryptology”EUROCRYPT

2000, Lecture Notes in Computer Science, vol. 1807,

proposed other variations of this scheme, where

ed. B. Preneel. Springer-Verlag, Berlin, 91“101.

the prime e can be chosen even shorter than + 1

˚

[3] Cramer, R. and I.B. Damgard (1996). “New gen-

bits (and the computation made slightly more ef-

erations of secure and practical RSA-based signa-

¬cient), at the price of a longer public key.

tures.” Advances in Cryptology”CRYPTO™96, Lec-

For all of these schemes, it is proved that they ture Notes in Computer Science, vol. 1109, ed. N.

are secure (in the sense of EU-CMA), assum- Koblitz. Springer-Verlag, Berlin, 173“186.

ing the strong RSA assumption and the collision- [4] Cramer, R. and V. Shoup (2000). “Signature schemes