Lattices that admit logarithmic worst-case to average-case connection factors

We exhibit an average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n -dimensional lattices in the worst case, for γ(n) = O(√log n). The previously best known factor for any non-trivial class of lattices was γ(n) = Õ(n).

Authors

• Chris Peikert
• Alon Rosen

Keywords

• algebraic number theory
• lattices
• worst-case to average-case reductions