An efficient lattice reduction using reuse technique blockwisely on NTRU

详细信息    查看全文

• 作者：Kyungmi Chung^a ; ^{thinkmi01@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Hyang-Sook Lee^a ; ^{hsl@ewha.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Seongan Lim^b ; ^{seongannym@ewha.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：NTRU lattice ; LLL algorithm ; iLLL algorithm ; Reuse technique
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 December 2016
• 年：2016
• 卷：214
• 期：Complete
• 页码：88-98
• 全文大小：560 K

文摘

In this paper, we propose a lattice reduction algorithm for use with NTRU lattices. Given an NTRU lattice as its input, the algorithm computes an LLL-reduced basis. The proposed lattice reduction algorithm is more efficient than the classical LLL algorithm. Recently, a lattice reduction algorithm for ideal lattices, named iLLL, was proposed by Plantard, Susilo, and Zhang. This algorithm is identical to that of the LLL except for the fact that it contains an additional subroutine, named Reuse. The subroutine serves to further reduce a set of short vectors that has already been computed by the algorithm prior to its initiation. As a result, the iLLL is able to output an LLL-reduced basis more efficiently than the LLL is able to do so. However, the iLLL cannot be directly applied to an NTRU lattice, because it is not an ideal lattice. Yet, from the fact that an NTRU lattice is also a module lattice (a generalization of an ideal lattice), we can adapt the main idea behind the iLLL blockwisely in our approach to NTRU lattices. We demonstrate that the proposed algorithm (containing a modified version of the aforementioned subroutine Reuse) is asymptotically mi>nmi>2 times faster at outputting an LLL-reduced basis than the LLL when applied to NTRU lattices of dimension nmi>nmi>. In the case of small nmi>nmi>, our experiments show that the proposed algorithm is slightly faster at outputting an LLL-reduced basis than the LLL. In addition, we present an example of how to recover a private key of an NTRU encryption scheme by using the proposed algorithm in the case of n=22mi>nmi>=22.