  We study the complexity of lattice problems in a world where algorithms,
reductions, and protocols can run in superpolynomial time, revisiting four
foundational results: two worst-case to average-case reductions and two
protocols. We also show a novel protocol.
  1. We prove that secret-key cryptography exists if
$\widetilde{O}(\sqrt{n})$-approximate SVP is hard for $2^{\varepsilon n}$-time
algorithms. I.e., we extend to our setting (Micciancio and Regev's improved
version of) Ajtai's celebrated polynomial-time worst-case to average-case
reduction from $\widetilde{O}(n)$-approximate SVP to SIS.
  2. We prove that public-key cryptography exists if
$\widetilde{O}(n)$-approximate SVP is hard for $2^{\varepsilon n}$-time
algorithms. This extends to our setting Regev's celebrated polynomial-time
worst-case to average-case reduction from $\widetilde{O}(n^{1.5})$-approximate
SVP to LWE. In fact, Regev's reduction is quantum, but ours is classical,
generalizing Peikert's polynomial-time classical reduction from
$\widetilde{O}(n^2)$-approximate SVP.
  3. We show a $2^{\varepsilon n}$-time coAM protocol for $O(1)$-approximate
CVP, generalizing the celebrated polynomial-time protocol for $O(\sqrt{n/\log
n})$-CVP due to Goldreich and Goldwasser. These results show
complexity-theoretic barriers to extending the recent line of fine-grained
hardness results for CVP and SVP to larger approximation factors. (This result
also extends to arbitrary norms.)
  4. We show a $2^{\varepsilon n}$-time co-non-deterministic protocol for
$O(\sqrt{\log n})$-approximate SVP, generalizing the (also celebrated!)
polynomial-time protocol for $O(\sqrt{n})$-CVP due to Aharonov and Regev.
  5. We give a novel coMA protocol for $O(1)$-approximate CVP with a
$2^{\varepsilon n}$-time verifier.
  All of the results described above are special cases of more general theorems
that achieve time-approximation factor tradeoffs.
