Jordan–Gauss Graphs and Twisted Diffie–Hellman Multivariate Protocols with Stable Generators of Prescribed Degree and Density

A well-known family of algebraic graphs of large girth, \(D(n,q)\), has previously been used to implement twisted Diffie--Hellman protocols with graph-based stable cubic generators from the affine Cremona semigroup \(End(F_q[x_1,x_2,…,x_n])\). This approach enables Alice and Bob to compute a shared collision tuple in \((F_q)n^3\) in \(O(n^5)\) time instead of explicitly constructing the corresponding collision transformation. In this paper, we develop new implementations of twisted Diffie--Hellman protocols, as well as their inverse variants, using families of Jordan--Gauss graphs and stable generators of the corresponding affine Cremona semigroups. We show that Double Schubert graphs \(DS(k,K)\), defined over a finite commutative ring \(K\), can be used to construct stable generators of \(End(K[x_1,x_2,…,xₖ₍ₖ₊₁₎])\) with prescribed degree \(d\) and prescribed density \(O(n^β)\), where \(n=k(k+1)\). Sparse elements of \(AGL_n(K)\) are then used to conjugate these graph-based stable transformations, allowing the communicating parties to efficiently derive shared collision tuples in \(Kn^d\). We further show that other \(K\)-analogues of Jordan--Gauss subgraphs of projective geometry can be used in place of Double Schubert graphs to implement both the twisted Diffie--Hellman protocol and its inverse ElGamal-type variant. In addition, we investigate protocols involving two generators, one being a nonlinear graph-based transformation and the other a sparse element of \(AGL_n(K)\). Finally, we present results of computer simulations for multivariate protocols whose stable generators are constructed using the large-girth graph \(A(n,q)\).