On Graphs Defined by Equations and Cubic Multivariate Public Keys

Graphs of large girth of algebraic nature known in the Theory of Extremal Graphs are known as efficient instruments for the design of construction of Low Density Parity Check Codes for the protection of communications, for the design of stream ciphers for Data protection and key exchange protocols in the terms of Noncommutative Cryptography and new cryptosystems in this field. In our paper we use these graph for the constructions of new public keys of Multivariate Cryptography. In particular we present cubic multivariate maps corresponding to graphs \(A(n,F_{2^s})\) and \(D(n,F_{2^s}), \ s\ge 16\) in the case of finite field \(F_{2^s}\) for the sufficiently large parameter s. The inverse map for the encryption transformation has large polynomial degree \(\ge 2^{s-1}\) . Computer experiments are presented for the case \(s=32\) .