On the hardness of NTRU problems

doi:10.1007/s11704-021-1073-6

Front. Comput. Sci.

2022, Vol. 16

Issue (6) : 166822 https://doi.org/10.1007/s11704-021-1073-6

RESEARCH ARTICLE

On the hardness of NTRU problems

Yang WANG^1,², Mingqiang WANG^1,²(

)

¹. School of Mathematics, Shandong University, Jinan 250100, China
². Key Laboratory of Cryptologic Technology and Information Security, Shandong University, Jinan 250100, China

Download: PDF(1274 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 $γ$ problem, to average-case NTRU problems. Our results also mean that solving a kind of average-case SVP $γ$ 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 = O ~ (n 5.5)$ , average-case NTRU problem over arbitrary cyclotomic field $K$ with $[K : Q] = n$ is at least as hard as worst-case SIVP $γ$ problems over $K$ with $γ = O ~ (n 6)$ .

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

Corresponding Author(s): Mingqiang WANG

Just Accepted Date: 06 August 2021 Issue Date: 28 January 2022

Cite this article:

Yang WANG,Mingqiang WANG. On the hardness of NTRU problems[J]. Front. Comput. Sci., 2022, 16(6): 166822.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-021-1073-6
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I6/166822

1	J Hoffstein, J Pipher, J H Silverman. NTRU: a ring-based public key cryptosystem. In: Proceedings of the 3rd International Algorithmic Number Theory Symposium. 1998, 267– 288
2	J Hoffstein, N Howgrave-Graham, J Pipher, J H Silverman, W Whyte. NTRUsign: digital signatures using the NTRU lattice. In: Proceedings of Cryptographers’ Track at the RSA Conference. 2003, 122– 140
3	D Coppersmith, A Shamir. Lattice attacks on NTRU. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 1997, 52– 61
4	M Albrecht, S Bai, L Ducas. 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	J H Cheon , J Jeong , C Lee . 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	L Ducas, P Q Nguyen. 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	C Gentry. 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	N Gama, P Q Nguyen. New chosen-ciphertext attacks on NTRU. In: Proceedings of the 10th International Workshop on Public Key Cryptography. 2007, 89– 106
9	N Howgrave-Graham. 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, A Joux. A chosen-ciphertext attack against NTRU. In: Proceedings of the 20th Annual International Cryptology Conference. 2000, 20– 35
11	P Kirchner, P A Fouque. 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	C Peikert . A decade of lattice cryptography. Foundations and trends® in theoretical computer science, 2016, 10( 4): 283– 424
14	C Peikert, O Regev, N Stephens-Davidowitz. 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	V Lyubashevsky, C Peikert, O Regev. 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	D Stehlé, R Steinfeld. 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	Y Yu, G Xu, X Wang. Provably secure NTRU instances over prime cyclotomic rings. In: Proceedings of the 20th IACR International Workshop on Public Key Cryptography. 2017, 409– 434
18	Y Wang, M Q Wang. Provably secure NTRUEncrypt over any cyclotomic field. In: Proceedings of the 25th International Conference on Selected Areas in Cryptography. 2018, 391– 417
19	C Gentry, C Peikert, V Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 197– 206
20	A Langlois , D Stehlé . Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015, 75( 3): 565– 599
21	D Micciancio , O Regev . Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, 2007, 37( 1): 267– 302
22	O Regev . On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009, 56( 6): 34–
23	W Banaszczyk . New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 1993, 296( 1): 625– 635
24	M R Albrecht , R Player , S Scott . On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 2015, 9( 3): 169– 203
25	M Chiani , D Dardari , M K Simon . 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	V Lyubashevsky, C Peikert, O Regev. 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	H Cohen. A Course in Computational Algebraic Number Theory. Berlin, Heidelberg: Springer, 1993
28	M Rosca, D Stehlé, A Wallet. 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	F H Liu, Z Wang. Rounding in the rings. In: Proceedings of the 40th Annual International Cryptology Conference. 2020, 296– 326
30	A Pellet-Mary, D Stehlé. 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

[1]

Download

[1]	Ismael RODRÍGUEZ, David RUBIO, Fernando RUBIO. Complexity of adaptive testing in scenarios defined extensionally[J]. Front. Comput. Sci., 2023, 17(3): 173206-.
[2]	Momeng LIU, Yupu HU. Universally composable oblivious transfer from ideal lattice[J]. Front. Comput. Sci., 2019, 13(4): 879-906.
[3]	Qingliang CHEN,Kaile SU,Abdul SATTAR,Xiangyu LUO,Aixiang CHEN. A first-order coalition logic for BDI-agents[J]. Front. Comput. Sci., 2016, 10(2): 233-245.
[4]	Silvano COLOMBO TOSATTO,Pierre KELSEN,Qin MA,Marwane el KHARBILI,Guido GOVERNATORI,Leendert van der TORRE. Algorithms for tractable compliance problems[J]. Front. Comput. Sci., 2015, 9(1): 55-74.
[5]	Mingming JIANG,Yupu HU,Hao LEI,Baocang WANG,Qiqi LAI. Lattice-based certificateless encryption scheme[J]. Front. Comput. Sci., 2014, 8(5): 828-836.
[6]	Xiuhua LU,Qiaoyan WEN,Zhengping JIN,Licheng WANG,Chunli YANG. A lattice-based signcryption scheme without random oracles[J]. Front. Comput. Sci., 2014, 8(4): 667-675.

Viewed

Full text

Abstract

Cited

Shared

Discussed