On the hardness of NTRU problems

Abstract

The hardness of NTRU problem affects heavily on the securities of the cryptosystems based on it. However, we could only estimate the hardness of the specific parameterized NTRU problems from the perspective of actual attacks, and whether there are worst-case to average-case reductions for NTRU problems like other lattice-based problems (e.g., the Ring-LWE problem) is still an open problem. In this paper, we show that for any algebraic number field K, the NTRU problem with suitable parameters defined over the ring of integers R is at least as hard as the corresponding Ring-LWE problem. Hence, combining known reductions of the Ring-LWE problem, we could reduce worst-case basic ideal lattice problems, e.g., SIVP {}_{\gamma } problem, to average-case NTRU problems. Our results also mean that solving a kind of average-case SVP {}_{\gamma } problem over highly structured NTRU lattice is at least as hard as worst-case basic ideal lattice problems in K. As an important corollary, we could prove that for modulus q=\tilde{O}(n^{5.5}), average-case NTRU problem over arbitrary cyclotomic field K with [K:\mathbb{Q}]=n is at least as hard as worst-case SIVP {}_{\gamma } problems over K with \gamma =\tilde{O}(n^6).

Keywords

lattice-based cryptography / algebraic nmber fields / NTRU Problems / Ring-LWE / computational complexity

References

[1] Hoffstein J, Pipher J, Silverman J H. NTRU: a ring-based public key cryptosystem. In: Proceedings of the 3rd International Algorithmic Number Theory Symposium. 1998, 267– 288

[2] Hoffstein J, Howgrave-Graham N, Pipher J, Silverman J H, Whyte W. NTRUsign: digital signatures using the NTRU lattice. In: Proceedings of Cryptographers’ Track at the RSA Conference. 2003, 122– 140

[3] Coppersmith D, Shamir A. Lattice attacks on NTRU. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 1997, 52– 61

[4] 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 36th Annual International Cryptology Conference. 2016, 153– 178

[5] 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 Journal of Computation and Mathematics, 2016, 19( A): 255– 266

[6] Ducas L, Nguyen P Q. Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures. In: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security. 2012, 433– 450

[7] Gentry C. Key recovery and message attacks on NTRU-composite. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 2001, 182– 194

[8] Gama N, Nguyen P Q. New chosen-ciphertext attacks on NTRU. In: Proceedings of the 10th International Workshop on Public Key Cryptography. 2007, 89– 106

[9] Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Proceedings of the 27th Annual International Cryptology Conference. 2007, 150– 169

[10] Jaulmes É, Joux A. A chosen-ciphertext attack against NTRU. In: Proceedings of the 20th Annual International Cryptology Conference. 2000, 20– 35

[11] Kirchner P, Fouque P A. Revisiting lattice attacks on overstretched NTRU parameters. In: Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2017, 3– 26

[12] NIST . Post-quantum cryptography, round 3 submissions. csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions. 2020

[13] Peikert C . A decade of lattice cryptography. Foundations and trends® in theoretical computer science, 2016, 10( 4): 283– 424

[14] Peikert C, Regev O, Stephens-Davidowitz N. Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 2017, 461– 473

[15] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2010, 1– 23

[16] Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. In: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2011, 27– 47

[17] Yu Y, Xu G, Wang X. Provably secure NTRU instances over prime cyclotomic rings. In: Proceedings of the 20th IACR International Workshop on Public Key Cryptography. 2017, 409– 434

[18] Wang Y, Wang M Q. Provably secure NTRUEncrypt over any cyclotomic field. In: Proceedings of the 25th International Conference on Selected Areas in Cryptography. 2018, 391– 417

[19] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 197– 206

[20] Langlois A , Stehlé D . Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015, 75( 3): 565– 599

[21] Micciancio D , Regev O . Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, 2007, 37( 1): 267– 302

[22] Regev O . On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009, 56( 6): 34–

[23] Banaszczyk W . New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 1993, 296( 1): 625– 635

[24] Albrecht M R , Player R , Scott S . On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 2015, 9( 3): 169– 203

[25] Chiani M , Dardari D , Simon M K . New exponential bounds and approximations for the computation of error probability in fading channels. IEEE Transactions on Wireless Communications, 2003, 2( 4): 840– 845

[26] Lyubashevsky V, Peikert C, Regev O. A toolkit for ring-LWE cryptography. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 35– 54

[27] Cohen H. A Course in Computational Algebraic Number Theory. Berlin, Heidelberg: Springer, 1993

[28] Rosca M, Stehlé D, Wallet A. On the ring-LWE and polynomial-LWE problems. In: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2018, 146– 173

[29] Liu F H, Wang Z. Rounding in the rings. In: Proceedings of the 40th Annual International Cryptology Conference. 2020, 296– 326

[30] Pellet-Mary A, Stehlé D. On the hardness of the NTRU problem. In: Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security. 2021, 3– 35

RIGHTS & PERMISSIONS

Higher Education Press