子格攻擊的反思

Abstract

格規約是目前被認為是對最短向量問題最實際的演算法，因此估計格規約實際上能產生的短向量長度是重要的問題。子格攻擊是在格的行列式值較小時，將輸入經過處理再使用格規約，能產生比直接使用格規約得到的向量更短的方法。本文將對子格攻擊做一完整的介紹以及用實驗驗證結果。

Lattice basis reduction is a common and perhaps the most practical method today to solve the approximate shortest vector problem. It is important to estimate the length of the short vectors output by lattice basis reduction. However, accurate estimation is difficult to obtain, and people often rely on empirical heuristics. Based on the asymptotic behavior of the lengths of the short vectors, there is a well-known sublattice attack if the determinant of the lattice is relatively small. Here we provide detailed exposition of the cause of the sublattice attack and verify with experimentation on Goldstein-Mayer lattices.