The book presents a self-contained overview of the state of the art in the complexity of lattice problems, with particular emphasis on problems that are related to the construction of cryptographic functions. Specific topics covered are the strongest known inapproximability result for the shortest vector problem; the relations between this and other computational lattice problems; an exposition of how cryptographic functions can be built and prove secure based on worst-case hardness assumptions about lattice problems; and a study of the limits of non-approximability of lattice problems. Some background in complexity theory, but no prior knowledge about lattices, is assumed.
Micciancio (U. of California, San Diego) and Goldwasser (Massachusetts Institute of Technology) introduce lattices, deceptively simple geometric objects that can be pictorially depicted as the set of intersection points of an infinite, regular n-dimensional grid. Their rich combinatoratorial structure has attracted mathematicians and computer scientists working on diverse applications from number theory to cryptography. Following Atjai's lead, the authors focus on designing cryptographic functions that are as difficult to break as solving a computationally hard lattice problem. After introducing the basics of point lattices, complexity theory, and Minkowski's theorems, they venture into specific types of algorithmic problems (e.g., shortest vector, closest vector, and basis reduction problems). The final chapters delve into cryptographic functions and interactive proof systems. Annotation c. Book News, Inc., Portland, OR (booknews.com)