Lattice Problems beyond Polynomial Time

We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context-two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly n/ log n when running the protocol or reduction in 2 εn time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows. 1. We show a worst-case to average-case reduction proving that secret-key cryptography (specifically, collision-resistant hash functions) exists if the (decision version of the) Shortest Vector Problem (SVP) cannot be approximated to within a factor of O( √ n) in 2 εn time for any constant ε > 0. This extends to our setting Ajtai's celebrated polynomial-time reduction for the Short Integer Solutions problem (SIS) [STOC, 1996], which showed (after improvements by Micciancio and Regev [FOCS, 2004; and SIAM J. Computing, 2007]) that secret-key cryptography exists if SVP cannot be approximated to within a factor of O(n) in polynomial time. 2. We show another worst-case to average-case reduction proving that public-key cryptography exists if SVP cannot be approximated to within a factor of O(n) in 2 εn time. This extends Regev's celebrated polynomial-time reduction for the Learning with Errors problem (LWE) [STOC, 2005; and J. ACM, 2009], which achieved an approximation factor of O(n 1.5 ). In fact, Regev's reduction is quantum, but we prove our result under a classical reduction, generalizing Peikert's polynomial-time classical reduction [STOC, 2009], which achieved an approximation factor of O(n 2 ). 3. We show that the (decision version of the) Closest Vector Problem (CVP) with a constant approximation factor has a coAM protocol with a 2 εn -time verifier. This generalizes the i