On Schubert cells in Grassmanians and new algorithms of multivariate cryptography

V. A. Ustimenko

Trudy Instituta matematiki, Tome 23 (2015) no. 2, pp. 137-148.

Résumé

The partition of projective geometry over the field $F_q$ into Schubert sets allows to convert an incidence graph to symbolic Grassman automaton. Special symbolic computations of these automata produce bijective transformation of the largest Schubert cell. Some of them are chosen as maps which are used in new cryptosystems. The natural analogue of projective geometry over $F_q$ and related Grassman automaton can be defined over a general commutative ring $K$ and used for applications. In case of finite ring these automata allows to define a symmetric encryption algorithm, which uses plainspace $(K)^{k(k+1)}$ and key space formed by special tuple of elements from $K[x_1,x_2,\dots,x_k]^k$ (governing functions). The length of the password tuple can be chosen by users. Every encryption map corresponding to chosen tuple is a multivariate map, its degree is defined by degrees of multivariate governing functions. These degrees can be chosen in a way that the value of corresponding multivariate map given in standard form can be computed in a polynomial time. It will be shown that bijectivity of the last governing function guaranties bijectivity of the transformation of space $(K)^{k(k+1)}$. So this symmetric algorithm can be used for the extention of the bijective polynomial map $h: K^k\to K^k$ to the bijective nonlinear map $E(h): (K)^{k(k+1)}\to (K)^{k(k+1)}$. Transformations of kind $G=T_1E(h)T_2$, where $T_1$ and $T_2$ are affine bijections can be used in cryptography. In the case when all governing functions are linear the transformation $G$ will be quadratic. We consider examples of quadratic cryptosystems $E(h)$ over special fields, where h is an encryption function of Imai Matsumoto algorithm. Finally we suggest multivariate algorithms of Postquantum Cryptography which use hidden discrete logarithm problem and hidden factorisation problems for integers. In case of factorization the last governing function ia chosen as a nonbijective map.

Bibliographie

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

[2] Ustimenko V., “Schubert cells in Lie geometries and key exchange via symbolic computations”, Proceedings of the International Conference “Applications of Computer Algebra”, ACA 2010 (Vlora, 2010), Albanian Math. J., 4, no. 4, 2010, 135–145 | MR | Zbl

[3] Ustimenko V. A., “On the flag geometry of simple group of Lie type and Multivariate Cryptography”, Algebra and Discrete Mathematics, 19:1 (2015), 130–144 | MR | Zbl

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

[5] Ding J., Gower J. E., Schmidt D. S., “Multivariate Public Key Cryptosystems”, Advances in Information Security, 25 (2006)

[6] Ustimenko V. A., “Explicit constructions of extremal graphs and new multivariate cryptosystems”, Proceedings of The Central European Conference (2014, Budapest), Studia Scientiarum Mathematicarum Hungarica, 52, 2015, 185–204 | DOI | MR

[7] Ustimenko V., “On the extremal graph theory for directed graphs and its cryptographical applications”, Advances in Coding Theory and Cryptography, Series on Coding Theory and Cryptology, 3, 2007, 181–200 | DOI | MR

[8] Ustimenko V. A., “On the cryptographical properties of extreme algebraic graphs”, Algebraic Aspects of Digital Communications, Lectures of Advanced NATO Institute, NATO Science for Peace and Security Series D: Information and Communication Security, 24, IOS Press, July 2009 | MR | Zbl

[9] Patarin J., “Cryptoanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88”, Advances in Cryptology, Eurocrypt '96, Springer Verlag, 43–56 | MR

[10] Koblitz N., Algebraic aspects of cryptography, Springer, 1998 | MR | Zbl

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

[12] Patarin J., The Oil i Vinegar digital signatures, Presented at Dagstuhl Workshop on Cryptography, 1997

[13] Kipnis A., Shamir A., “Cryptanalisis of the Oil and Vinegar Signature Scheme”, Advances in Cryptology - Crypto 96, Lecture Notes in Computer Science, 1462, 1996, 257–266 | DOI | MR

[14] Kipnis A., “Unbalanced Oil and Vinegar Signature Scheme — extended version”, Euro-Crypt (1999)

[15] Bulygin S., Petzoldt A., Buchmann J., “Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks”, Progress in Cryptology - INDOCRYPT 2010, Lecture notes in Computer Science, 6498, eds. Guang Gong, Kishan Chand Gupta, 2010, 17–32 | DOI | MR | Zbl

[16] Petzoldt A., Bulygin S., Buchmann J., “Cyclic rainbow — a multivariate signature scheme with a partially cyclic public key”, Progress in Cryptology - INDOCRYPT 2010, Lecture notes in Computer Science, 6498, eds. Guang Gong, Kishan Chand Gupta, 2010, 33–48 | DOI | MR | Zbl

[17] Petzoldt A., Bulygin S., Buchmann J., “Fast verification for improved versions of the uov and rainbow signature schemes”, Post-Quantum Cryptography, Lecture Notes in Computer Science, 7932, ed. Philippe Gaborit, 2014, 188–202 | DOI

[18] Romanczuk-Polubiec U., Ustimenko V., “On two windows multivariate cryptosystem depending on random parameters”, Algebra and Discrete Mathematics, 19:1 (2015), 101–129 | MR | Zbl

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

[20] Brower A., Cohen A., Nuemaier A., Distance regular graphs, Springer, Berlin, 1989 | MR

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

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

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

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

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

[26] Cossidente A., Resmene M. J., “Remarks on Singer Cyclic Groups and their normalisers”, Designs, Codes and Cryptography, 32 (2004), 97–102 | DOI | MR | Zbl