论文标题
$ 2^{n/2} $ - $ \ sqrt {n} $ - svp和$ \ sqrt {n} $ - hermite SVP的时间算法，以及（h）SVP的改进的时间及时折衷权
A $2^{n/2}$-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
论文作者
论文摘要
我们显示了$ 2^{n/2+o（n）} $ - 时间算法，该算法在晶格$ \ MATHCAL {l} \ subset \ subset \ subset \ subset \ mathbb {r}^n $中，最多$ \ tilde \ tilde {o}（o） \ min \ {λ_1（\ Mathcal {l}），\ det（\ Mathcal {l}）^{1/n} \} $，其中$λ_1（\ Mathcal {l}）$是最短的非零晶格载体vector vestector and $ \ is lats $ det（l Mathise）的长度。 Minkowski表明$λ_1（\ Mathcal {l}）\ leq \ sqrt {n} \ det（\ Mathcal {l}）^{1/n} $，并且存在$λ_1（\ Mathcal {l}）\ geq chot（\ geq chot）（\ geq chot） \ det（\ Mathcal {l}）^{1/n} $，以便我们的算法找到相对于确定剂（最多可达到polyogarithmic因子）尽可能短的向量。 该结果背后的主要技术贡献是对Arxiv：1412.7994的算法的新分析（更简单的变体），该算法以前只有以前已知可以解决较少的有用问题。为此，我们至关重要地依赖``反向minkowski theorem''（由dadush arxiv：1606.06913猜想，并由arxiv：1611.05979证明），可以将其视为$λ_1（\ viscal {\ natercal {\ l l} \ l e q \ l leq \ s s s s phosever \ det（\ Mathcal {l}）^{1/n} $。 以前，由于[Liu，Wang，Xu，Xu和Zheng，2011]，找到此类矢量的最快算法是$ 2^{。802N + O（n）} $ - 时间算法，实际上发现了具有长度$ o（1）\ cdotλ_1（1）\ ccdotλ_1（1）\λ_1（late）的非零lattice vector。尽管我们没有展示如何找到具有此长度的晶格向量，$ 2^{n/2+o（n）} $，但我们确实表明我们的算法足以满足此类算法的最重要应用：基础减少。特别是，我们展示了Gama和Nguyen的幻灯片还原算法的修改版[Gama and Nguyen，STOC 2008]，可以将其与上述算法结合使用，以改善几乎所有与Cryptography相关的政权中最短矢量算法的时间长度折衷。
We show a $2^{n/2+o(n)}$-time algorithm that finds a (non-zero) vector in a lattice $\mathcal{L} \subset \mathbb{R}^n$ with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathcal{L}), \det(\mathcal{L})^{1/n}\}$, where $λ_1(\mathcal{L})$ is the length of a shortest non-zero lattice vector and $\det(\mathcal{L})$ is the lattice determinant. Minkowski showed that $λ_1(\mathcal{L}) \leq \sqrt{n} \det(\mathcal{L})^{1/n}$ and that there exist lattices with $λ_1(\mathcal{L}) \geq Ω(\sqrt{n}) \cdot \det(\mathcal{L})^{1/n}$, so that our algorithm finds vectors that are as short as possible relative to the determinant (up to a polylogarithmic factor). The main technical contribution behind this result is new analysis of (a simpler variant of) an algorithm from arXiv:1412.7994, which was only previously known to solve less useful problems. To achieve this, we rely crucially on the ``reverse Minkowski theorem'' (conjectured by Dadush arXiv:1606.06913 and proven by arXiv:1611.05979), which can be thought of as a partial converse to the fact that $λ_1(\mathcal{L}) \leq \sqrt{n} \det(\mathcal{L})^{1/n}$. Previously, the fastest known algorithm for finding such a vector was the $2^{.802n + o(n)}$-time algorithm due to [Liu, Wang, Xu, and Zheng, 2011], which actually found a non-zero lattice vector with length $O(1) \cdot λ_1(\mathcal{L})$. Though we do not show how to find lattice vectors with this length in time $2^{n/2+o(n)}$, we do show that our algorithm suffices for the most important application of such algorithms: basis reduction. In particular, we show a modified version of Gama and Nguyen's slide-reduction algorithm [Gama and Nguyen, STOC 2008], which can be combined with the algorithm above to improve the time-length tradeoff for shortest-vector algorithms in nearly all regimes, including the regimes relevant to cryptography.
