Complexity of Lattice Problems: A Cryptographic Perspective

✍ Scribed by Daniele Micciancio, Shafi Goldwasser

• Publisher: Springer
• Year: 2012
• Tongue: English
• Leaves: 230
• Series: The Springer International Series in Engineering and Computer Science
• Edition: Softcover reprint of the original 1st ed. 2002
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

ToC......Page 6
Preface......Page 9
1.1 Lattices......Page 11
1.1.1 Determinant......Page 16
1.1.2 Successive minima......Page 17
1.1.3 Minkowski's theorems......Page 21
1.2 Computational problems......Page 24
1.2.1 Complexity Theory......Page 25
1.2.2 Some lattice problems......Page 27
1.2.3 Hardness of approximation......Page 29
1.3 Notes......Page 31
2 Approximation Algorithms......Page 33
2.1.1 Reduced basis......Page 34
2.1.2 Gauss' algorithm......Page 37
2.1.3 Running time analysis......Page 40
2.2.1 Reduced basis......Page 42
2.2.2 The LLL basis reduction algorithm......Page 44
2.2.3 Running time analysis......Page 46
2.3 Approximating CVP in Dimension n......Page 50
2.4 Notes......Page 52
3 Closest Vector Problem......Page 55
3.1 Decision versus Search......Page 56
3.2 NP-completeness......Page 58
3.3 SVP is not harder than CVP......Page 62
3.3.1 Deterministic reduction......Page 63
3.3.2 Randomized Reduction......Page 66
3.4.1 Polylogarithmic factor......Page 68
3.4.2 Larger factors......Page 71
3.5 CVP with preprocessing......Page 74
3.6 Notes......Page 77
4 Shortest Vector Problem......Page 79
4.1 Kannan's homogenization technique......Page 80
4.2 The Ajtai-Micciancio embedding......Page 87
4.3.1 Hardness under randomized reductions......Page 93
4.3.2 Hardness under nonuniform reductions......Page 95
4.3.3 Hardness under deterministic reductions......Page 96
4.4 Notes......Page 97
5 Sphere Packings......Page 101
5.1 Packing Points in Small Spheres......Page 104
5.2 The Exponential Sphere Packing......Page 106
5.2.1 The Schnorr-Adleman prime number lattice......Page 107
5.2.2 Finding clusters......Page 109
5.2.3 Some additional properties......Page 114
5.3 Integer Lattices......Page 115
5.4 Deterministic construction......Page 118
5.5 Notes......Page 120
6 Low-Degree Hypergraphs......Page 121
6.1 Sauer's Lemma......Page 122
6.2 Weak probabilistic construction......Page 124
6.2.1 The exponential bound......Page 125
6.2.2 Well spread hypergraphs......Page 128
6.2.3 Proof of the weak theorem......Page 131
6.3 Strong probabilistic construction......Page 132
6.4 Notes......Page 134
7.1 Successive minima and Minkowski's reduction......Page 135
7.2 Orthogonality defect and KZ reduction......Page 141
7.3 Small rectangles and the covering radius......Page 146
7.4 Notes......Page 151
8 Cryptographic Functions......Page 153
8.1 General techniques......Page 156
8.1.1 Lattices, sublattices and groups......Page 157
8.1.2 Discrepancy......Page 163
8.1.3 Statistical distance......Page 167
8.2 Collision resistant hash functions......Page 171
8.2.1 The construction......Page 172
8.2.2 Collision resistance......Page 174
8.2.3 The iterative step......Page 178
8.2.4 Almost perfect lattices......Page 192
8.3 Encryption Functions......Page 194
8.3.1 The GGH scheme......Page 195
8.3.2 The HNF technique......Page 197
8.3.3 The Ajtai-Dwork cryptosystem......Page 199
8.3.4 NTRU......Page 201
8.4 Notes......Page 204
9 Interactive Proof Systems......Page 205
9.1 Closest vector problem......Page 208
9.1.1 Proof of the soundness claim......Page 211
9.2 Shortest vector problem......Page 214
9.3 Treating other norms......Page 216
9.4 What does it mean......Page 218
9.5 Notes......Page 220
References......Page 221
About the
Authors......Page 227
Index......Page 228
Back Cover
......Page 230