Improved Decryption Bounds and Key Generation for Matrix NTRU over Integral Domain

• Thiago do Rêgo Sousa Cepesc http://orcid.org/0000-0002-0776-034X
• Tertuliano Souza Neto Cepesc https://orcid.org/0009-0000-1517-6023

DOI: https://doi.org/10.5753/sbseg.2025.9721

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 M_n(Z[ √ −3]) that makes the key generation significantly faster.

References

Chen, C., Danba, O., Hoffstein, J., Hulsing, A., Rijneveld, J., Schanck, J. M., Schwabe, P., Whyte, W., and Zhang, Z. (2020). Ntru: algorithm specifications and supporting documentation (2019). URL: [link], 1.

Coglianese, M. and Goi, B.-M. (2005). Matru: A new ntru-based cryptosystem. In Progress in Cryptology-INDOCRYPT 2005: 6th International Conference on Cryptology in India, Bangalore, India, December 10-12, 2005. Proceedings 6, pages 232–243. Springer.

Daniel J. Bernstein, Tanja Lange, Chitchanok Chuengsatiansup, and Peter Schwabe (Accessed: 2024). NTRU Prime. [link]. Website.

Gama, N. and Nguyen, P. Q. (2007). New chosen-ciphertext attacks on ntru. In International Workshop on Public Key Cryptography, pages 89–106. Springer.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219.

Hoffstein, J., Pipher, J., and Silverman, J. H. (1998). Ntru: A ring-based public key cryptosystem. In International algorithmic number theory symposium, pages 267–288. Springer.

Hungerford, T. W. (2012). Algebra, volume 73. Springer Science & Business Media.

Jaulmes, É. and Joux, A. (2000). A chosen-ciphertext attack against ntru. In Annual international cryptology conference, pages 20–35. Springer.

Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177):203–209.

Miller, V. S. (1985). Use of elliptic curves in cryptography. In Conference on the theory and application of cryptographic techniques, pages 417–426. Springer.

Mittal, S. and Ramkumar, K. (2022). A retrospective study on ntru cryptosystem. In AIP Conference Proceedings, volume 2451. AIP Publishing.

Monica Nevins, Camelia KarimianPour, A. M. (2010). Ntru over rings beyond z. Designs, Codes and Cryptography, 56:65–78.

Nayak, R., Sastry, C., and Pradhan, J. (2008). A matrix formulation for ntru cryptosystem. In 2008 16th IEEE International Conference on Networks, pages 1–5. IEEE.

NIST. Post-Quantum Cryptography Standardization. [link].

Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.

Salleh, N. and Kamarulhaili, H. (2020). Ntru public-key cryptosystem and its variants: An overview. Int. l J. of Cryptology Research, 10(1):1–21.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee.

Silverman, J. H., Pipher, J., and Hoffstein, J. (2008). An introduction to mathematical cryptography, volume 1. Springer.

Singh, S. and Padhye, S. (2016). Generalisations of ntru cryptosystem. Security and Communication Networks, 9(18):6315–6334.

Sousa, T. and Neto, T. S. (2024). Lattice base reduction attack on matrix ntru. In Anais do XXIV Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, pages 431–444, Porto Alegre, RS, Brasil. SBC.

Wijayanti, I. E., Isnaini, U., Sari, A. K., Ali, S., and Aji, N. C. (2023). Matrix ntru cryptosystem over integral domain. In 2023 IEEE International Conference on Cryptography, Informatics, and Cybersecurity (ICoCICs), pages 35–40. IEEE.