Schubert cells in Lie geometries and key exchange via symbolic computations

We propose some cryptographical algorithms based on nite BN-pair G dened over the elds Fq. We convert the adjacency graph for maxi-mal ags of the geometry of group G into a nite Tits automaton by specialcolouring of arrows and treat the largest Schubert cell Sch = FqN on thisvariety as a totality of possible initial states and a totality of accepting statesat a time. The computation (encryption map) corresponds to some walk inthe graph with the starting and ending points in Sch. To make algorithmsfast we will use the embedding of geometry for G into Borel subalgebra ofcorresponding Lie algebra. We consider the induced subgraph of adjacencygraph obtained by deleting all vertices outside of largest Schubert cell andcorresponding automaton (Schubert automaton). We consider the followingsymbolic implementation of Tits and Schubert automata. The symbolic initialstate is a string of variables x, where roots are listed according Bruhatorder, choice of label will be governed by linear expression in variables x,where is a simple root.Conjugations of such nonlinear map with element of ane group actingon FqN can be used in Die-Hellman key exchange algorithm based on thecomplexity of group theoretical discrete logarithm problem in case of Cremonagroup of this variety. We evaluate the degree of these polynomial maps fromabove and the maximal order of this transformation from below. For simplicitywe assume that G is a simple Lie group of normal type but the algorithm canbe easily generalised on wide classes of Tits geometries. In a spirit of algebraicgeometry we generalise slightly the algorithm by change of linear governingfunctions for rational linear maps.