Lattice Base Reduction Attack on Matrix NTRU

• Thiago do Rêgo Sousa CEPESC-ABIN
• Tertuliano Souza Neto CEPESC-ABIN

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

Resumo

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. In addition, we give sufficient conditions to avoid decryption failure for the Matrix NTRU.

Referências

Albrecht, M. and Ducas, L. (2021). Lattice attacks on ntru and lwe: a history of refinements. Cryptology ePrint Archive.

Bi, J. and Han, L. (2021). Lattice attacks on ntru revisited. IEEE Access, 9:66218–66222.

Bremner, M. (2011). Lattice basis reduction. CRC Press New York.

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.

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.

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.

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.

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.

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.

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.

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

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.

Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische annalen, 261:515–534.

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.

Mamdikar, M. R., Kumar, V., and Ghosh, D. (2018). Implementation of automatic invertible matrix mechanism in ntru matrix formulation algorithm.

May, A. and Silverman, J. H. (2001). Dimension reduction methods for convolution modular lattices. In International Cryptography and Lattices Conference, pages 110–125. Springer.

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

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.

Nayak, R., Pradhan, J., and Sastry, C. (2012). Evaluation of performance characteristics of polynomial based and lattice based nrtu cryptosystem.

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].

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.

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.

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.

Wijayanti, I. E. et al. (2023). 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.

Zhao, Z. and Ye, Q. (2023). Revisiting lower dimension lattice attacks on ntru. Information Processing Letters, 181:106353.