Improving FALCON’s Key Generation on ARMv8-A Platforms - Teixeira, Caio; Gazzoni Filho, Décio Luiz; Hernández, Julio César López (Anais do Simpósio Brasileiro de Cibersegurança (SBSeg); 2023: Anais do XXIII Simpósio Brasileiro de Segurança da Informação e de Sistemas ComputacionaisDO - 10.5753/sbseg.2023.233093, 2023)
This short paper proposes two implementation techniques that may speed up the key generation routine of FALCON, a lattice-based digital signature scheme recently standardized by NIST. The first is a change in the set of primes used for splitting polynomials in NTT+RNS representation: by mixing 31-bit and 63-bit primes, we postulate that operations may be computed concurrently using both the scalar ALU (for 64-bit) and SIMD ALU (computing four 32-bit operations in a single 128-bit register). The second uses arbitrary-precision floating-point operations to compute the polynomial reduction step, which we prototype and benchmark on both Apple M1 SoC and Cortex-A72, improving on the original implementation for deeper recursion levels.