Complexity of Lattice Problems: A Cryptographic Perspective

Front Cover
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

Other editions - View all

Common terms and phrases