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 root n/log n when running the protocol or reduction in 2(epsilon 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) over tilde(root n) in 2(epsilon n) time. This extends to our setting Ajtai's celebrated polynomial-time reduction for the Short Integer Solutions (SIS) problem (1996), which showed (after improvements by Micciancio and Regev (2004, 2007)) that secret-key cryptography exists if SVP cannot be approximated to within a factor of (O) over tilde (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) over tilde (n) in 2(epsilon n) time. This extends Regev's celebrated polynomial-time reduction for the Learning with Errors (LWE) problem (2005, 2009), which achieved an approximation factor of (O) over tilde (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 (2009), which achieved an approximation factor of (O) over tilde (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(epsilon n)-time verifier. We prove this via a (very simple) generalization of the celebrated polynomial-time protocol due to Goldreich and Goldwasser (1998, 2000). It follows that the recent series of 2(epsilon n)-time and even 2((1-epsilon)n)-time hardness results for CVP cannot be extended to large constant approximation factors.. unless AMETH is false. We also rule out 2((1-epsilon)n)-time lower bounds for any constant approximation factor gamma > root 2, under plausible complexity-theoretic assumptions. (These results also extend to arbitrary norms, with different constants.) (4) We show that O(root log n)-approximate SVP has a coNTIME protocol with a 2(epsilon n)-time verifier. Here, the analogous (also celebrated!) polynomial-time result is due to Aharonov and Regev (2005), who showed a polynomial-time protocol achieving an approximation factor of root n (for both SVP and CVP, while we only achieve this result for CVP). This result implies similar barriers to hardness, with a larger approximation factor under a weaker complexity-theoretic conjectures (as does the next result). (5) Finally, we give a novel coMA protocol for constant-factor-approximate CVP with a 2(epsilon n)-time verifier. Unlike our other results, this protocol has no known analog in the polynomial-time regime. All of the results described above are special cases of more general theorems that achieve time-approximation factor tradeoffs. In particular, the tradeoffs for the first four results smoothly interpolate from the polynomial-time results in prior work to our new results in the exponential-time world.