On the key exchange with nonlinear polynomial maps of stable degree
This work addresses cryptographic security for key exchange protocols, offering a novel approach based on algebraic structures, though it appears incremental as it builds on group-theoretic methods.
The paper tackles the problem of secure key exchange by constructing polynomial maps of stable degree to form a group-theoretic Diffie-Hellman algorithm in the Cremona group, where the adversary cannot compute the discrete logarithm using degree analysis. It provides explicit constructions for commutative rings with at least three regular elements and discusses implementation using computer algebra tools.
We say that the sequence $g_n$, $n\ge 3$, $n \rightarrow \infty$ of polynomial transformation bijective maps of free module $K^n$ over commutative ring $K$ is a sequence of stable degree if the order of $g_n$ is growing with $n$ and the degree of each nonidentical polynomial map of kind ${g_n}^k$ is an independent constant $c$. A transformation $b=τ {g_n}^k τ^{-1}$, where $τ$ is affine bijection, $n$ is large and $k$ is relatively small, can be used as a base of group theoretical Diffie-Hellman key exchange algorithm for the Cremona group $C(K^n)$ of all regular automorphisms of $K^n$. The specific feature of this method is that the order of the base may be unknown for the adversary because of the complexity of its computation. The exchange can be implemented by tools of Computer Algebra (symbolic computations). The adversary can not use the degree of righthandside in $b^x=d$ to evaluate unknown $x$ in this form for the discrete logarithm problem. In the paper we introduce the explicit constructions of sequences of elements of stable degree for cases $c=3$ for each commutative ring $K$ containing at least 3 regular elements and discuss the implementation of related key exchange and public key algorithms.