logo

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

Abstract

There is no abstract available for this article.


Acknowledgment

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


Supplement

Appendixes A and B.


References

[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

  •   

    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}'$;

    $t\leftarrow2$;

    while $t<N$ do

    ${\rm~count}\leftarrow~1$;

    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

    $\boldsymbol{f}'=\boldsymbol{v}$;

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

    end if

    ${\rm~count}={\rm~count}+1$;

    end while

    $t\leftarrow~t+1$;

    end while

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

京ICP备18024590号-1