一個改良的LLL演算法與其對NTRU之密碼攻擊

Abstract

在1982年由Lenstra, Lenstra 和 Lovasz三位數學家提出的一個基底裁減(Basis reduction)演算法，簡稱LLL演算法，被證明可在多項式時間內解出緒(Lattice)上的SVP (Shortest vector problem)及CVP (Closet vector problem)這兩個NP-hard問題。但LLL演算法在面對高維度的緒時便會失去它的效果。在此論文中我們經由觀察LLL演算法中的長度裁減(Size reduction)動作，提出一個修改的LLL演算法，藉以提昇LLL演算法的效能。 NTRU公鑰加密系統中公鑰和私鑰之間的關係可以使NTRU金鑰還原問題(NTRU key recovery problem)被轉換為緒上的SVP問題，並以LLL演算法求解。我們提出一個修改的LLL演算法。我們比較修改的LLL演算法與原來的LLL演算法的效能，並利用解NTRU公鑰還原問題來比較二者所能解的NTRU維度，以顯示我們修改的LLL演算法優於原本的LLL演算法。

In 1982, Lenstra, Lenstra and Lovasz invented a basis reduction algorithm, abbreviated LLL algorithm, which has been proven a polynomial-time algorithm that solves the shortest vector problem (SVP) and the closest vector problem (CVP) on lattices. These two problems have been proven NP-hard. However, LLL algorithm will be unacceptable on high-degree lattices. By observing the size reduction step of the original LLL algorithm, we propose a modified LLL algorithm in this thesis to improve the efficiency of LLL algorithm. The relationship between the public key and the private key of NTRU public-key cryptosystems makes the NTRU key recovery problem can be reduced to the SVP on lattices, and so can be solved by LLL algorithm. We compare the efficiency of the modified LLL algorithm and the original LLL algorithm. The comparison between these two algorithms in solving the NTRU key recovery problem shows that the modified LLL algorithm is superior to the original LLL algorithm.