论文标题
最近的色彩算法
The nearest-colattice algorithm
论文作者
论文摘要
在这项工作中，我们展示了求解最接近矢量问题（CVP）的多项式时间算法的层次结构。我们的第一个贡献是一种启发式算法，与HSVP算法相同的距离权衡，即$ \ of β^{\ frac {n} {2β}} \ textrm {covol}（λ）^{\ frac {\ frac {1} {n}} $对于等级$ n $的随机lattice $λ$。与所谓的Kannan的嵌入技术相比，我们的算法允许使用预反复计算，可用于有效的批处理CVP实例。这意味着对基于格子的签名的某些攻击导致了预先登陆后非常便宜的伪造。我们的第二个贡献是从近似最接近的向量的因子$ \ o \ of n^{\ frac32}β^{\ frac {\ frac {3n} {2β}} $到最短矢量问题（svp）中的第二个贡献。
In this work, we exhibit a hierarchy of polynomial time algorithms solving approximate variants of the Closest Vector Problem (CVP). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as HSVP algorithms, namely $\approx β^{\frac{n}{2β}}\textrm{covol}(Λ)^{\frac{1}{n}}$ for a random lattice $Λ$ of rank $n$. Compared to the so-called Kannan's embedding technique, our algorithm allows using precomputations and can be used for efficient batch CVP instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a proven reduction from approximating the closest vector with a factor $\approx n^{\frac32}β^{\frac{3n}{2β}}$ to the Shortest Vector Problem (SVP) in dimension $β$.
