On the flag geometry of simple group of Lie type and multivariate cryptography

We propose some multivariate cryptosystems based on finite $BN$-pair $G$ defined over the fields $F_q$. We convert the adjacency graph for maximal flags of the geometry of group $G$ into a finite Tits automaton by special colouring of arrows and treat the largest Schubert cell ${\rm Sch}$ isomorphic to vector space over $F_q$ on this variety as a totality of possible initial states and a totality of accepting states at a time. The computation (encryption map) corresponds to some walk in the graph with the starting and ending points in ${\rm Sch}$. To make algorithms fast we will use the embedding of geometry for $G$ into Borel subalgebra of corresponding Lie algebra. We also consider the notion of symbolic Tits automata. The symbolic initial state is a string of variables $t_{\alpha}\in F_q$, where roots $\alpha$ are listed according Bruhat's order, choice of label will be governed by special multivariate expressions in variables $t_{\alpha}$, where $\alpha$ is a simple root. Deformations of such nonlinear map by two special elements of affine group acting on the plainspace can produce a computable in polynomial time nonlinear transformation. The information on adjacency graph, list of multivariate governing functions will define invertible decomposition of encryption multivariate function. It forms a private key which allows the owner of a public key to decrypt a ciphertext formed by a public user. We also estimate a polynomial time needed for the generation of a public rule.