Implementation Of Subfield Lattice Attack And Number Theoretic Transform

The NTRU public key cryptosystem was proposed in 1996.After about twen-ty years' cryptanalysis,NTRU remains secure.Most cryptographers believe the shortest vector problem on NTRU lattices are hard to solve.NTRU cryptosys-tems have many attractive features such as the key sizes are relatively small,high speed of encryption and decryption.NTRU cryptosystems are one of the most innovative schemes in post quantum cryptography.In the first part of this paper,we investigate a variant of NTRU problem called overstretched NTRU problem,in which the modulus q is super polyno-mial in the dimension n of NTRU lattice.In the 36th International Cryptology Conference(Crypto 2016),Albrecht et al.proposed a subfield lattice algorithm to attack this problem.Their algorithm maps an instance of NTRU problem to a subfield using the Norm mapping.Then they use lattice reduction algorithm to find a short vector(x',y')in the subfield lattice.Finally they lift the vector(x',y')back to the full field.However,the length of the shortest vector in the subfield lattice is hard to predict,if we use the theory of lattice reduction algo-rithm to derive an upper bound of the length of(x',y'),then that bound will not be very accurate because lattice reduction algorithm performs much better in practice.In order to make the attack viable in theory,we have to use a much larger modulus q.Therefore,we give an implementation of the subfield lattice algorithm in Python language to investigate the hardness of overstretched NTRU problem.The experiments we done using our implementation suggests that this algorithm is also effective for smaller modulus q than the parameters provid-ed by theoretical derivation.Our work shall be helpful for people who want to implement cryptosystems based on the overstretched NTRU problem.The task of multiplying two polynomials modulo XN + 1 is a fundamental operation in public key cryptosystems based on NTRU and RLWE problems.The practical efficiency of these cryptosystems rely on the efficiency of this operation.In the second part of the paper,we investigate how to multiply two polynomials modulo XN + 1 using a variant of Fourier transform called number theoretic transform(NTT for short).A direct application of number theoretic transform will require two 2N-dimensional NTT and one 2N-dimensional inverse NTT.Besides,an additional modulo XN + 1 operation is performed.By observing the NTT more closely,we find another algorithm which needs only two N-dimensional NTT and one N-dimensional inverse NTT.The iterative implementation of N dimensional NTT have to execute N log N/2 butterfly operations,which means our revised algorithm need only to execute butterfly operations in comparison with a direct application of NTT which have to execute butterfly operations.In addition,we have also implemented our revised algorithm using C language.The experiments we have done suggest that our algorithm performs 2x faster than the original algorithm.