On the Families of Stable Multivariate Transformations of Large Order and Their Cryptographical Applications

Ustimenko, Vasyl

doi:10.1515/tmmp-2017-0021

Abstract

Families of stable cyclic groups of nonlinear polynomial transformations of affine spaces Kn over general commutative ring K of with n increasing order can be used in the key exchange protocols and El Gamal multivariate cryptosystems related to them. We suggest to use high degree of noncommutativity of affine Cremona group and modify multivariate El Gamal algorithm via conjugations of two polynomials of kind g^k and g⁻¹ given by key holder (Alice) or giving them as elements of different transformation groups. Recent results on the existence of families of stable transformations of prescribed degree and density and exponential order over finite fields can be used for the implementation of schemes as above with feasible computational complexity.

References

[1] DING, J.-GOWER, V.-SCHMIDT, D. S.: Multivariate Public Key Cryptosystems. In: Adv. Inform. Sec. Vol. 25, Springer-Verlag, New York, 2006.
Search in Google Scholar Back to article
[2] COSSIDENTE, A.-DE RESMINI, M. J.: Remarks on Singer cyclic groups and their normalizers, Des. Codes Cryptogr. 32 (2004), no. 1-3, 97-102, 10.1023/B:DESI.0000029214.50635.17
Search in Google Scholar Back to article
[3] KANTOR, W.: Linear groups containing a Singer cycle, J. Algebra 62 (1980), no. 1, 232-234.10.1016/0021-8693(80)90214-8
Search in Google Scholar Back to article
[4] BABAI, L.: Graph isomorphism in quasipolinomial time, arXive: 1512 03547v1 [cs. DS], December 11, 2015.
Search in Google Scholar Back to article
[5] KIPNIS, A.-SHAMIR, A.: Cryptanalisis of the Oil and Vinegar Signature Scheme, Adv. in Cryptology-Crypto ’96, Lect. Notes in Comput. Sci. Vol. 1462, 1996, pp. 257-266.10.1007/BFb0055733
Search in Google Scholar Back to article
[6] PATARIN, J.-GOUBIN, L.: Trapdoor one-way permutations and multivariate polynominals, ICICS 1997, pp. 356-368.10.1007/BFb0028491
Search in Google Scholar Back to article
[7] Asymmetric cryptography with S-Boxes, ICICS 1997, pp. 369-380.
Search in Google Scholar Back to article
[8] PATARIN, J.: Asymmetric cryptography with a hidden monomial, and a candidate algorithm for 64 bits asymmetric signatures. In: Advances in cryptologyCRYPTO’96, Santa Barbara, CA), Lect. Notes in Comput. Sci. Vol. 1109, Springer-Verlag, Berlin, 1996, pp. 45-60. 10.1007/3-540-68697-5_4
Search in Google Scholar Back to article
[9] GOUBIN, L.-PATARIN, J.-YANG, B.-Y.: Multivariate Cryptography. Encyclopedia of Cryptography and Security (2nd ed.), Springer-Verlag Berlin 2011, pp. 824-828.10.1007/978-1-4419-5906-5_421
Search in Google Scholar Back to article
[10] PORRAS, J.-BAENA, J.-DING, J.: New candidates for multivariate trapdoor functions, Rev. Colombiana Mat. 49 (2015), no. 1, 57-76.10.15446/recolma.v49n1.54163
Search in Google Scholar Back to article
[11] USTIMENKO, V. A.: Explicit constructions of extremal graphs and new multivariate cryptosystems, In: Proceedings of The Central European Conference, 2014, Budapest”, Studia Sci. Math. Hungar. 52 (2015), 185-204.10.1556/012.2015.52.2.1312
Search in Google Scholar Back to article
[12] On multivariate cryptosystems based on computable maps with invertible decompositions, Ann. Univ. Mariae Curie-Sk_lodowska Sect. AI-Inform. 14 (2014), 7-18.10.2478/umcsinfo-2014-0001
Search in Google Scholar Back to article
[13] On Shubert cells in grassmanians and new algorithm of multivariatecryptography, Tr. Inst. Mat. 23 (2015), no. 2, 137-148
Search in Google Scholar Back to article
[14] On Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Zap. Nauchn. Semin. POMI 326, (2005), 214-234; translated in J. Math. Sci., 140 (2007), no. 3, 461-471.
Search in Google Scholar Back to article
[15] USTIMENKO, V.-WROBLEWSKA, A.: On the key exchange with nonlinear polynomial maps of stable degree, Ann. Univ. Mariae Curie-Skodowska Sect. AI-Inform. 13 (2013), no. 1, 63-80.10.2478/v10065-012-0047-6
Search in Google Scholar Back to article
[16] WROBLEWSKA, A.: On some properties of graph based public keys, Albanian J. Math. 2 (2008), no. 3, 229-234.
Search in Google Scholar Back to article
[17] USTIMENKO, V.: Coordinatisation of trees and their quotients. In: the ”Voronoj’s Impact on Modern Science”, Vol 2, 1998, Kiev, Institute of Mathematics pp. 125-152.
Search in Google Scholar Back to article
[18] LAZEBNIK, F.-USTIMENKO, V. A.: Some algebraic constractions of dense graphs of large girth and of large size. In: Expanding graphs, Princeton, NJ, 1992, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 10, 1993, Amer. Math. Soc., Providence, RI, pp. 75-93.10.1090/dimacs/010/07
Search in Google Scholar Back to article
[19] LAZEBNIK, F.-USTIMENKO, V. A. -WOLDAR, A. J.: New series of dense graphs of high girth, Bull. Amer. Math. Soc. (N.S.) 32 (1995), no. 1, 73-79.10.1090/S0273-0979-1995-00569-0
Search in Google Scholar Back to article
[20] USTIMENKO, V.- ROMANCZUK, U.: On dynamical systems of large girth or cycle indicator and their applications to multivariate cryptography. In: Artificial Intelligence, Evolutionary Computing and Metaheuristics, In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Vol. 427, Springer-Verlag, 2013, pp. 257-285.10.1007/978-3-642-29694-9_10
Search in Google Scholar Back to article
[21] USTIMENKO, V.-WROBLEWSKA, A.: Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography, Ann. Univ. Mariae Curie-Skodowska Sect. AI-Inform. 12 (2012), no. 3, 65-74.10.2478/v10065-012-0030-2
Search in Google Scholar Back to article
[22] KLISOWSKI, M.: Zwi¸eszenie Bezpiecze´nstwa Kryptograficznych Algorytm´owielu Zmiennych Bazuj¸acych na Algebraicznej Teorii Graf´ow. PhD Thesis, Cz¸estochowa, 2014.
Search in Google Scholar Back to article
[23] KLISOWSKI, M.-USTIMENKO, V.: Graph based cubical multivariate maps and their cryptographical applications. In: Advances on Superelliptic curves and their Applications, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., Vol. 41, IOS, Amsterdam, 2015 pp. 305-327.
Search in Google Scholar Back to article
[24] WROBLEWSKA, A.-USTIMENKO, V.: On new examples of families of multivariate stable maps and their cryptographical applications, Ann. Univ. Mariae Curie-Sk_lodowska Sect. AI-Inform. 14 (2014), no. 1, 19-35.10.2478/umcsinfo-2014-0004
Search in Google Scholar Back to article
[25] , USTIMENKO, V.- WOLDAR, A.: A geometric approach to orbital recognition in Chevalley-type coherent configurations and association schemes, Australas. J. Combin. 67 (2017), no. 2, 166-202.
Search in Google Scholar Back to article

On the Families of Stable Multivariate Transformations of Large Order and Their Cryptographical Applications

Abstract

Paradigm

My account