NP-hard to solve exactly under randomized re-

sented by a basis), SVP asks to ¬nd the shortest

nonzero vector in L. The problem can be de¬ned ductions [1]. The strongest NP-hardness result

for SVP known to date is due to Micciancio [5],

with respect to any norm, but the Euclidean norm

who showed that SVP is NP-hard even to approxi-

is the most common (see the entry lattice for a √

mate within any factor less than 2. Stronger (but

de¬nition). A variant of SVP (commonly studied

still subpolynomial) inapproximability results are

in computational complexity theory) only asks to

compute the length (denoted »(L)) of the shortest known for SVP in the ∞ norm [2]. On the other

nonzero vector in L, without necessarily ¬nding hand, Goldreich and Goldwasser [3] have shown

that (under standard complexity assumptions)

the vector.

SVP cannot be NP-hard to approximate within

SVP has been studied by mathematicians (in

small polynomial factors g = O( n/ log n).

the equivalent language of quadratic forms) since

As is the case with the related Closest Vector

the 19th century because of its connection to many

Problem, ¬nding a good approximation algorithm

problems in the number theory. One of the earliest

(i.e., a polynomial-time algorithm with polyno-

references to SVP in the computer science litera-

mial approximation factors) is one of the most im-

ture is [7], where the problem is conjectured to be

portant open questions in the area. Indeed, the

NP-hard.

hardness of approximating SVP within certain

A cornerstone result about SVP is Minkowski™s

polynomial factors can be used as the basis for

¬rst theorem, which states that the shortest

the construction of provably secure cryptographic

nonzero vector in any n-dimentional lattice has

length at most γn det(L)1/n , where γn√ an abso- functions (see lattice based cryptography).

is

lute constant (approximately equal to n) that de-

Daniele Micciancio

pends only of the dimension n, and det(L) is the

determinant of the lattice (see the entry lattice for References

a de¬nition).

The upper bound provided by Minkowski™s the- [1] Ajtai, M. (1998). “The shortest vector problem in L2

orem is tight, i.e., there are lattices such that the is NP-hard for randomized reductions (extended ab-

shortest nonzero vector has length γn det(L)1/n . stract).” Proceedings of the Thirtieth Annual ACM

However, general lattices may contain vectors Symposium on Theory of Computing”STOC™98,

much shorter than that. Moreover, Minkowski™s Dallas, TX. ACM Press, New York, 10“19.

570 Shrinking generator

¬rst row concerns only the initialization; the

[2] Dinur, I. (2000). “Approximating SV P∞ to within

almost-polynomial factors is NP-hard.” Proceedings internal states are of the form st st’1 st’2 or

of the 4th Italian Conference on Algorithms and st st’1 st’2 st’3 ):

Complexity”CIAC 2000, Rome, Lecture Notes in

Computer Science, vol. 1767, eds. G. Bongiovanni,

G. Gambosi, and R. Petreschi. Springer, Berlin, 263“

R1 R2

276.

[3] Goldreich, O. and S. Goldwasser (2000). “On the lim- State Output State Output Output

its of nonapproximability of lattice problems.” Jour-

nal of Computer and System Sciences, 60 (3), 540“ 010 0101

563. Preliminary version in STOC™98. 001 0 1010 1

´

[4] Lenstra, A.K., H.W. Lenstra, Jr., and L. Lovasz

100 1 1101 0 0

(1982). “Factoring polynomials with rational co-

110 0 0110 1

ef¬cients.” Mathematische Annalen, 261, 513“

111 0 0011 0

534.

011 1 1001 1 1

[5] Micciancio, D. “The shortest vector problem is NP-

101 1 0100 1 1

hard to approximate to within some constant.”

010 1 0010 0 0

SIAM Journal on Computing, 30 (6), 2008“2035.

001 0 0001 0

Preliminary version in FOCS™98.

[6] Schnorr, C.-P. (1987). “A hierarchy of polynomial 100 1 1000 1 1

time lattice basis reduction algorithms.” Theoretical 110 0 1100 0

Computer Science, 53 (2“3), 201“224. 111 0 1110 0

[7] van Emde Boas, P. (1981). “Another NP-complete 011 1 1111 0 0

problem and the complexity of computing short vec-

101 1 0111 1 1

tors in a lattice.” Technical Report 81-04, Math-

. . . . .

. . . . .

ematische Instituut, University of Amsterdam, . . . . .

Available on-line at URL http://turing.wins.uva.nl/

peter/

The inventors discussed some security points in

their paper. More recent results have been given

in [2, 5]. A discussion about the implementation

SHRINKING GENERATOR and the use of a buffer (in order to avoid the

irregular rate of the output) is presented in [3]

The shrinking generator is a clock-controlled and [4].

generator that has been proposed in 1993 [1]. It

is based on two Linear Feedback Shift Registers Caroline Fontaine

(LFSRs), say R1 and R2 . The idea is that R1 ™s out-

put will decimate R2 ™s output. At each step, both

References

are clocked; if R1 output a 1, then R2 ™s output bit

is included in the keystream, else (if R1 outputs a

[1] Coppersmith, D., H. Krawczyk, and Y. Mansour

0) R2 ™s output bit is discarded.

(1994). “The shrinking generator.” Advances in

Cryptology”CRYPTO™93, Lecture Notes in Com-

puter Science, vol. 773, ed. D.R. Stinson. Springer-

R1 Verlag, Berlin, 22“39.

[2] Golic, J. (1995). “Intrinsic statistical weakness of

keystream generators”. Advances in Cryptology”

ASIACRYPT™94, Lecture Notes in Computer Sci-

ence, vol. 917, eds. J. Pieprzyk and R. Safari-Naini.

R2 keep Springer-Verlag, Berlin, 91“103.

[3] Kessler, I. and H. Krawczyk (1995). “Minimum

buffer length and clock rate for the shrinking

generator cryptosystem.” IBM Research Report

discard RC19938, IBM T.J. Watson Research Center, York-

town Heights, NY, USA.

[4] Krawczyk, H. (1994). “The shrinking genera-

EXAMPLE. Let us consider R1 of length three, tor: Some practical considerations.” Fast Software

with the feedback relation st+1 = st + st’2 , and Encryption, Lecture Notes in Computer Science,

R2 of lenth four, with the feedback relation vol. 809, ed. R.J. Anderson. Springer-Verlag, Berlin,

st+1 = st + st’3 . Then the following happens (the 45“46.

Side-channel analysis 571

AES rounds

1 2 3 4 5 6 7 8 9 10

Fig. 1. AES power trace

Basically a power consumption trace exhibits

[5] Johansson, T. (1998). “Reduced complexity corre-

lation attack on two clock-controlled generators.” large scale patterns most often related to the

Advances in Crptology”ASIACRYPT™98, Lecture structure of the executed code. The picture below

Notes in Computer Science, vol. 1514, eds. K. Ohta (Figure 1) shows the power trace of a smart-card

and D. Pei. Springer-Verlag, Berlin, 342“356. chip ciphering a message with the Advanced En-

cryption Standard (AES). The ten rounds are eas-

ily recognised with nine almost regular patterns

¬rst followed by a shorter one.

SIDE-CHANNEL ANALYSIS Zooming into a power signal exhibits a local be-

haviour in close relationship with the silicon tech-