On Dynamical Systems of Large Girth or Cycle Indicator and Their Applications to Multivariate Cryptography

We are going to observe special algebraic Turing machines designed for different assignments of cryptography such as classical symmetric encryption, public key algorithms, problems of secure key exchange, development of hash functions. The security level of related algorithms is based on the discrete logarithm problem (DLP) in Cremona group of free module over finite commutative ring. In the case of symbolic computations with “sufficiently large number of variables” the order of generator (base of DLP) is impossible to evaluate and we have “hidden discrete logarithm problem”. In the case of subgroups of Cremona group DLP is closely connected with the following classical difficult mathematical problems:

(1) solving the system of nonlinear polynomial equations over finite fields and rings,

(2) problem of finding the inverse map of bijective polynomial multivariable map.

The complexity of Discrete Logarithm Problem depends heavily from the choice of base. Generation of good “pseudorandom” base guarantees the high complexity of (1) and (2) and security of algorithms based on corresponding DLP. We will use methods of theory of special combinatorial time dependent dynamical systems for the construction of special Turing machines for the generation of the nonlinear DLP bases of large (or hidden) order and small degree.