TY - JOUR

T1 - An efficient lattice reduction using reuse technique blockwisely on NTRU

AU - Chung, Kyungmi

AU - Lee, Hyang Sook

AU - Lim, Seongan

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2016

Y1 - 2016

N2 - 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 n2 times faster at outputting an LLL-reduced basis than the LLL when applied to NTRU lattices of dimension n. In the case of small n, 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=22.

AB - 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 n2 times faster at outputting an LLL-reduced basis than the LLL when applied to NTRU lattices of dimension n. In the case of small n, 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=22.

KW - iLLL algorithm

KW - LLL algorithm

KW - NTRU lattice

KW - Reuse technique

UR - http://www.scopus.com/inward/record.url?scp=84977636391&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.05.029

DO - 10.1016/j.dam.2016.05.029

M3 - Article

AN - SCOPUS:84977636391

SN - 0166-218X

VL - 214

SP - 88

EP - 98

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -