Geodesic
On the flag geometry of simple group of Lie type and multivariate cryptography
Algebra and discrete mathematics, Tome 19 (2015) no. 1, pp. 130-144.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: multivariate cryptography, flag variety, geometry of simple group of Lie type, symbolic walks.
Mots-clés : Schubert cell 
@article{ADM_2015_19_1_a12,
     author = {Vasyl Ustimenko},
     title = {On the flag geometry of simple group of {Lie} type and multivariate cryptography},
     journal = {Algebra and discrete mathematics},
     pages = {130--144},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a12/}
}
TY  - JOUR
AU  - Vasyl Ustimenko
TI  - On the flag geometry of simple group of Lie type and multivariate cryptography
JO  - Algebra and discrete mathematics
PY  - 2015
SP  - 130
EP  - 144
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a12/
LA  - en
ID  - ADM_2015_19_1_a12
ER  - 
%0 Journal Article
%A Vasyl Ustimenko
%T On the flag geometry of simple group of Lie type and multivariate cryptography
%J Algebra and discrete mathematics
%D 2015
%P 130-144
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a12/
%G en
%F ADM_2015_19_1_a12
Vasyl Ustimenko. On the flag geometry of simple group of Lie type and multivariate cryptography. Algebra and discrete mathematics, Tome 19 (2015) no. 1, pp. 130-144. http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a12/

[1] Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, Advances in Information Security, 25, Springer, 2006, 260 pp. | MR | Zbl

[2] V. Ustimenko, “On Multivariate Cryptosystems Based on Computable Maps with Invertible Decompositions”, Annales of UMCS, Informatica, 14, Special issue "Proceedings of International Conference Cryptography and Security Systems" (2014), 7–18 | DOI | MR

[3] Anton Betten, Mihael Braun, Adalbert Kerber, Axel Kohnert, Alfred Wasserman, Error Correcting Linear Codes Isometry and Applications, Springer, 2006 | MR | Zbl

[4] Andreas Stephan Essenhans, Axel Kohnert, Alfed Wassermann, Constructions of codes for Network Coding, arXiv: 1005.2839[cs]

[5] A. Beultespacher, “Enciphered Geometry, Some Applications of Geometry to Cryptography”, Annals of Discrete Mathematics, 37 (1988), 59–68 | DOI | MR

[6] V. A. Ustimenko, “Graphs with Special Arcs and Cryptography”, Acta Applicandae Mathematicae, 71:2, November (2002), 117–153 | DOI | MR

[7] Ustimenko V., “Schubert cells in Lie geometries and key exchange via symbolic computations” (Vlora), Albanian Journal of Mathematics, 4:4, Special Issue. Proceedings of the International Conference “Applications of Computer Algebra” (2010), 135–145 | MR | Zbl

[8] V. Ustimenko, “On walks of variable length in Schubert incidence systems and multivariate flow ciphers”, Dopovidi of Nathional Acad. Sci. of Ukraine, 2014, no. 3, 55–150

[9] Kluwer, Dordrecht, 1992, 112–119 | MR

[10] V. A. Ustimenko, “Linear interpretation of Chevalley group flag geometries”, Ukraine Math. J., 43:7–8 (1991), 1055–1060 (Russian) | MR | Zbl

[11] V. A. Ustimenko, “On the Varieties of Parabolic Subgroups, their Generalizations and Combinatorial Applications”, Acta Applicandae Mathematicae, 52 (1998), 223–238 | DOI | MR | Zbl

[12] R. W. Carter, Simple Groups of Lie Type, Wiley, New York, 1972 | MR | Zbl

[13] F. Harary, Graph Theory, Addison-Wesley Publishing Co, Reading, MA, 1966 | MR

[14] R. Wilson, Introduction to Graph Theory, Oliver, Edinburg, 1972 | MR | Zbl

[15] E. Moore, “Tactical Memoranda 1–3”, Amer. J. of Math., 18:3 (1896), 264-290 | DOI | MR

[16] A. Brower, A. Cohen, A. Nuemaier, Distance regular graphs, Springe, Berlin, 1989 | MR

[17] N. Bourbaki, Lie Groups and Lie Algebras, Chapters 1–9, Springer, 1998–2008 | MR | Zbl

[18] Handbook on Incidence Geometry, ed. F. Buekenhout, North Holland, Amsterdam, 1995 | MR