Cutting dimensions in the LLL attack for the ETRU post-quantum cryptosystem
Resumo
NTRU is one of the most important post-quantum cryptosystems nowadays, based on polynomial rings with coefficients in Z. Among its variants, the ETRU cryptosystem utilizes Eisenstein integers Z[ω], where ω is a primitive cube root of unity. We explore this cryptosystem and introduce a new lattice based on May’s technique, which proposes reducing the original lattice dimension to enable attacks with increased complexity. This new lattice allowed us to recover the private key of the ETRU system for a dimension that was not yet possible using current lattice reduction techniques over the original lattice.Referências
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.
Daniel J. Bernstein, Tanja Lange, Chitchanok Chuengsatiansup, and Peter Schwabe (Accessed: 2024). NTRU Prime. [link]. Website.
Diffie W, H. M. (1976). New directions in cryptography. In IEEE Transactions on Information Theory, 22:644–654.
Gama, N. and Nguyen, P. Q. (2007). New chosen-ciphertext attacks on ntru. In International Workshop on Public Key Cryptography, pages 89–106. 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.
Jaulmes, É. and Joux, A. (2000). A chosen-ciphertext attack against ntru. In Annual international cryptology conference, pages 20–35. Springer.
Karbasi, A. H. and Atani, R. E. (2015). Iltru: An ntru-like public key cryptosystem over ideal lattices. International Association for Cryptologic Research, Cryptology ePrint Archive:549–558.
Katherine Jarvis, M. N. (2015). Etru: Ntru over the eisenstein integers. Designs, Codes and Cryptography, 74:219–242.
Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische annalen, 261:515–534.
Lyu, S., Porter, C., and Ling, C. (2020). Lattice reduction over imaginary quadratic fields. IEEE Transactions on Signal Processing, 68:6380–6393.
Lyubashevsky, V. and Micciancio, D. (2009). On bounded distance decoding, unique shortest vectors, and the minimum distance problem. Lecture Notes in Computer Science, 5677:450–461.
May, A. (1999). Cryptanalysis of ntru. unpublished.
May A, S. J. (2001). Dimension reduction methods for convolutional modular lattices. Lecture Notes in Computer Science, 2146:110–125.
Monica Nevins, Camelia KarimianPour, A. M. (2010). Ntru over rings beyond z. Designs, Codes and Cryptography, 56:65–78.
Neal, K. (1987). Elliptic curves cryptosystems. Mathematics of Computation, 48:203–209.
Nguyen, P. Q. (2010). Hermite’s constant and lattice algorithms, the lll algorithm: Survey’s and applications. Information Security and Cryptography, pp:16–69.
NIST. Post-Quantum Cryptography Standardization. [link].
NIST (2019). Digital Signature Standard (DSS). [link].
Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of ACM, 56 no. 6:no. 6.
Rivest RL., Shamir A., A. L. (1978). A method for obtaining digital signatures and public key cryptosystem. Communications of the ACM, 21:120–126.
S. Lyu, C. P. and Ling, C. (2020). Lattice reduction over imaginary quadratic fields. IEEE Transactions on Signal Processing, 68:6380–6393.
Shor, P. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, page 124–134.
Sonika Singh, S. P. (2016). Generalizations of the ntru cryptosystem. 9:4823–6411.
Zhu, Z. and Tian, F. (2021). Comparison and intelligent analysis of ntru and etru signature algorithms for public key digital signature. Journal of Physics: Conference Series, 2083 no. 4:42009.
Daniel J. Bernstein, Tanja Lange, Chitchanok Chuengsatiansup, and Peter Schwabe (Accessed: 2024). NTRU Prime. [link]. Website.
Diffie W, H. M. (1976). New directions in cryptography. In IEEE Transactions on Information Theory, 22:644–654.
Gama, N. and Nguyen, P. Q. (2007). New chosen-ciphertext attacks on ntru. In International Workshop on Public Key Cryptography, pages 89–106. 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.
Jaulmes, É. and Joux, A. (2000). A chosen-ciphertext attack against ntru. In Annual international cryptology conference, pages 20–35. Springer.
Karbasi, A. H. and Atani, R. E. (2015). Iltru: An ntru-like public key cryptosystem over ideal lattices. International Association for Cryptologic Research, Cryptology ePrint Archive:549–558.
Katherine Jarvis, M. N. (2015). Etru: Ntru over the eisenstein integers. Designs, Codes and Cryptography, 74:219–242.
Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische annalen, 261:515–534.
Lyu, S., Porter, C., and Ling, C. (2020). Lattice reduction over imaginary quadratic fields. IEEE Transactions on Signal Processing, 68:6380–6393.
Lyubashevsky, V. and Micciancio, D. (2009). On bounded distance decoding, unique shortest vectors, and the minimum distance problem. Lecture Notes in Computer Science, 5677:450–461.
May, A. (1999). Cryptanalysis of ntru. unpublished.
May A, S. J. (2001). Dimension reduction methods for convolutional modular lattices. Lecture Notes in Computer Science, 2146:110–125.
Monica Nevins, Camelia KarimianPour, A. M. (2010). Ntru over rings beyond z. Designs, Codes and Cryptography, 56:65–78.
Neal, K. (1987). Elliptic curves cryptosystems. Mathematics of Computation, 48:203–209.
Nguyen, P. Q. (2010). Hermite’s constant and lattice algorithms, the lll algorithm: Survey’s and applications. Information Security and Cryptography, pp:16–69.
NIST. Post-Quantum Cryptography Standardization. [link].
NIST (2019). Digital Signature Standard (DSS). [link].
Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of ACM, 56 no. 6:no. 6.
Rivest RL., Shamir A., A. L. (1978). A method for obtaining digital signatures and public key cryptosystem. Communications of the ACM, 21:120–126.
S. Lyu, C. P. and Ling, C. (2020). Lattice reduction over imaginary quadratic fields. IEEE Transactions on Signal Processing, 68:6380–6393.
Shor, P. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, page 124–134.
Sonika Singh, S. P. (2016). Generalizations of the ntru cryptosystem. 9:4823–6411.
Zhu, Z. and Tian, F. (2021). Comparison and intelligent analysis of ntru and etru signature algorithms for public key digital signature. Journal of Physics: Conference Series, 2083 no. 4:42009.
Publicado
16/09/2024
Como Citar
SILVA, Augusto Miguel Camillo; SOUSA, Thiago do Rêgo; SOUZA NETO, Tertuliano.
Cutting dimensions in the LLL attack for the ETRU post-quantum cryptosystem. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 24. , 2024, São José dos Campos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 154-164.
DOI: https://doi.org/10.5753/sbseg.2024.240859.
