Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor

DOI10.1137/S0097539703433511zbMath1112.68067OpenAlexW2051176401MaRDI QIDQ4651529

Daniele Micciancio

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703433511

zbMATH Keywords

covering radiuscryptographyshortest vector problemaverage-case complexityhash functionspoint latticesclosest vector problem with preprocessingalmost perfect lattices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Combinatorics in computer science (68R05) Data encryption (aspects in computer science) (68P25) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Relations with coding theory (11H71)

Related Items (13)

The inapproximability of lattice and coding problems with preprocessing ⋮ Multi-key Homomorphic Authenticators ⋮ Covering codes for the fixed length Levenshtein metric ⋮ A Note on Lattice Packings via Lattice Refinements ⋮ Explicit Hard Instances of the Shortest Vector Problem ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ Watermarking cryptographic functionalities from standard lattice assumptions ⋮ Multi-theorem preprocessing NIZKs from lattices ⋮ The Geometry of Lattice Cryptography ⋮ Computing the covering radius of a polytope with an application to lonely runners ⋮ Worst-case to average-case reductions for module lattices ⋮ The remote set problem on lattices

This page was built for publication: Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor