Improved Decryption Bounds and Key Generation for Matrix NTRU over Integral Domain
Thiago do Rêgo Sousa,Tertuliano Souza Neto
TLDR
There is an error on the condition to avoid decryption failures and the key generation process is not practical due to severe limitations on matrix inversion, so a corrected statement for the decryption failure theorem is proposed and an expansion of the set of solutions when dealing with the problem of inverting matrix in Mn(Z[ √ −3]) is proposed.
Abstract
Shor’s algorithm [Shor 1994] is the main threat to classical public-key cryptography. Since its introduction in 1996, NTRU and its variants aim to develop cryptographic algorithms that are secure even against quantum computers. In this work, we study the matrix NTRU over integral domains proposed in 2023. We found that there is an error on the condition to avoid decryption failures and the key generation process is not practical due to severe limitations on matrix inversion. We propose a corrected statement for the decryption failure theorem and an expansion of the set of solutions when dealing with the problem of inverting matrix in Mn(Z[ √ −3]) that makes the key generation significantly faster.