Average time fast SVP and CVP algorithms for low density lattices and the factorization of integers
Claus-Peter Schnorr (Johann Wolfgang Goethe-Universität Frankfurt, Germany)
We propose and analyze novel algorithms for finding shortest and closest lattice vectors. The algorithm New Enum performs the stages of exhaustive enumeration of short/close lattice vectors in order of decreasing success rate. We analyze New Enum for lattice bases satisfying GSA which in practice holds on the average for well reduced bases. New Enum solves SVP in nn/8+o(n) time for bases of dimension n that satisfy GSA. Under the volume heuristics a shortest lattice vector is found in polynomial time if the density of the lattice is moderately small. This might affect the RSA scheme. Integers N can be factored by solving (ln N)O(1) CVP's for the prime number lattice. Under combined standard and new heuristics these CVP's are solvable in polynomial time.
Talk slides (PDF).