On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems

Abstract

Results of implementation of several multivariate public keys of linear degree of size O(n) and polynomial density defined over commutative ring K with the nontrivial multiplicative group K*. are presented. The space of plaintexts of these cryptosystems is (K*)ⁿ and space of ciphertexts is Kⁿ. The encryption map is the restriction on (K*)ⁿ of polynomial transformation of the space Kⁿ which is the composition of special Eulerian trams-formation with cubical map of Multivariate Cryptography of kind T₁QT₂, where T₁ and T₂ are bijective affine trans-formations and Q is a nonlinear map defined via walk on algebraic bipartite graph points and lines of which form the space Kⁿ.
This scheme is implemented for the cases K=F_q and K=Z_q, q=2³². The knowledge of private key allows to decipher of the message from public user in time O(n²). The cryptosystems are generalisations of algorithms suggested 9 years ago cryptanalysis of which are unknown. The problem of breaking the cryptosystem is equivalent to solving of system of nonlinear equations in n variables of degree cn, de c>0. The computer packages for the investigation of such systems are undeveloped.