Hawk / Falcon: keygen improvement

[Thomas Pornin]

Hello all,

I found a small improvement in the process used to solve the NTRU equation, as used in the keygen of Falcon (soon FN-DSA) and Hawk (and also the KEM scheme BAT); it is described there: https://eprint.iacr.org/2025/1239

In a nutshell, the bulk of the work can be done on f and F alone, instead of (f,g) and (F,G), so the number of operations is reduced (it is faster) and, maybe more importantly, it needs less RAM. RAM usage if often the bottleneck on small embedded systems (microcontrollers); this is relevant in particular for Hawk, whose signature generation uses less RAM than the keygen.

As an example, on an ARM Cortex-M4 with degree n=512 ("level 1" security), Hawk keygen cost goes down from 47.92m to 38.56m cycles (on average), while RAM usage is reduced, from 13312 bytes down to 11264 bytes.

The new code has been integrated in the Hawk reference and optimized implementations, available on: https://github.com/hawk-sign/dev

Thomas