On Families of Graphs of Large Cycle Indicator, Matrices of Large Order and Key Exchange Protocols With Nonlinear Polynomial Maps of Small Degree

This paper studies the group theoretical protocol of Diffie?CHellman key exchange in the case of symmetrical group ${S_{p^n}}$ and more general Cremona group ${C(\mathbb K^n)}$ of polynomial automorphisms of free module ${\mathbb K^n}$ over arbitrary commutative ring ${\mathbb K}$ . This algorithm depends very much on the choice of the base ${g_n \in C( \mathbb K^n)}$ . It is important to work with the base ${g_n \in C( \mathbb K^n)}$ , which is a polynomial map of a small degree and a large order such that the degrees of all powers ${g_n^k}$ are also bounded by a small constant. We suggest fast algorithms for generation of a map ${g_n={f_n} \xi_nf_n^{-1}}$ , where ?? _n is an affine transformation (degree is 1) of a large order and f _n is a fixed nonlinear polynomial map in n variables such that ${f_n^{-1}}$ is also a polynomial map and both maps f _n and ${f_n^{-1}}$ are of small degrees. The method is based on properties of infinite families of graphs with a large cycle indicator and families of graphs of a large girth in particular. It guaranties that the order of g _n is tending to infinity as the dimension n tends to infinity. We propose methods of fast generation of special families of cubical maps f _n such that ${f_n^{-1}}$ is also of degree 3 based on properties of families of graphs of a large girth and graphs with a large cycle indicator. At the end we discuss cryptographical applications of maps of the kind ?? f _n ??^?1 and some graph theoretical problems motivated by such applications.