SCIENCE CHINA Information Sciences, Volume 61 , Issue 5 : 059101(2018) https://doi.org/10.1007/s11432-017-9175-y

A lower dimension lattice attack on NTRU

More info
  • ReceivedJan 12, 2017
  • AcceptedJun 21, 2017
  • PublishedOct 30, 2017


There is no abstract available for this article.


This work was supported by National Natural Science Foundation of China (Grant Nos. 11531002, 61572026) and Open Foundation of State Key Laboratory of Cryptology.


Appendixes A and B.


[1] Hoffstein J, Pipher J, Silverman J H. NTRU: a ring-based public key cryptosystem. Algorithmic Number Theory, 1998, 1423: 267--288. Google Scholar

[2] Coppersmith D, Shamir A. Lattice attacks on NTRU. In: Proceedings of the 16th Annual International Conference on Theory and Application of Cryptographic Techniques, Konstanz, 1997. 52--61. Google Scholar

[3] Silverman J H, Whyte W. Estimating decryption failure probabilities for NTRUEncrypt. 2003. https://assets.onboardsecurity.com/static/downloads/NTRU/resources/NTRUTech018.pdf. Google Scholar

[4] Silverman J H. Dimension-reduced lattices, zero-forced lattices, and the NTRU public key cryptosystem. 1999. https://assets.securityinnovation.com/static/downloads/NTRU/resources/NTRUTech013.pdf. Google Scholar

[5] Shoup V. NTL: A Library for Doing Number Theory Version 5.5.2, 2010. http://shoup.net/ntl/. Google Scholar

[6] Chen Y M, Nguyen P Q. BKZ 2.0: better lattice security estimates. In: Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, 2011. 1--20. Google Scholar

[7] Albrecht M, Bai S, Ducas L. A subfield lattice attack on overstretched NTRU assumptions: cryptanalysis of some FHE and graded encoding schemes. In: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology. Berlin: Springer, 2016. 153--178. Google Scholar

[8] Cheon J H, Jeong J, Lee C. An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero. LMS J Comput Math, 2016, 19: 255-266 CrossRef Google Scholar

[9] Kirchner P, Fouque P A. Revisiting lattice attacks on overstretched NTRU parameters. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2017. 3--26. Google Scholar

  • Table 1   The results of expermients and target RHF
    $N$ 19 37 57 73 83 97 107
    $t$ 3 7 11 12 14 13 16
    $\text{Prob}(\boldsymbol{f}^{ls(k)}\in\mathcal{L})$ 1 0.999 0.975 0.999 0.967 0.998 0.723
    IN-Lattice attack 1.0436 1.0227 1.0148 1.0116 1.0102 1.0087 1.0079
    Zero-Force attack 1.0258 1.0134 1.0087 1.0067 1.0059 1.0049 1.0045
    CS attack 1.0215 1.0110 1.0071 1.0055 1.0049 1.0042 1.0038

    Algorithm 1 IN-Lattice attack

    Require:Fixed $N,~q,~d_g,~h$ and the probability $\text{Prob}(\boldsymbol{f}^{ls(k)}\in~\mathcal{L}_I)$;

    Output:A valid private key $\boldsymbol{f}'$;


    while $t<N$ do


    while ${\rm~count}<=~\lceil1/\text{Prob}(\boldsymbol{f}^{ls(k)}\in~\mathcal{L}_I)\rceil$ do

    Randomly choose a subset $I$ of $[N]$ such that $\#I=t$;

    Construct an IN-Lattice $\mathcal{L}_I$ with size $t$;

    Reduce $\mathcal{L}_I$;

    if the reduced basis contains a vector $\boldsymbol{v}$ which can be used to decrypt then


    Output $\boldsymbol{f}&apos;$, $t$ and break;

    end if


    end while


    end while

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号