论文标题
多项式时间以外的晶格问题
Lattice Problems Beyond Polynomial Time
论文作者
论文摘要
我们研究了一个世界中晶格问题的复杂性，在这个世界上，算法，减少和协议可以在超级分类时间内运行，重新审视了四个基本结果：两个最差的平均案例减少和两个方案。我们还展示了一个新颖的协议。 1。我们证明，如果$ \ widetilde {o}（\ sqrt {n}）$ - 近似SVP很难，$ 2^{\ varepsilon n} $ - 时间算法很难。即，我们扩展到我们的设置（Micciancio和Regev的改进版本）Ajtai著名的多项式时间最差案例从$ \ widetilde {o}（n）$ - $ - 近似SVP降低到SIS。 2。我们证明，如果$ \ widetilde {o}（n）$ - 近似SVP很难，$ 2^{\ varepsilon n} $ - 时间算法很难。这扩展到了我们的设置Regev的著名多项式时间最差案例，从$ \ widetilde {o}（n^{1.5}）$ - 大约SVP降低到LWE。实际上，Regev的减少是量子，但我们的减少是经典的，从$ \ widetilde {o}（n^2）$ - 近似SVP概括了Peikert的多项式经典减少。 3。我们显示了$ 2^{\ varepsilon n} $ - $ o（1）$ - 近似CVP的时间coam协议，概括了$ o（\ sqrt {n/\ log n}）$ o（\ sqrt {n/\ log n}）$ - 由于Goldreich和Goldreich和Goldwasser所致的CVP。这些结果表明，将CVP和SVP的细颗粒硬度结果延伸到更大的近似因子的复杂性理论障碍。 （此结果也扩展到任意规范。） 4。我们显示了$ 2^{\ varepsilon n} $ - 时间共同互联网确定的协议，用于$ O（\ sqrt {\ log n}）$ - 近似SVP，概括了（也庆祝！）$ o（\ sqrt {n}）$ - cvp和rege aharonov and rece aharonov and rece（也庆祝！）polynomial time协议。 5。我们为$ o（1）$ - 近似CVP提供了一个新颖的昏迷协议，其中$ 2^{\ varepsilon n} $ - 时间验证器。 上面描述的所有结果都是更一般定理的特殊案例，这些案例可以实现时间及时的折衷。
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.
