Complexity of Lattice Problems

A Cryptographic Perspective

AvDaniele Micciancio,Shafi Goldwasser

Häftad, Engelska, 2012

Del 671 i serien Springer International Series in Engineering and Computer Science

2 973 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

Inbunden

3 062 kr

Beskrivning

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.

Produktinformation

Utgivningsdatum:2012-10-29
Mått:155 x 235 x 13 mm
Vikt:365 g
Format:Häftad
Språk:Engelska
Serie:Springer International Series in Engineering and Computer Science
Antal sidor:220
Förlag:Springer-Verlag New York Inc.
ISBN:9781461352938

Utforska kategorier

Innehållsförteckning

1 Basics.- 1 Lattices.- 2 Computational problems.- 3 Notes.- 2. Approximation Algorithms.- 1 Solving SVP in dimension.- 2 Approximating SVP in dimension n.- 3 Approximating CVP in dimension n.- 4 Notes.- 3. Closest Vector Problem.- 1 Decision versus Search.- 2 NP-completeness.- 3 SVP is not harder than CVP.- 4 Inapproximability of CVP.- 5 CVP with preprocessing.- 6 Notes.- 4. Shortest Vector Problem.- 1 Kannan’s homogenization technique.- 2 The Ajtai-Micciancio embedding.- 3 NP-hardnessofSVP.- 4 Notes.- 5. Sphere Packings.- 1 Packing Points in Small Spheres.- 2 The Exponential Sphere Packing.- 3 Integer Lattices.- 4 Deterministic construction.- 5 Notes.- 6. Low-Degree Hypergraphs.- 1 Sauer’s Lemma.- 2 Weak probabilistic construction.- 3 Strong probabilistic construction.- 4 Notes.- 7. Basis Reduction Problems.- 1 Successive minima and Minkowski’s reduction.- 2 Orthogonality defect and KZ reduction.- 3 Small rectangles and the covering radius.- 4 Notes.- 8. Cryptographic Functions.- 1 General techniques.- 2 Collision resistant hash functions.- 3 Encryption Functions.- 4 Notes.- 9. Interactive Proof Systems.- 1 Closest vector problem.- 2 Shortest vector problem.- 3 Treating other norms.- 4 What does it mean?.- 5 Notes.- References.