Fast polynomial inversion algorithms for the post-quantum cryptography

Several cryptosystems suggested for the post-quantum cryptography candidates, including Falcon, BIKE, and NTRU, are defined in a polynomial ring. They must derive the inverse polynomial of any given polynomial for generating a public key. This process consumes considerable processing time; therefore, reducing the time to derive the inverse polynomial significantly improves many cryptosystems’ performance. In this paper, we primarily suggest two polynomial inversion algorithms, combined-variable-time and combined-constant-time algorithms, based on the modification of the extended Euclidean algorithm. The combined-variable-time algorithm shows how to calculate the inverse polynomial by introducing the combined matrix fast, which is generated by merging several steps of the polynomial operations. In cryptosystems, to defend against side-channel attacks, the implementation with constant running time is essential in preventing information leakage. Thus, we propose the combined-constant-time polynomial inversion algorithm, which expends less running time than the conventional NTRU inversion algorithm. For binary polynomial inversion, the proposed combined-variable-time algorithm is 1.95 times faster than the variable-time algorithm used in the previous NTRU (Silverman Almost inverses and fast NTRU key creation, NTRU Tech Report, no. 014v1, Mar. 15, 1999), and the combined-constant-time algorithms are 1.43 times faster than the reference constant-time algorithms submitted to round 3 of the NIST PQC standardization, respectively. For ternary polynomial inversion, the proposed combined-variable-time and combined-constant-time algorithms are 1.59 and 1.29 times faster than the corresponding reference algorithms.