shares s1 = g(x1 ), . . . , sk’1 = g(xi ) all possible val-

Patterns for the SHA-2 Family. http://eprint.iacr

ues of s0 are equally probable, hence the scheme

.org/2004/207.

is perfect.

[5] ISO/IEC 10118-3 (2003). “Information technology”

For some applications it is convenient to have

security techniques”hash-functions”Part 3:

Dedicated hash-functions.” the maximal possible number n of participants

equal to q, especially for q = 2m . For Shamir™s

[6] Joux, A., P. Carribault, W. Jalby, and C. Lemuet

(2004). “Collisions in SHA-0.” Presented at the scheme n < q but the following simple modi¬ca-

rump session of CRYPTO 2004, August. tion allows to have n = q. Namely, the dealer gen-

[7] National Institute of Standards and Technology

erates a random polynomial of the form f (x) =

(NIST). (1995). FIPS Publication 180-1: Secure

f0 + f1 x + · · · + fk’2 x k’2 + s0 x k’1 and distribute

Hash Standard.

shares si = f (xi ), where the xi are different but not

[8] National Institute of Standards and Technology

necessary nonzero elements of GF(q). The perfect-

(NIST). (2002). FIPS Publication 180-2: Secure

ness of this scheme can be proved either directly

Hash Standard.

(along the line of the above proof by considering

[9] Saarinen, M.-J.O. (2003). “Cryptanalysis of block

the polynomial h(x) = f (x) ’ s0 x k’1 of degree at

ciphers based on SHA-1 and MD5.” Fast Software

most k ’ 2), or as an application of established

Encryption”FSE 2003, Lecture Notes in Com-

puter Science, vol. 2887, ed. Thomas Johansson. in [3] the relationship between perfect (n, k)-

Springer-Verlag, Berlin, 36“44. threshold schemes and (n + 1, k) Reed“Solomon

[10] Wang, X., Y.-L. Yin, and H. Yu (2005). Col- codes (see cyclic codes), since the above construc-

lision Search Attacks on SHA-1. Unpublished

tion is equivalent to so-called 2-lengthening of

manuscript.

Reed“Solomon codes.

Robert Blakley

Gregory Kabatiansky

SHAMIR™S THRESHOLD

SCHEME References

In [1], Shamir proposed an elegant “polyno- [1] Shamir, A. (1979). “How to share a secret.” Commu-

mial” construction of a perfect threshold schemes nications of the ACM, 22 (1), 612“613.

568 Shannon™s model

cryptanalyst

sender A encryption decryption receiver B

Ek (m) = c Dk (c) = m

m

k k

key source

secure channel

Fig. 1. The conventional cryptosystem

same key k. To this end, they use a secure chan-

[2] Blakley, R. (1979). “Safeguarding cryptographic

keys.” Proceedings of AFIPS 1979 National Com- nel, a communication line without any eavesdrop-

puter Conference, 48, 313“317. pers. A possibility is that they agreed beforehand

[3] McEliece, R.J. and D.V. Sarwate (1981). “On secret on the key, another possibility is that one has

haring and Reed“Solomon codes.” Communications sent the key by means of a courier to the other.

of the ACM, 24, 583“584.

Nowadays public key cryptography is often used

for this purpose.

Normally, the same cryptosystem E will be used

for a long time and by many people, so it is rea-

SHANNON™S MODEL sonable to assume that E is also known to the

cryptanalyst. It is the frequent changing of the key

Although symmetric cryptosystems have been that has to provide the security of the data. This

around for at least two thousand years (see for principle was already clearly stated by the Dutch-

instance Caesar cipher), it was only in 1949 that man Auguste Kerckhoff (see maxims) in the 19th

Claude Shannon gave a formal mathematical de- century.

scription of these systems [1]. Often M = C in which case one wants the num-

In his description, a sender A (often called ber of plaintexts that are mapped to a particular

Alice) wants to send a message m to a receiver B ciphertext (under different keys) to be the same. In

(who is called Bob). The message is called a plain- that case the ciphertext does not give any informa-

text and is taken from a ¬nite set, called plain- tion about the plaintext (see information theory).

text space M. Of course, Alice may send more The cryptanalyst who is connected to the trans-

messages. mission line can be:

Since the transmission channel is insecure (a Passive (eavesdropping): The cryptanalyst tries

person called Eve is also connected to the channel), to ¬nd m (or even better k) from c.

Alice applies a mapping Ek to m. The result c is Active (tampering): The cryptanalyst tries to ac-

called the ciphertext and is an element of a set C, tively manipulate the data that are being trans-

the ciphertext space. The mapping Ek is called the mitted. For instance, she alters a transmitted

encryption function. It is c that Alice sends to Bob ciphertext.

and so it will be c that is intercepted by Eve.

Henk van Tilborg

Clearly, the encryption function Ek must be a

one-to-one mapping, since Bob must be able to re-

Reference

trieve the plaintext/message m from the cipher-

text c by means of the decryption function Dk . In

formula: Dk (c) = m. [1] Shannon, C.E. (1949). “Communication theory and

Since more people may want to use the same secrecy systems.” Bell Systems Technical Journal,

28, 656“715.

cryptosystem and since Alice and Bob do not want

to use the same mapping too long for security rea-

sons, their function is taken from a large set E of

one-to-one mappings from M to C. It is for this

SHARE

reason that the encryption and decryption func-

tions carry a label k. This k is called the key and

is taken from the so-called key-space K. It is the Share is a portion of information distributed by a

set E = {Ek | k ∈ K} that describes the cryptosys- secret sharing scheme (SSS) to a given user. In the

tem. Quite clearly Alice and Bob must use the standard de¬nition of SSS, shares are distributed

Shortest vector problem 569

via secure, private channels in such a way that theorem only proves that short vectors exist, i.e.,

each participant only knows his own share [1, 2]. it does not give an ef¬cient algorithmic proce-

We note that it is also possible to organize SSS in dure to ¬nd such vectors. An algorithm to ¬nd

case of public channels [3]. the shortest nonzero vector in two-dimensional

lattices was already known to Gauss in the 19th

Robert Blakley century, but no general methods to ef¬ciently ¬nd

Gregory Kabatiansky (approximately) shortest vectors in n-dimentional

lattices were known until the early 1980s. A g-

References approximation algorithm for SVP is an algorithm

that on input a lattice L, outputs a nonzero lattice

vector of length at most g times the length of the

[1] Shamir, A. (1979). “How to share a secret.” Commu-

nications of the ACM, 22 (1), 612“613. shortest vector in the lattice. The LLL lattice re-

[2] Blakley, R. (1979). “Safeguarding cryptographic duction algorithm ([4], see lattice reduction) can

keys.” Proceedings of AFIPS 1979 National Com- be used to approximate SVP within a factor g =

√

puter Conference, 48, 313“317. O((2/ 3)n ) where n is the dimension of the lattice.

[3] Beimel, A. and B. Chor (1998). “Secret sharing with

Smaller approximation factors (slightly subexpo-

public reconstruction.” IEEE Transactions on Infor-

nential in n”see subexponential time for a def-

matiom Theory, 44 (5), 1887“1896.

inition) can be achieved in polynomial time us-

ing more complex algorithms like Schnorr™s Block

Korkine“Zolotarev reduction [6].

No ef¬cient (polynomial time) algorithm to com-

SHORTEST VECTOR pute the length of the shortest vector in a lat-

PROBLEM tice is known to date (leave alone actually ¬nding

the shortest vector). The NP-hardness of SVP (in

the Euclidean norm) was conjectured by van Emde

The Shortest Vector Problem (SVP) is the most

Boas in 1981 [7]. The conjecture remained wide

famous and widely studied computational prob-