Acceleration of modular arithmetic in post-quantum signature schemes

Abstract

Since the discovery of the Shor quantum algorithm, capable of solving factorization and discrete logarithm problems in polynomial time, post-quantum cryptographic algorithms have been actively developed. Although some of the post-quantum algorithms have already been standardized by NIST, an important problem remains their lower efficiency compared to the classical cryptographic algorithms. The purpose of this work is to accelerate operations on polynomials in lattice-based post-quantum signature schemes. The research is carried out by analyzing fast multiplucation and reduction algorithms. The paper considers the Number Theoretic Transform (NTT), K-RED and Montgomery reduction algorithms. The effectiveness of the K-RED algorithm in comparison with the algorithm Montgomery is substantiated. The question of the applicability of the NTT and fast reduction algorithms in the Russian signature scheme «Kryzhovnik» and NIST algorithms Falcon and CRYSTALS-Dilithium is considered. As a result of the research, recommendations for embedding the K-RED algorithm in the reference implementations of the Falcon and CRYSTALS-Dilithium signature schemes are given, as well as the implementation in C of accelerated multiplication using the NTT and the K-RED algorithm. The results of this research can be embedded in the NIST standards FIPS 204 and FIPS 206, as well as adapted for use in other lattice-based signature schemes.

Keywords

• lattices, post-quantum cryptography, reduction algorithm, multiplication of polynomials, quotient ring.