Complexity of Lattice Problems: A Cryptographic Perspective

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\rAuthors......Page 227
Index......Page 228
Back Cover\r......Page 230