Algorithms for the Generalized NTRU Equations and their Storage Analysis
- 주제(키워드) NTRU , LATTE , hierarchical identity-based encryption
- 주제(기타) Computer Science, Software Engineering
- 주제(기타) Mathematics, Applied
- 설명문(일반) [Cho, Gook Hwa; Lim, Seongan] Ewha Womans Univ, Inst Math Sci, Seoul, South Korea; [Lee, Hyang-Sook] Ewha Womans Univ, Dept Math, Seoul, South Korea
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS
- 발행기관 IOS PRESS
- 발행년도 2020
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000175448
- 본문언어 영어
- Published As http://dx.doi.org/10.3233/FI-2020-1982
초록/요약
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 l >= 3. For l = 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 l >= 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 l >= 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(l(2)n(2) log B) and that of the algorithm using a field norm is O(l(2)n 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 l = 3 and the average storage requirements for l = 3, 4.
more