Abstract
NTRU lattices use bases with a compact representation as polynomials; elements of a lattice of dimension $2n$ are encoded as a pair of polynomials with integer coefficients and taken modulo a given irreducible polynomial of degree $n$, usually $X^n+1$ (with $n$ a power of two). The private key is the knowledge of two polynomials $(f,g)$ with small coefficients. Some cryptographic algorithms based on NTRU lattices, in particular NTRUSign and Falcon, require a complete basis, i.e. two extra polynomials $F$ and $G$, also with small coefficients, that fulfill the NTRU equation: $fG - gF = q$, for a given small integer $q$. While generating $f$ and $g$ is simple, computing matching $F$ and $G$ requires considerable resources in CPU and RAM, making key pair generation inapplicable to small constrained systems.
In this presentation, we will show how the NTRU equation can be solved much more efficiently by using the field norm over a tower of fields. We first show a novel method for computing the resultant of a small polynomial with the modulus $X^n+1$; we will then draw on that method to solve the NTRU equation in a resource-efficient way. When applied to the Falcon signature system, RAM cost of key pair generation was reduced by a factor of more than 100 (from about 3 MB down to less than 30 kB) and CPU cost was also reduced by a similar factor (from about 2 seconds to 21 milliseconds). This allows the implementation of the whole of Falcon, including key pair generation, on embedded systems, with constant-time code (free of timing-based side channels).