子格攻擊的反思

Reflections on the Sublattice Attack

李文鼎(Wen-Ding Li)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.01662

摘要

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

關鍵字

格基 ； 格規約 ； 最短格向量問題 ； 子格攻擊

並列摘要

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.

並列關鍵字

Lattice ； Lattice Basis Reduction ； Shortest Vector Problem ； Sublattice Attack

參考文獻

[CL] Jung Hee Cheon and Changmin Lee. Cryptanalysis of the multilinear map on the ideal lattices.

[LLL82] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Fac- toring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.

[LN13] Mingjie Liu and Phong Q Nguyen. Solving bdd by enumeration: An update. In Topics in Cryptology–CT-RSA 2013, pages 293–309. Springer, 2013.

[NS06] Phong Q. Nguyen and Damien Stehlé. LLL on the average. In Algorithmic Number Theory, pages 238–256. Springer, 2006.

[vdPS13] Joop van de Pol and Nigel P Smart. Estimating key sizes for high dimen- sional lattice-based systems. In Cryptography and Coding, pages 290–303. Springer, 2013.