Lattice Basis Reduction

NP-Completeness 219

Project 13.2. Write a report and present a seminar talk on the NP-

completeness of the problem of finding a shortest nonzero lattice vector for

the Euclidean norm,

|y|

2

=



|y

1

|

2

+ |y

2

|

2

+ ··· + |y

n

|

2



1/2

for y = [y

1

, y

2

, . . . , y

n

] ∈ R

n

.

A very readable introduction to this topic is Kumar and Sivakumar [82] (es-

pecially §3). The fundamental res ults were first proved by Ajtai [5, 6]; see

also Bl¨omer and Seifert [17]. The original proof by Ajtai has been simplified

by Micciancio [97, 98], whose Ph.D. thesis fr om MIT is available online [9 6].

The book by Micciancio and Goldwasser [100] develops this material from the

point of view of