Vulnerable Public Keys in NTRU Cryptosystem

Abstract

In this paper the authors give an efficient bounded distance decoding (BDD for short) algorithm for NTRU lattices under some conditions about the modulus number q and the public key h. They then use this algorithm to give plain-text recovery attack to NTRU Encrypt and forgery attack on NTRU Sign. In particular the authors figure out a weak domain of public keys such that the recent transcript secure version of NTRU signature scheme NTRUMLS with public keys in this domain can be forged.

Keywords

Lattice / CVP / NTRU Lattice

References

[1] Ajtai, M., The shortest vector problem in L ₂ is NP-hard for randomized reduction, STOC, 1998, 10–19.

[2] Albrecht, M. R., Shi, B. and Ducas, L., A subfield lattice attack on overstreched NTRU assumption cryptanalysis of some FHE and graded encoding schemes, Crytpology ePrint Archive, https://eprint.iacr.org/2016/127.

[3] Aono Y, Wang Y, Hayashi T, Takagi T. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. Advances in Cryptology-Eurocrypt 2016, 2016, Berlin: Spring-Verlag 789-819

[4] Bernstein D, Chuengsatiansup C, Lange T, van Vredendaal C. NTRU Prime: Reducing attack surface at low cost. Selected Areas in Cyptography-SAC 2017, 2018, Cham: Spring-Verlag 235-260

[5] Chen, Y. and Nguyen, P. Q., BKZ2.0: Better lattice security estimates, Asiacrypt 2011, Lecture Notes in Computer Science 7073, 1–20, http://www.di.ens.fr/ychen/research/.

[6] Ducas, L. and Nguyen, P. Q., Learning a zonotope and more: Cryptanalysis of NTRUSign countermeasuresm, Asiacrypt 2012, Lecture Notes in Computer Science 765, 433–450.

[7] Gentry, C. and Szydlo, M., Cryptanlysis of revised NTRU signature scheme, Eurocrypt 2002, Lecture Notes in Computer Science 2332, 299–320.

[8] Hoffstein J, Howgrave-Graham N, Pipher J, Whyte W. Nguyen P Q, Vallee B. Practical Lattice-Based Cryptography: N-TRU Encrypt and NTRU Sign. The LLL algorithms, Information Setting and Cryptogolgy, 2010, Berlin, Heidelberg: Springer-Verlag 349-390

[9] Hoffstein, J., Pipher, J., Schanck, J. M., et al., Transcript secure signatures based on modular lattices, version 2, https://eprint.iacr.org/2014/457. DOI: https://doi.org/10.1007/1978-3-642-02295-1-11

[10] Khot S. Hardness of approximating the shortest vector problem. Journal of ACM, 2005, 52: 789-808

[11] Lindner R. Current attacks on NTRU, 2006, HesseDarmstadt: Techology University of Darmstadt

[12] Micciancio D, Goldwasser S. Complexity of Lattice Problems, A Cryptographic Perspective, 2002, Boston, MA: Kluwer Academic Publishers

[13] Nguyen, P. Q. and Regev, Q., Learning a parallelpiped: Cryptanalysis of GGH and NTRU signatures, Eurocrytp 2006, Lecture Notes in Computer Science 4004, 215–233.

[14] Schanck J M. Practical lattice cryptosystems. NTRU Encrypt and NTRUMLS, 2015, Ontario: Waterloo University

[15] Silverman J H. NTRU and lattice-based crypto, Past, Presnet and Future. The mathematics of post-quantum cryptography, 2015, New Jersey: DIMACS Center, Rutgers University January 12–16

[16] Stehlé, D. and Steinfeld, R., Making NTRU Encrypt and NTRU Sign as secure as standard worst-case problems over ideal lattices, Eurocrypt 2011, Lecture Notes in Computer Science 6632, 24–47.