Message recovery attack on NTRU using a lattice independent from the public key

Marios Adamoudis; Konstantinos A. Draziotis

doi:10.3934/amc.2023040

Article Contents

2025, Volume 19, Issue 1: 109-125. Doi: 10.3934/amc.2023040

This issue Previous Article Construction of extremal $ \mathbb{Z}_{4} $-codes using a neighborhood search algorithm Next Article New bounds for covering codes of radius 3 and codimension $ 3t+1 $

Message recovery attack on NTRU using a lattice independent from the public key

Marios Adamoudis^1, and
Konstantinos A. Draziotis^2, ,

1.
Department of Mathematics, Aristotle University of Thessaloniki, 54 124, Thessaloniki, Greece
2.
Department of Informatics, Aristotle University of Thessaloniki, 54 124, Thessaloniki, Greece

^*Corresponding author: Konstantinos A. Draziotis
^*Corresponding author: Konstantinos A. Draziotis

Received: September 2022

Revised: September 2023

Early access: October 2023

Published: February 2025

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

In the present paper, we introduce a new attack on NTRU-HPS cryptosystem using lattice theory and Babai's Nearest Plane Algorithm. This attack generalizes the classic CVP attack on NTRU. We present numerical data in support of the validity of our result.

Keywords:

Mathematics Subject Classification: 94A60, 11T71, 11H06, 68R01.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	M. Adamoudis, K. A. Draziotis and D. Poulakis, Enhancing an attack to DSA schemes, Algebraic Informatics, Lecture Notes in Comput. Sci., Springer, Cham, 11545 (2019), 13-25. doi: 10.1007/978-3-030-21363-3_2.
[2]	M. Adamoudis, K. A. Draziotis and D. Poulakis, Attacking (EC)DSA with partially known multiples of nonces, Cryptology ePrint Archive, (2021), https://eprint.iacr.org/2021/347.
[3]	M. Albrecht, S. Bai and L. Ducas, A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and graded encoding schemes, Advances in Cryptology-CRYPTO 2016. Part Ⅰ, Lecture Notes in Comput. Sci., Springer, Berlin, 9814 (2016), 153–178 doi: 10.1007/978-3-662-53018-4_6.
[4]	F. Aydin, A. Aysu, M. Tiwari, A. Gerstlauer and M. Orshansky, Horizontal side-channel vulnerabilities of post-quantum key exchange and encapsulation protocols, ACM Transactions on Embedded Computing Systems, 20 (2021), 1-22. doi: 10.1145/3476799.
[5]	L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986), 1-13. doi: 10.1007/BF02579403.
[6]	D. J. Bernstein, B. B. Brumley, M.-S. Chen, C. Chuengsatiansup, T. Lange, A. Marotzke, B.-Y. Peng, N. Tuveri, C. van Vredendaal and B.-Y. Yang, NTRU prime: Reducing attack surface at low cost, Selected areas in cryptography—SAC 2017, Lecture Notes in Comput. Sci., Springer, Cham, 10719 (2018), 235–260. https://ntruprime.cr.yp.to/warnings.html. doi: 10.1007/978-3-319-72565-9_12.
[7]	D. J. Bernstein, C. Chuengsatiansup, T. Lange and C. van Vredendaal, NTRU prime: Reducing attack surface at low cost, Selected Areas in Cryptography-SAC 2017, Lecture Notes in Comput. Sci., Springer, Cham, 10719 (2018), 235–260. doi: 10.1007/978-3-319-72565-9_12.
[8]	J. A. Buchmann, F. Göpfert, R. Player and T. Wunderer, On the hardness of LWE with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack, Progress in Cryptology—AFRICACRYPT 2016, Lecture Notes in Comput. Sci., Springer, 9646 (2016), 24–43. doi: 10.1007/978-3-319-31517-1_2.
[9]	J. H. Cheon, J. Jeong and C. Lee, An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero, LMS J. Comput. Math., 19 (2016), 255-266. doi: 10.1112/S1461157016000371.
[10]	G. Bourgeois and J.-C. Faugère, Algebraic attack on NTRU using Witt vectors and Gröbner bases, Journal of Mathematical Cryptology, 3 (2009), 205-214. doi: 10.1515/JMC.2009.011.
[11]	C. Chen, O. Danba, J. Hoffstein, A. Hülsing, J. Rijneveld, J. M. Schanck, T. Saito, P. Schwabe, W. Whyte, K. Xagawa, T. Yamakawa and Z. Zhang, Algorithm specifications and supporting documentation, The round 3 NIST submission package, https://ntru.org.
[12]	D. Coppersmith and A. Shamir, Lattice attacks on NTRU, Advances in Cryptology—EUROCRYPT '97 (Konstanz), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 1233 (1997), 52–61. doi: 10.1007/3-540-69053-0_5.
[13]	A. Esser, A. May, J. Verbel and W. Wen, Partial key exposure attacks on BIKE, Rainbow and NTRU, Advances in Cryptology-CRYPTO 2022. Part Ⅲ, Lecture Notes in Comput. Sci., Springer, Cham, 13509 (2022), 346–375. doi: 10.1007/978-3-031-15982-4_12.
[14]	Fpylll, The FPLLL development team, fpylll, a Python wraper for the fplll lattice reduction library, Version: 0.5.6, (2021), available at https://github.com/fplll/fpylll.
[15]	N. Gama and P. Q. Nguyen, New chosen-ciphertext attacks on NTRU, Public Key Cryptography-PKC 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4450 (2007), 89–106. doi: 10.1007/978-3-540-71677-8_7.
[16]	C. Gentry, Key recovery and message attacks on NTRU-composite, Advances in Cryptology-EUROCRYPT 2001 (Innsbruck), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 2045 (2001), 182–194. doi: 10.1007/3-540-44987-6_12.
[17]	A. Hülsing, J. Rijneveld, J. Schanck and P. Schwabe, High-speed key encapsulation from NTRU, Cryptographic Hardware and Embedded Systems – CHES 2017, LNCS, Springer-Verlag, 10529 (2017), 232–252, https://link.springer.com/chapter/10.1007/978-3-319-66787-4_12.
[18]	J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, Algorithmic Number Theory (Portland, OR, 1998), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 1423 (1998), 267–288. doi: 10.1007/BFb0054868.
[19]	N. Howgrave-Graham, A hybrid lattice-reduction and meet-in-the-middle attack against NTRU, Advances in Cryptology-CRYPTO 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4622 (2007), 150–169. doi: 10.1007/978-3-540-74143-5_9.
[20]	N. Howgrave-Graham, J. H. Silverman and W. Whyte, Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3, Topics in Cryptology-CT-RSA 2005, Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 3376 (2005), 118–135. doi: 10.1007/978-3-540-30574-3_10.
[21]	N. Howgrave-Graham, J. H. Silverman and W. Whyte, Meet-in-the-middle Attack on an NTRU private key, Technical report, NTRU Cryptosystems, (2006), available at http://www.ntru.org.
[22]	OPENSSH 9.0, https://www.openssh.com/txt/release-9.0
[23]	A. A. Kamal and A..M. Youssef, A scan-based side channel attack on the NTRUEncrypt cryptosystem, ARES '12: Proceedings of the 2012 Seventh International Conference on Availability, Reliability and Security, (2012), 402-409. doi: 10.1109/ARES.2012.14.
[24]	P. Kirchner and P. A. Fouque, Revisiting lattice attacks on overstretched NTRU parameter, Advances in Cryptology-EUROCRYPT 2017. Part Ⅰ, Lecture Notes in Comput. Sci., Springer, Cham, 10210 (2017), 3–26. doi: 10.1007/978-3-319-56620-7_1.
[25]	A. May, Cryptanalysis of NTRU (preprint), (1999), http://citeseerx.ist.psu.edu/viewdoc/summary?doi = 10.1.1.41.3484.
[26]	H. Minkowski, Bibliotheca Mathematica Teubneriana, Band 40 Johnson Reprint Corp., New York-London 1968.
[27]	P. Q. Nguyen, Boosting the Hybrid attack on NTRU: Torus LSH, permuted HNF and boxed sphere, Computer Science, Mathematics, (2021).
[28]	NTRU Prime FAQ team, FAQ, (2022), https://ntruprime.cr.yp.to/faq.html.
[29]	NIST, 3rd round candidate announcement, (2022), https://csrc.nist.gov/news/2020/pqc-third-round-candidate-announcement.
[30]	K. G. Paterson and R. Villanueva-Polanco, Cold boot attacks on NTRU, Progress in Cryptology-INDOCRYPT 2017, Lecture Notes in Comput. Sci., Springer, Cham, 10698 (2017), 107–125. doi: 10.1007/978-3-319-71667-1_6.
[31]	Sage Mathematics Software, The Sage Development Team (version 8.1), http://www.sagemath.org.
[32]	A. Salvanos, The NTRU cryptosystem and attacks on the private key, Master Thesis, Math. Department, Aristotle University of Thessaloniki, Greece, (2018), http://ikee.lib.auth.gr/record/303247/files/GRI-2019-23739.pdf.
[33]	P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), IEEE Computer Society Press, Los Alamitos, CA, (1994), 124–134. doi: 10.1109/SFCS.1994.365700.
[34]	J. H. Silverman, Dimension-reduced lattices, zero-forced lattices, and the NTRU public key cryptosystem, Technical Report 13, Version 1, NTRU Cryptosystems, (1999).
[35]	H. Silverman, N. P. Smart and F. Vercauteren, An algebraic approach to NTRU ($q = 2n$) via Witt vectors and overdetermined systems of non linear equations, Security in Communication Networks – SCN 2004, Springer, 3352 (2005), 278-298.
[36]	N. V. Vizev, Side Channel Attacks on NTRUEncrypt, Bachelor Thesis, University of Technology Darmstadt, Department of Computer Science, 2007.
[37]	T. Wunderer, A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack, Journal of Mathematical Cryptology, 13 (2019), 1-26. doi: 10.1515/jmc-2016-0044.
[38]	Z. Xu, O. Pemberton, D. Oswald and Z. Zheng, Reveal the invisible secret: Chosen-ciphertext side-channel attacks on NTRU, CARDIS 2022, Springer, 13820 (2023), 227-247.