Lattice Basis Reduction Attack on Matrix NTRU
DOI:
https://doi.org/10.5753/jbcs.2026.5486Keywords:
Post-quantum cryptography, NTRU, Matrix NTRU, Lattice cryptanalysis, Lattice attack, Decryption failure, CryptanalysisAbstract
NTRU is one of the most important post-quantum cryptosystems nowadays and since its introduction several variants have been proposed in the literature. In particular, the Matrix NTRU is a variant which replaces the NTRU polynomials by integer matrices. In this work, we develop a lattice-based reduction attack on the Matrix NTRU cryptosystem that allows us to recover the plaintext. We also show that this system is completely vulnerable to the proposed attack for parameters that could be used in practice. We show that this practical attack can also be extended by reducing the lattice dimension. In addition, we give sufficient conditions to avoid decryption failure for the Matrix NTRU.
Downloads
References
Albrecht, M. and Ducas, L. (2021). Lattice attacks on ntru and lwe: a history of refinements. Cryptology ePrint Archive. Available at:[link].
Bernstein, D. J., Chuengsatiansup, C., Lange, T., and van Vredendaal, C. (2017). Ntru prime: Reducing attack surface at low cost. In Selected Areas in Cryptography (SAC 2017), pages 235-260. Springer. DOI: 10.1007/978-3-319-72565-9_12.
Bi, J. and Han, L. (2021). Lattice attacks on ntru revisited. IEEE Access, 9:66218-66222. DOI: 10.1109/ACCESS.2021.3076598.
Bremner, M. (2011). Lattice basis reduction. CRC Press New York. DOI: 10.1201/b11066.
Chen, C., Danba, O., Hoffstein, J., Hulsing, A., Rijneveld, J., Schanck, J. M., Schwabe, P., Whyte, W., and Zhang, Z. (2020a). Ntru: algorithm specifications and supporting documentation (2019). 1. Available at:[link]
Chen, C., Danba, O., Hoffstein, J., Hülsing, A., Rijneveld, J., Schanck, J. M., Saito, T., Schwabe, P., Whyte, W., Xagawa, K., Yamakawa, T., and Zhang, Z. (2020b). NTRU algorithm specifications and supporting documentation. Section 6.3. DOI: 10.1007/978-1-4419-5906-5_464.
Chen, Y. and Nguyen, P. Q. (2011). Bkz 2.0: Better lattice security estimates. In International Conference on the Theory and Application of Cryptology and Information Security, pages 1-20. Springer. DOI: 10.1007/978-3-642-25385-0_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. DOI: 10.1007/11596219_19.
Coppersmith, D. and Shamir, A. (1997). Lattice attacks on ntru. In International conference on the theory and applications of cryptographic techniques, pages 52-61. Springer. DOI: doi.org/10.1007/3-540-69053-0_5.
do Rêgo Sousa, T. and Neto, T. S. (2025). Improved decryption bounds and key generation for matrix ntru over integral domain. In Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSeg), pages 515-528. SBC. DOI: doi.org/10.5753/sbseg.2025.9721.
Gama, N. and Nguyen, P. Q. (2007). New chosen-ciphertext attacks on ntru. In International Workshop on Public Key Cryptography, pages 89-106. Springer. DOI: 10.1007/978-3-540-71677-8_7.
Hall, C., Goldberg, I., and Schneier, B. (1999). Reaction attacks against several public-key cryptosystem. In Information and Communication Security: Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings 2, pages 2-12. Springer. DOI: 10.1007/978-3-540-47942-0_2.
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. DOI: 10.1007/bfb0054868.
Howgrave-Graham, N., Nguyen, P. Q., Pointcheval, D., Proos, J., Silverman, J. H., Singer, A., and Whyte, W. (2003). The impact of decryption failures on the security of ntru encryption. In Annual International Cryptology Conference, pages 226-246. Springer. DOI: 10.1007/978-3-540-45146-4_14.
Jacques-García, F. A., Uribe-Mejía, D., Macías-Bobadilla, G., and Chaparro-Sánchez, R. (2022). On modular inverse matrices a computation approach. South Florida Journal of Development, 3(3):3100-3111. DOI: 10.46932/sfjdv3n3-005.
Jaulmes, É. and Joux, A. (2000). A chosen-ciphertext attack against ntru. In Annual international cryptology conference, pages 20-35. Springer. DOI: 10.1007/3-540-44598-6_2.
Kumar, V., Mamdikar, M. R., and Gosh, D. (2013). Matrix formulation of ntru algorithm using multiple public keys from matrix data bank for high degree polynomials. In CEEE, pages 191-198. DOI: 10.15224/978-981-07-6260-5-40.
Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische annalen, 261:515-534. DOI: 10.1007/BF01457454.
Luo, X.-R. and Lin, C.-H. J. (2011). Discussion on matrix ntru. IJCSNS International Journal of Computer Science and Network Security, 11(1):32-35. Available at:[link].
Mamdikar, M. R., Kumar, V., and Ghosh, D. (2013). Implementation of automatic invertible matrix mechanism in ntru matrix formulation algorithm. Available at:[link]. Accessed: 2026-04-17.
May, A. (1999). Cryptanalysis of ntru. preprint, February. Available at:[link].
May, A. and Silverman, J. H. (2001). Dimension reduction methods for convolution modular lattices. In International Cryptography and Lattices Conference, pages 110-125. Springer. DOI: 10.1007/3-540-44670-2_10.
Mittal, S. and Ramkumar, K. (2022). A retrospective study on ntru cryptosystem. In AIP Conference Proceedings, volume 2451. AIP Publishing. DOI: 10.1063/5.0095312.
Nayak, R., Pradhan, J., and Sastry, C. (2011). Reaction attacks in the matrix scheme of ntru cryptosystem. In International Conference on Advances in Information Technology and Mobile Communication, pages 27-32. Springer. DOI: 10.1007/978-3-642-20573-6_5.
Nayak, R., Pradhan, J., and Sastry, C. V. (2012). Evaluation of performance characteristics of polynomial based and lattice based ntru cryptosystem. International Journal of Network Security. Available at:[link].
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. DOI: 10.1109/icon.2008.4772602.
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. Avaialble at:[link].
Silva, A., Sousa, T., and Neto, T. S. (2024). Cutting dimensions in the lll attack for the etru post-quantum cryptosystem. In Anais do XXIV Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, pages 154-164, Porto Alegre, RS, Brasil. SBC. DOI: 10.5753/sbseg.2024.240859.
Silverman, J. H., Pipher, J., and Hoffstein, J. (2008). An introduction to mathematical cryptography, volume 1. Springer. DOI: /10.1080/01611190902721016.
Singh, S. and Padhye, S. (2016). Generalisations of ntru cryptosystem. Security and Communication Networks, 9(18):6315-6334. DOI: 10.1002/sec.1693.
Team, S. D. (2024). SageMath. Available from [link].
Tripathi, B., Thakur, K., Nayak, R., Sastry, C., and Pradhan, J. (2016). Ntru cryptosystem with companion matrix. A matrix formulation for NTRU cryptosystem, pages 1-5. Available at:[link].
Wijayanti, I. E., Isnaini, U., Sari, A. K., Ali, S., and Aji, N. C. (2023a). Matrix ntru cryptosystem over integral domain. In 2023 IEEE International Conference on Cryptography, Informatics, and Cybersecurity (ICoCICs), pages 35-40. IEEE. DOI: 10.1109/ICoCICs58778.2023.10277330.
Wijayanti, I. E. et al. (2023b). The meet-in-the-middle attack on the matrix ntru cryptosystem. In 2023 IEEE International Conference on Cryptography, Informatics, and Cybersecurity (ICoCICs), pages 149-153. IEEE. DOI: 10.5753/sbseg.2024.240851.
Zhao, Z. and Ye, Q. (2023). Revisiting lower dimension lattice attacks on ntru. Information Processing Letters, 181:106353. DOI: 10.1016/j.ipl.2022.106353.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Thiago do Rego Sousa, Tertuliano Carneiro de Souza Neto
This work is licensed under a Creative Commons Attribution 4.0 International License.
