### Schubert cells in Lie geometries and key exchange via symbolic computations

*Vasyl Alex Ustimenko*

#### Abstract

We propose some cryptographical algorithms 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}={F_q}^N$ 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 consider the induced subgraph of adjacency graph

obtained by deleting all vertices outside of largest Schubert cell

and corresponding automaton (Schubert automaton). We consider the following symbolic implementation of Tits and Schubert automata. The symbolic initial state is a string of variables $x_{\alpha}$, where roots $\alpha$ are listed according Bruhat order, choice of label will be governed by linear expression in variables $x_{\alpha}$, where $\alpha$ is a simple root.

Conjugations of such nonlinear map with element of affine group acting on ${\rm F_q}^N$can be used in Diffie-Hellman key exchange algorithm based on the complexity of group theoretical discrete logarithm problem in case of Cremona group of this variety. We evaluate the degree of these polynomial maps from above and the maximal order of this transformation from below.

For simplicity we assume that $G$ is a simple Lie group of normal type but the algorithm can be easily generalised on wide classes of Tits geometries. In a spirit of algebraic geometry we generalise slightly the algorithm by change of linear governing functions for rational linear maps.

$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}={F_q}^N$ 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 consider the induced subgraph of adjacency graph

obtained by deleting all vertices outside of largest Schubert cell

and corresponding automaton (Schubert automaton). We consider the following symbolic implementation of Tits and Schubert automata. The symbolic initial state is a string of variables $x_{\alpha}$, where roots $\alpha$ are listed according Bruhat order, choice of label will be governed by linear expression in variables $x_{\alpha}$, where $\alpha$ is a simple root.

Conjugations of such nonlinear map with element of affine group acting on ${\rm F_q}^N$can be used in Diffie-Hellman key exchange algorithm based on the complexity of group theoretical discrete logarithm problem in case of Cremona group of this variety. We evaluate the degree of these polynomial maps from above and the maximal order of this transformation from below.

For simplicity we assume that $G$ is a simple Lie group of normal type but the algorithm can be easily generalised on wide classes of Tits geometries. In a spirit of algebraic geometry we generalise slightly the algorithm by change of linear governing functions for rational linear maps.

Full Text: PDF

This work is licensed under a Creative Commons Attribution 3.0 License.