A Proposal of Solving NTRU Equation Using Matrix Representation Instead of Recursive Operation

As quantum computer becomes more practical in real world, classical cryptoststems might be broken in the near future. NIST has announced Post Quantum Cryptography (PQC) project to standardize the cryptographies that are not broken in polynomial time even using quantum computers. Falcon is one of the finalists of the NIST PQC project which is designed based on the NTRUsign. However, the computation time of key generation time is known to be slower than other schemes. In this paper, the authors introduce a novel algorithm to solve the NTRU equation, a major part of key generation, which enables parallel processing. It is designed based on the basic matrix operation.