A NEW APPROACH TO THE DEVELOPMENT OF MULTIDIMENSIONAL CRYPTOGRAPHY ALGORITHMS
Authors:   Saint Petersburg Electrotechnical University “LETI”, Moldovyan Dmitriy , Moldovyan Nikolay ,   St. Petersburg Federal Research Center of the Russian Academy of Sciences, Moldovyan Nikolay ,   St. Petersburg Federal Research Center of the Russian Academy of Sciences
Published: April 2023

Purpose of work is the reduction in the size of the public key of public-key algorithms of multivariate cryptography based on the computational difficulty of solving systems of many power equations with many unknowns. Research method is use of non-linear mappings defined as exponentiation operations in finite extended fields GF(qm) represented in the form of finite algebras. The latter makes it possible to perform the exponentiation operation in the field GF(qm) by calculating the values of power polynomials over the field GF(q), which define a hardly reversible nonlinear mapping of the vector space over GF(q) with a secret trapdoor. Due to the use of nonlinear mappings of this type, it is possible to specify a public key in multidimensional cryptography algorithms in the form of a nonlinear mapping implemented as a calculation of the values of a set of polynomials of the third and sixth degree. At the same time, due to the use of masking linear mappings that do not lead to an increase in the number of terms in polynomials, the size of the public key is reduced in comparison with known analogue algorithms, in which the public key is represented by a set of polynomials of the second and third degrees. The proposed approach potentially expands the areas of practical application of post-quantum algorithms for public encryption and electronic digital signature, related to multidimensional cryptography, by significantly reducing the size of the public key. Results of the study are the main provisions of a new approach to the development of algorithms of multidimensional cryptography are formulated. Hardly invertible nonlinear mappings with a secret trapdoor are proposed in the form of exponentiation operations to the second and third powers in finite extended fields GF(qm), represented in a form of a finite algebra. A rationale is given for specifying a public key in a form that includes a superposition of two non-linear mappings performed as a calculation of a set of second and third degree polynomials defined over GF(q). Techniques for implementing mappings of this type are proposed and specific options for specifying the fields GF(qm) in the form of finite algebras are considered. An estimate of the size of the public key in the algorithms developed within the framework of the new approach is made. at a given security level.. Practical relevance includes the developed main provisions of a new method for constructing multidimensional cryptography algorithms based on the computational difficulty of solving systems of many power equations with many unknowns and related to post-quantum cryptoschemes. The proposed approach expands the areas of practical application of post-quantum algorithms of this type by significantly reducing the size of the public key, which provides the prerequisites for improving performance and reducing technical resources for their implementation