# Complexity of Lattice Problems: A Cryptographic Perspective

Springer Science & Business Media, Mar 31, 2002 - Computers - 220 pages
Lattices are geometric objects that can be pictorially described as the set of intersection points of an infinite, regular n-dimensional grid. De spite their apparent simplicity, lattices hide a rich combinatorial struc ture, which has attracted the attention of great mathematicians over the last two centuries. Not surprisingly, lattices have found numerous ap plications in mathematics and computer science, ranging from number theory and Diophantine approximation, to combinatorial optimization and cryptography. The study of lattices, specifically from a computational point of view, was marked by two major breakthroughs: the development of the LLL lattice reduction algorithm by Lenstra, Lenstra and Lovasz in the early 80's, and Ajtai's discovery of a connection between the worst-case and average-case hardness of certain lattice problems in the late 90's. The LLL algorithm, despite the relatively poor quality of the solution it gives in the worst case, allowed to devise polynomial time solutions to many classical problems in computer science. These include, solving integer programs in a fixed number of variables, factoring polynomials over the rationals, breaking knapsack based cryptosystems, and finding solutions to many other Diophantine and cryptanalysis problems.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 BASICS 1 11 Determinant 6 12 Successive minima 7 13 Minkowskis theorems 11 2 Computational problems 14 21 Complexity Theory 15 22 Some lattice problems 17 23 Hardness of approximation 19
 3 Integer Lattices 105 4 Deterministic construction 108 5 Notes 110 LOWDEGREE HYPERGRAPHS 111 1 Sauers Lemma 112 2 Weak probabilistic construction 114 21 The exponential bound 115 22 Well spread hypergraphs 118

 3 Notes 21 APPROXIMATION ALGORITHMS 23 1 Solving SVP in dimension 2 24 12 Gauss algorithm 27 13 Running time analysis 30 2 Approximating SVP in dimension n 32 22 The LLL basis reduction algorithm 34 23 Running time analysis 36 3 Approximating CVP in dimension n 40 4 Notes 42 CLOSEST VECTOR PROBLEM 45 1 Decision versus Search 46 2 NPcompleteness 48 3 SVP is not harder than CVP 52 31 Deterministic reduction 53 32 Randomized Reduction 56 4 Inapproximability of CVP 58 42 Larger factors 61 5 CVP with preprocessing 64 6 Notes 67 SHORTEST VECTOR PROBLEM 69 1 Kannans homogenization technique 70 2 The AjtaiMicciancio embedding 77 3 NPhardness of SVP 83 32 Hardness under nonuniform reductions 85 33 Hardness under deterministic reductions 86 4 Notes 87 SPHERE PACKINGS 91 1 Packing Points in Small Spheres 94 2 The Exponential Sphere Packing 96 21 The SchnorrAdleman prime number lattice 97 22 Finding clusters 99 23 Some additional properties 104
 23 Proof of the weak theorem 121 3 Strong probabilistic construction 122 4 Notes 124 BASIS REDUCTION PROBLEMS 125 2 Orthogonality defect and KZ reduction 131 3 Small rectangles and the covering radius 136 4 Notes 141 CRYPTOGRAPHIC FUNCTIONS 143 1 General techniques 146 11 Lattices sublattices and groups 147 12 Discrepancy 153 13 Statistical distance 157 2 Collision resistant hash functions 161 21 The construction 162 22 Collision resistance 164 23 The iterative step 168 24 Almost perfect lattices 182 3 Encryption Functions 184 31 The GGH scheme 185 32 The HNF technique 187 33 The AjtaiDwork cryptosystem 189 34 NTRU 191 4 Notes 194 INTERACTIVE PROOF SYSTEMS 195 1 Closest vector problem 198 11 Proof of the soundness claim 201 12 Conclusion 204 3 Treating other norms 206 4 What does it mean? 208 5 Notes 210 References 211 Index 219 Copyright

### References to this book

 Advances in Cryptology - EUROCRYPT 2005: 24th Annual International ...EUROCRYPTNo preview available - 2005
 Advances in Cryptology – ASIACRYPT 2005: 11th International Conference on ...Bimal RoyLimited preview - 2005
All Book Search results &raquo;