Algorithms for the generalized NTRU equations and their storage analysis. (English) Zbl 07350027

Summary: In LATTE, a lattice based hierarchical identity-based encryption (HIBE) scheme, each hierarchical level user delegates a trapdoor basis to the next level by solving a generalized NTRU equation of level \(\ell\geq 3\). For \(\ell=2\), Howgrave-Graham, Pipher, Silverman, and Whyte presented an algorithm using resultant and Pornin and Prest presented an algorithm using a field norm with complexity analysis. Even though their ideas of solving NTRU equations can be conceptually extended for \(\ell\geq 3\), no explicit algorithmic extensions with the storage analysis are known so far. In this paper, we interpret the generalized NTRU equation as the determinant of a matrix. By using the mathematical properties of the determinant, we show that how to construct algorithms for solving the generalized NTRU equation either using resultant or a field norm for any \(\ell\geq 3\). We also obtain an upper bound of the size of solutions by using the properties of the determinant. From our analysis, the storage requirement of the algorithm using resultant is \(O(\ell^2n^2\log B)\) and that of the algorithm using a field norm is \(O(\ell^2n\log B)\), where \(B\) is an upper bound of the coefficients of the input polynomials of the generalized NTRU equations. We present examples of our algorithms for \(\ell=3\) and the average storage requirements for \(\ell=3,4\).


68-XX Computer science


NTRU; NTRUSign; Falcon
Full Text: DOI


[1] Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem. International Algorithmic Number Theory Symposium, Algorithmic Number Theory 1998. Springer, Berlin, Heidelberg, 1998. Lecture Notes in Computer Science,1423: 267-288. doi:10.1007/BFb0054868. · Zbl 1067.94538
[2] Stehl´e D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2011.
[3] P¨oppelmann T, G¨uneysu, T. Towards practical lattice-based public-key encryption on reconfigurable hardware. International Conference on Selected Areas in Cryptography, Selected Areas in Cryptography 2013. Springer, Berlin, Heidelberg, 2013. Lecture Notes in Computer Science,8282: 68-85. doi: 10.1007/978-3-662-43414-7 4.
[4] Hoffstein J, Howgrave-Graham N, Pipher J, Silverman J H, Whyte W. NTRUSIGN: Digital signatures using the NTRU lattice. Cryptographers Track at the RSA Conference 2003. Springer, Berlin, Heidelberg, 2003. Lecture Notes in Computer Science,2612: 122-140. doi:10.1007/3-540-36563-X 9. · Zbl 1039.94525
[5] Fouque P-A, Hoffstein J, Kirchner P, Lyubashevsky V, Pornin T, Prest T. Falcon: Fast-Fourier lattice-based compact signatures over NTRU. Post-Quantum Cryptography Standardization Round 2 Submissions, 2019. Accessed 26 June 2020, https://falcon-sign.info/
[6] Ducas L, Lyubashevsky V, Prest T. Efficient identity-based encryption over NTRU lattices. International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2014. Springer, Berlin, Heidelberg, 2014. Lecture Notes in Computer Science,8874: 22-41. doi: 10.1007/978-3-662-45608-8 2. · Zbl 1317.94103
[7] Sarah M, Neil S, Elizabeth O. A Practical Implementation of Identity-Based Encryption over NTRU Lattices. IMA International Conference on Cryptography and Coding 2017. Lecture Notes in Computer Science,10655: 227-246. doi:10.1007/978-3-319-71045-7 12. · Zbl 1397.94089
[8] Campbell P, Groves M. Practical post-quantum hierarchical identity-based encryption. In 16th IMA International Conference on Cryptography and Coding, 2017.
[9] Cash D, Hofheinz D, Kiltz E, Peikert C. Bonsai trees, or how to delegate a lattice basis.Journal of cryptology, 2012.25(4):601-639. doi:10.1007/s00145-011-9105-2. · Zbl 1277.94017
[10] Pornin T, Prest T. More Efficient Algorithms for the NTRU Key Generation Using the Field Norm. IACR International Workshop on Public Key Cryptography 2019. Springer, Cham, 2019. Lecture Notes in Computer Science,11443: 504-533. doi:10.1007/978-3-030-17259-6 17. · Zbl 07159416
[11] Babai L. On Lov´asz‘ lattice reduction and the nearest lattice point problem.Combinatorica,1986.6(1):1- 13. doi:10.1007/BF02579403. · Zbl 0593.68030
[12] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008 pp. 197-206. doi: 10.1145/1374376.1374407. · Zbl 1231.68124
[13] Shweta A, Dan B, Xavier B. Efficient lattice (H)IBE in the standard model. International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2010. Springer, Berlin, Heidelberg, 2010. Lecture Notes in Computer Science,6110: 553-572. doi:10.1007/978-3-642-13190-5 28. · Zbl 1227.94022
[14] Shweta A, Dan B, Xavier B. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Cryptology Conference, CRYPTO 2010. Springer, Berlin, Heidelberg, 2010. Lecture Notes in Computer Science,6223: 98-115. doi:10.1007/978-3-642-14623-7 6. · Zbl 1280.94035
[15] Sedjelmaci S M.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.