On Quadratic Equations of the q-Regular Tree and Their Applications in Graph Theory and Cryptography

Graphs D(n,q) and their connected components CD(n,q) were defined 30 years ago. We briefly review their applications to Extremal Graph Theory, Spectral Graph Theory, Algebraic Graph Theory, Symmetric Cryptography, and Theory of Low Density Parity Check Codes. We introduce several new algorithms of Noncommutative Cryptography based on these graphs of large girth. In particular we propose a modification of the Diffie–Hellman protocol in terms of the semigroup of walks of even length on the forest obtained as the projective limit of D(n,q) and the homomorphic image of this monoid, acting on the vector space (Fq)n as the transformation group G(n,q) of cubic polynomial transformations. The protocol allows users to compute a collision vector from (Fq)n in time O(n2). The security of these schemes rests on the complexity of the Conjugacy Power Problem for the affine Cremona semigroup of automorphisms of Fq[x1,x2,…,xn]. An inverse protocol of El Gamal type allows one to use this scheme for encryption or the creation of digital signatures. Several obfuscations of these algorithms are given.