Algorithms for the Generalized NTRU Equations and their Storage Analysis

• Autorzy: Cho Gook Hwa , Lim Seongan , Lee Hyang-Sook

Identyfikatory

DOI

10.3233/FI-2020-1982

• Języki publikacji: EN

Abstrakty

EN

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 ℓ ≥ 3. For ℓ = 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 ℓ ≥ 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 ℓ ≥ 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 (ℓ² n ² logB ) and that of the algorithm using a field norm is O (ℓ² n logB ), 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 ℓ = 3 and the average storage requirements for ℓ = 3, 4.

Słowa kluczowe

EN

NTRU; LATTE; hierarchical identity based encryption

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 2
• Strony: 115--139
• Opis fizyczny: Bibliogr. 15 poz., tab.

Twórcy

autor

Cho Gook Hwa

• Institute of Mathematical Sciences, Ewha Womans University Seoul, Republic of Korea

autor

Lim Seongan

• Institute of Mathematical Sciences, Ewha Womans University Seoul, Republic of Korea

autor

Lee Hyang-Sook

• Department of Mathematics, Ewha Womans University Seoul, Republic of Korea

Bibliografia

• [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.
• [2] Stehlé 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. Springer, Berlin, Heidelberg, 2011. Lecture Notes in Computer Science, 6632: 27-47. doi:10.1007/978-3-642-20465-4_4.
• [3] Pöppelmann T, Güneysu, 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.
• [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.
• [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.
• [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.
• [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.
• [11] Babai L. On Lovász‘ lattice reduction and the nearest lattice point problem. Combinatorica,1986. 6(1):1-13. doi:10.1007/BF02579403.
• [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.
• [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.
• [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.
• [15] Sedjelmaci S M. Two fast parallel GCD algorithms of many integers. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, pp.397-404. doi:10.13140/RG.2.1.2399.0482.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).