## Complexity of Lattice Problems: A Cryptographic PerspectiveLattices 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 |

211 | |

219 | |

### Other editions - View all

Complexity of Lattice Problems: A Cryptographic Perspective Daniele Micciancio,Shafi Goldwasser No preview available - 2012 |

### Common terms and phrases

Ajtai approximating CVP approximation factor basis vectors bound Chapter closest vector problem coefficients compute constant contains Cook reduction covering radius cryptographic cryptosystem CVP instance decryption defined definition det(A deterministic efficiently encryption equivalent exists exponential find a lattice GAPSVP7 Goldreich hard hash functions Hermite normal form hypergraph inapproximability independent lattice vectors input integer vector ip norm lattice basis lattice point lattice problems Lemma linearly independent linearly independent lattice LLL algorithm LLL reduced matrix Micciancio Minkowski's Moreover nearest plane algorithm Notice NP-hard oracle output P/poly packing polynomial time algorithm probabilistic promise problem proof system Proposition public key rank reduced basis satisfies Section short vector shortest vector problem solution solve SVP span(B sphere of radius square free statistical distance sublattice subset sum subset sum problem successive minima SVP and CVP SVP7 target vector Theorem uniformly at random vector of length YES instance

### References to this book

Advances in Cryptology - EUROCRYPT 2005: 24th Annual International ... EUROCRYPT No preview available - 2005 |

Advances in Cryptology – ASIACRYPT 2005: 11th International Conference on ... Bimal Roy Limited preview - 2005 |