Vulnerable Public Keys in NTRU Cryptosystem

Liqing Xu; Hao Chen; Chao Li; Longjiang Qu

doi:10.1007/s11401-020-0225-6

Chinese Annals of Mathematics, Series B ›› 2020, Vol. 41 ›› Issue (5) : 657 -664. DOI: 10.1007/s11401-020-0225-6

Article

Vulnerable Public Keys in NTRU Cryptosystem

Liqing Xu ¹^,^a
, Hao Chen ¹^,^b
, Chao Li ²^,^c
, Longjiang Qu ²^,^d

Author information +

History +

PDF

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

Cite this article

Download citation ▾

Liqing Xu, Hao Chen, Chao Li, Longjiang Qu. Vulnerable Public Keys in NTRU Cryptosystem. Chinese Annals of Mathematics, Series B, 2020, 41(5): 657-664 DOI:10.1007/s11401-020-0225-6

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

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