ACCELERATING MODULAR REDUCTION FOR FALCON SIGNATURE SCHEME

Purpose of the study: precomputation reducing and execution time speeding up of Falcon signature scheme by implementing a modified version of the K-RED algorithm. Methods of research: resource intensity evaluation of modular reduction algorithms, mathematical modeling of modular reduction algorithms, testing of modular reduction algorithms as part of the post-quantum signature scheme. Results: multiplication of polynomials in the polynomial quotient ring is organized in Falcon in such a way that its execution requires precomputed lookup tables that store so-called twiddle factors. Modular reduction algorithms based on representing numbers in a special form require additional scaling of these twiddle factors by a given factor. Based on the size of the lookup tables used in Falcon signature scheme, a comparative analysis of the resource intensity of the Montgomery and K-RED algorithms has been conducted. Due to the fact that the memory consumption of the K-RED algorithm is almost twice that of the Montgomery algorithm, the K2-RED algorithm which allows for faster modular reduction with a smaller volume of scaled twiddle factors has been considered. A theorem that generalizes the K-RED algorithm to the case where the reduction modulus is not a Proth number has been proven. Additionally, requirements for the size of modified K-RED factors have been established, based on which representations of prime moduli in the NTRU equation solution have been selected. The modified K-RED algorithm has been implemented in C language and integrated into the Falcon reference implementation. Testing of modified Falcon has been conducted, resulting in a reduction in the execution time of key generation and signature verification procedures.