Optimization of polynomial multiplication algorithm for NTRU-like algorithms

Abstract

The problem of cryptographic protection against classical and potential crypto-analytic attacks with the use of quantum computer and quantum mathematics has become an urgent issue. Understanding this problem, technologically advanced states are making significant efforts to analyze the cryptographic stability of existing standards for cryptographic information security in the post-quantum period and are seeking to establish post-quantum standards for asymmetric cryptography. A practical solution to this problem is being pursued globally during the NIST USA international competition. As previous studies have shown, algebraic lattices are now considered to be a reliable mathematical basis on which post-quantum asymmetric encryptions and PIK can be created. NTRU-like algorithms are a class of crypto-transformations algorithms that satisfy basically the requirements of post-quantum cryptography. Algorithms for key generation direct and reverse cryptographic transformations are the basic components in NTRU-like algorithms for asymmetric crypto-transformations. A number of authors today focus on optimizing polynomial multiplication for these algorithms by the criterion of time complexity. A special requirement for them is the independence of the time of the multiplication operation from the polynomials themselves, which makes it impossible to attack by side channels. This paper proposes the use of the NTT and Toom-Kuk algorithms. It proposes a new solution to this problematic issue, which made it possible to obtain an acceleration of almost 2 times while providing a constant polynomial multiplication time. The objective of this article is to optimize the polynomial multiplication algorithm by the time complexity criterion, used to generate keys and perform direct and reverse cryptographic transformations of asymmetric encryptions and PIK on algebraic lattices.