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

• AcceptedJun 21, 2017
• PublishedOct 30, 2017
Share
Rating

### 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

[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.011 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}&apos;$;

$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}&apos;=\boldsymbol{v}$;

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

end if

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

end while

$t\leftarrow~t+1$;

end while

• #### 2

Citations

• Altmetric

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