References

three general types of challenge values that might

be used. The property of each is that the challenge

[1] Abdalla, M., J. An, M. Bellare, and C. Namprempre

value is not repeatedly sent to multiple claimants.

(2002). “From identi¬cation to signatures via the

Such a value is sometimes referred to as a nonce,

¬at-shamir transform: Minimizing assumptions

since it is a value that is “not used more than

for security and forward-security.” Advances in

Cryptology”EUROCRYPT 2004, Lecture Notes in once.” The challenge value could be a randomly

Computer Science, vol. 2332, ed. Lars Knudsen. generated value (see Random bit generation), in

Springer-Verlag, Berlin, 418“33. which case V would send a random value c to C.

[2] Fiat, Amos and Adi Shamir (1986). “How to prove Alternatively, the challenge value might be a se-

yourself: Practical solutions to identi¬cation and

quence number, in which case the veri¬er V would

signature problems.” Advances in Cryptology”

maintain a sequence value corresponding to each

CRYPTO™86, Lecture Notes in Computer Science,

challenger. At each challenge, the stored sequence

vol. 263, ed. Andrew M. Odlyzko. Springer-Verlag,

number would be increased by (at least) one be-

Berlin, 186“194.

fore sending to the claimant. Finally, the challenge

[3] Lenstra, Arjen and Eric Verheul (2001). “Selecting

value might be a function of the current time.

cryptographic key sizes.” Journal of Cryptology, 14

In this case, a challenge value need not be sent

(4), 255“293.

Second preimage resistance 543

SEAL

from V to C, but could be sent by C, along with

the computed veri¬er. As long as the time cho-

sen was within an accepted threshold, V would SEAL stands for Software-optimized Encryption

accept. ALgorithm. It is a binary additive stream cipher

There are three general classes of functions (see the entry concerning synchronous stream

and secret values that might be used as part ciphers). It has been proposed in 1993, and several

of a challenge-response protocol. The ¬rst is versions have been published: SEAL 1.0, SEAL 2.0

symmetric-key based in which the claimant C and SEAL 3.0 [3, 4]. Some attacks have been pub-

and veri¬er V a priori share a secret key K. The lished that show how SEAL 1.0, SEAL 2.0 [2] and

function f () is a symmetric encryption function later SEAL 3.0 [1] can be distinguished from a true

(see Symmetric Cryptosystem), a hash function, random function. But there is no really practical

or a Message Authentication Code (MAC algo- attack for the moment.

rithms). Both Kerberos (see Kerberos authen- SEAL has been designed to be really ef¬cient

tication protocol) and the Needham“Schroeder in its software implementation, mainly for 32-bit

protocol are examples of symmetric-key based processors. It is a length-increasing pseudoran-

challenge-response identi¬cation. In addition, the dom function that maps a 32-bit sequence number

protocols of ISO/IEC 9798-2 perform identi¬cation n to an L-bit keystream, under control of a 160-bit

using symmetric key techniques. secret key. a more precise description can be found

Alternatively, a public key based solution may in the original papers.

be used. In this case, the claimant C has the

Caroline Fontaine

private key in a public key cryptosystem (see

Public Key Cryptography). The veri¬er V pos-

sesses a public key that allows validation of the References

public key corresponding to C™s private key. In gen-

eral, C uses public key techniques (generally based [1] Fluhrer, S.R. (2001). “Cryptanalysis of the SEAL

on number-theoretic security problems) to produce 3.0 pseudorandom function family.” FSE™01, Lecture

a value v, using knowledge of his/her private key. Notes in Computer Science, vol. 2355, ed. M. Matsui.

For example, V might encrypt a challenge value Springer-Verlag, Berlin, 135-ff.

[2] Handschuh, H. and H. Gilbert (1997). “χ 2 -

and send the encrypted text. C would decrypt the

cryptanalysis of the SEAL encryption algorithm.”

encrypted text and return the value (i.e., the recov-

FSE™97, Lecture Notes in Computer Science, vol.

ered plaintext) to V (note that in this case it would

1687, eds. O. Nierstrasz and M. Lemoine. Springer-

only be secure to use a random challenge, and not

Verlag, Berlin, 1“12.

a sequence number or time-based value). Alterna-

[3] Rogaway, P. and D. Coppersmith (1994). “A software-

tively, V might send a challenge value to C and

optimized encryption algorithm.” FSE™94, Lecture

ask C to digitally sign and return the challenge Notes in Computer Science, vol. 809, ed. R.J.

(see Digital Signature Schemes). The Schnorr Anderson. Springer-Verlag, Berlin, 56“63.

identi¬cation protocol is another example of pub- [4] Rogaway, P. and D. Coppersmith (1998). “A software-

lic key based challenge-response identi¬cation. optimized encryption algorithm.” Journal of Cryp-

Finally, a zero-knowledge protocol can be used. tology, 11 (4), 273“287.

In this case, the challenger demonstrates knowl-

edge of his/her secret value without revealing any

information (in an information theoretic sense”

SECOND PREIMAGE

see “information theoretic security” in glossary)

RESISTANCE

about this value. Such protocols typically require

a number of “rounds” (each with its own challenge

value) to be executed before a claimant may be Second preimage resistance is the property of a

successfully veri¬ed. hash function that it is computationally infeasi-

ble to ¬nd any second input that has the same

Mike Just output as a given input. This property is related

to preimage resistance and one-wayness; however,

the later concept is typically used for functions

References

with input and output domain of similar size (see

one-way function). Second preimage resistance is

[1] Menezes, A., P. van Oorschot, and S. Vanstone

also known as weak collision resistance. A min-

(1997). Handbook of Applied Cryptography. CRC

imal requirement for a hash function to be sec-

Press, Boca Raton, FL.

ond preimage resistant is that the length of its re-

[2] Stinson, D.R. (1995). Cryptography: Theory and

sult should be at least 80 bits (in 2004). A hash

Practice. CRC Press, Boca Raton, FL.

544 Secret sharing schemes

function is said to be a one-way hash function second-preimage resistance, and collision resis-

tance.” Fast Software Encryption, Lecture Notes in

(OWHF) if it is both preimage resistant and second

Computer Science, vol. 3017, eds. B.K. Roy and W.

preimage resistant. The relation between collision

Meier. Springer-Verlag, Berlin, 371“388.

resistance, second preimage resistance and preim-

[7] Stinson, D. (2001). “Some observations on the theory

age resistance is rather subtle, and it depends

of cryptographic hash functions.” Technical Report

on the formalization of the de¬nition: it is shown

2001/020, University of Waterloo.

in [6] that under certain conditions, collision [8] Zheng, Y., T. Matsumoto, and H. Imai (1990). “Con-

resistance implies second preimage resistance nections between several versions of one-way hash

and second preimage resistance implies preimage functions.” Proceedings SCIS90, The 1990 Sympo-

resistance. sium on Cryptography and Information Security,

In order to formalize the de¬nition, one needs Nihondaira, Japan, January 31“February 2.

to specify according to which distribution the ¬rst

element in the domain is selected and one needs to

express the probability of ¬nding a second preim-

SECRET SHARING

age for this element. Moreover, one often intro-

SCHEMES

duces a class of functions indexed by a public

parameter, which is called a key. One could then

Informally speaking, a secret sharing scheme

distinguish between three cases: the probability

(SSS, for short) allows one to share a secret among

can be taken over the random choice of elements

n participants in a such a way that some sets of

in the range, over the random choice of the param-

participants called allowed coalitions can recover

eter, or over both simultaneously. As most practi-

the secret exactly, while any other sets of partici-

cal hash functions have a ¬xed speci¬cation, the

pants (non-allowed coalitions) cannot get any ad-

¬rst approach is more relevant to applications.

ditional (i.e., a posteriori) information about the

The second case is known as a Universal One-Way

possible value of the secret. the SSS with the last