Complexity of Lattice Problems
Subtitle: a Cryptographic Perspective
By: by Daniele Micciancio, Shafi Goldwasser
Contributors: Goldwasser, Shafi
Series: The Springer International Series in Engineering and Computer Science -- 671; International series in engineering and computer science -- 671.
Publisher: Springer US
Published: 2002
Place of publication: Boston, MA
Language: eng
Format: [electronic resource] :
Number of pages: 220
ISBN-13: 9781461352938; 9781461508977
Subjects: Computer engineering; Information theory; Computational complexity; Data structures (Computer science); Computer science
Description: 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.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.