Algebraic Constructions of Extremal Graph Theory were efficiently used for the construction of Low Density Parity Check Codes for satellite communication, constructions of stream ciphers and Postquantum Protocols of Noncommutative cryptography and corresponding El Gamal type cryptosystems.We shortly observe some results in these applications and present idea of the usage of algebraic graphs for the development of Multivariate Public Keys (MPK).Some MPK schemes are presented at theoretical level, implementation of one of them is discussed.Extended version of this article is available online at [31].

We introduce large groups of quadratic transformations of a vector space over the finite fields defined via symbolic computations with the usage of algebraic constructions of Extremal Graph Theory.They can serve as platforms for the protocols of Noncommutative Cryptography with security based on the complexity of word decomposition problem in noncommutative polynomial transformation group.The modifications of these symbolic computations in the case of large fields of characteristic two allow us to define quadratic bijective multivariate public keys such that the inverses of public maps has a large polynomial degree.Another family of public keys is defined over arbitrary commutative ring with unity.We suggest the usage of constructed protocols for the private delivery of quadratic encryption maps instead of the public usage of these transformations, i.e. the idea of temporal multivariate rules with their periodical change. I. ON POST QUANTUM, MULTIVARIATE AND NONCOMMUTATIVE CRYPTOGRAPHYP OST-Quantum Cryptography (PQC) is an answer to a threat coming from a full-scale quantum computer able to execute Shor's algorithm.With this algorithm implemented on a quantum computer, currently used public key schemes, such as RSA and elliptic curve cryptosystems, are no longer secure.PQC is subdivided into Coding based Cryptography, Multivariate Cryptography, Noncommutative Cryptography, Hash based Cryptography, Isogeny based Cryptography and Lattice based Cryptography.Each of these six areas is based on the complexity of certain NP-hard problem.Noteworthy that fundamental assumption of cryptography that there are no polynomial-time algorithms for solving any NP-hard problem remains valid.So all six directions are well justified theoretically.The tender of US National Institute of Standardisation Technology (NIST, 2017) is dedicated to the standardisation process of possible real life Post-Qantum Public keys.Already selected in July of 2022 four cryptosystems are developed via methods of Lattice based Cryptography.This fact motivates researchers from other four core areas of Post Quantum Cryptography to continue design of new cryptographical primitives.Noteworthy that during the NIST project an interesting results on cryptanalysis of Unbalanced Rainbow Oil and Vinegar digital signatures schemes were found (see [1], [2], [3]).

The main purpose of this paper is to introduce stream ciphers with the nonbijective encryption function of multivariate nature constructed in terms of algebraic graph theory. More precisely, we describe the two main symmetric algorithms for creation of multivariate encryption transformations based on three families of bipartite graphs with partition sets isomorphic to Kn , where K is selected as the finite commutative ring. The plainspace of the algorithm is Ω={x∣∑xi∈K⁎, x∈Kn}⊂Kn, Ω≅K⁎×Kn-1. The second algorithm is a generalization of the first one with using the jump operator, where generalized encryption map has an essentially higher degree in comparison with the previous version. Moreover, the degree of this generalized map is not bounded by some constant. This property guarantees resistance of the cipher to linearization attacks.

Certain families of graphs can be used to obtain multivariate polynomials for cryptographic algorithms.In particular, in this paper, we introduce stream ciphers based on nonbijective multivariate maps.The presented symmetric encryption algorithms are based on three families of bipartite graphs with partition sets isomorphic to K n , where K is selected as the finite commutative ring.The plainspace of the algorithm isWe describe the algorithm for the case K = Z2m , m ≥ 2. In fact, we use the relation d * d dec ≡ 1(mod 2 m-1 ), d, d dec ∈ Z

The paper illustrates the concept of the map with logarithmically invertible decomposition.We introduce families of multivariate cryptosystems such that there security level is connected with discrete logarithm problem in Cremona group.The private key of such cryptosystem is a modification of graph based stream ciphers which use stable multivariate maps.Modified version corresponds to a stable map with single disturbance.If the disturbance (or initial condition) allows fast computation then modified version is almost as robust as original one.Methods of modification improve the resistance of such stream ciphers implemented on numerical level to straightforward linearisation attacks.