TY - JOUR

T1 - Algorithms for the Generalized NTRU Equations and their Storage Analysis

AU - Cho, Gook Hwa

AU - Lim, Seongan

AU - Lee, Hyang Sook

N1 - Funding Information:
The research of Gook Hwa Cho was supported by NRF-2018R1D1A1B07041716 and NRF-2019R1A6A1A11051177. The research of Seongan Lim was supported by NRF-2016R1D1A1B01008562 and NRF-2018R1A2A1A05079095.
Funding Information:
The research of Hyang-Sook Lee was supported by MSIT (No. NRF-2018R1A2A1A05079095) and partially supported by the Ministry of Education (No. NRF-2019R1A6A1A11051177).
Publisher Copyright:
© 2020 - IOS Press and the authors. All rights reserved.

PY - 2020

Y1 - 2020

N2 - 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(ℓ2n2 logB) and that of the algorithm using a field norm is O(ℓ2n 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.

AB - 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(ℓ2n2 logB) and that of the algorithm using a field norm is O(ℓ2n 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.

KW - hierarchical identity-based encryption

KW - LATTE

KW - NTRU

UR - http://www.scopus.com/inward/record.url?scp=85098331269&partnerID=8YFLogxK

U2 - 10.3233/FI-2020-1982

DO - 10.3233/FI-2020-1982

M3 - Article

AN - SCOPUS:85098331269

SN - 0169-2968

VL - 177

SP - 115

EP - 139

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 2

ER -