Complexity of Lattice Problems

A Cryptographic Perspective

Authors: Daniele Micciancio and Shafi Goldwasser The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers. March 2002, 220 pages ISBN 0-7923-7688-9 [BibTeX] [Amazon] [Barnes&Noble] [Kluwer]

Description

Complexity of Lattice Problems: A Cryptographic Perspective is an essential reference for those researching ways in which lattice problems can be used to build cryptographic systems. It will also be of interest to those working in computational complexity, combinatorics, and foundations of cryptography.

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 proven 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.

The aim of the authors is to make lattice-based cryptography accessible to a wide audience, ultimately yielding further research and applications. Complexity of Lattice Problems: A Cryptographic Perspective will be valuable to anyone working in this fast-moving field. It serves as an excellent reference, providing insight into some of the most challenging issues being examined today.

Contents

Preface

1. BASICS

1. Lattices
   1.1 Determinant
   1.2 Successive minima
   1.3 Minkowski's theorems
2. Computational problems
   2.1 Complexity theory
   2.2 Some lattice problems
   2.3 Hardness of approximation
3. Notes

2. APPROXIMATION ALGORITHMS

1. Solving SVP in dimension 2
   1.1 Reduced basis
   1.2 Gauss' algorithm
   1.3 Running time analysis
2. Approximating SVP in dimension n
   2.1 Reduced basis
   2.2 The LLL basis reduction algorithm
   2.3 Running time analysis
3. Approximating CVP in dimension n
4. Notes

3. CLOSEST VECTOR PROBLEM

1. Decision versus Search
2. NP-completeness
3. SVP is not harder than CVP
   3.1 Deterministic reduction
   3.2 Randomized reduction
4. Inapproximability of CVP
   4.1 Polylogarithmic factor
   4.2 Larger factors
5. CVP with preprocessing
6. Notes

4. SHORTEST VECTOR PROBLEM

1. Kannan's homogenization technique
2. The Ajtai-Micciancio embedding
3. NP-hardness of SVP
   3.1 Hardness under randomized reductions
   3.2 Hardness under nonuniform reductions
   3.3 Hardness under deterministic reductions
4. Notes

5. SPHERE PACKINGS

1. Packing points in small spheres
2. The exponential sphere packing
   2.1 The Schnorr-Adleman prime number lattice
   2.2 Finding clusters
   2.3 Some additional properties
3. Integer lattices
4. Deterministic construction
5. Notex

6. LOW-DEGREE HYPERGRAPHS

1. Sauer's lemma
2. Weak probabilistic construction
   2.1 The exponential bound
   2.2 Well spread hypergraphs
   2.3 Proof of the weak theorem
3. Strong probabilistic construction
4. Notes

7. BASIS REDUCTION PROBLEMS

1. Successive minima and Minkowski's reduction
2. Orthogonality defect and KZ reduction
3. Small rectangles and the covering radius
4. Notes

8. CRYPTOGRAPHIC FUNCTIONS

1. General techniques
   1.1 Lattices, sublattices and groups
   1.2 Discrepancy
   1.3 Statistical distance
2. Collision resistant hash functions
   2.1 The construction
   2.2 Collision resistance
   2.3 The iterative step
   2.4 Almost perfect lattices
3. Encryption functions
   3.1 The GGH scheme
   3.2 The HNF technique
   3.3 The Ajtai-Dwork cryptosystem
   3.4 NTRU
4. Notes

9. INTERACTIVE PROOF SYSTEMS

1. Closest vector problem
   1.1 Proof of the soundness claim
   1.2 Conclusion
2. Shortest vector problem
3. Treating other norms
4. What does it mean?
5. Notes

References

Index