On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism

TitleOn new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism
Publication TypeJournal Article
Year of Publication2018
AuthorsUstimenko, VA
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
SectionInformation Science and Cybernetics
Date Published10/2018

Multivariate cryptosystems are divided into public rules, for which tools of encryption are open for users and systems of the El Gamal type, for which the encryption function is not given in public, and, for its generation, the opponent has to solve a discrete logarithm problem in the affine Cremona group. Infinite families of transformations of a free module Kn over a finite commutative ring K such that the degrees of their members are not growing with iteration are called stable families of transformations. Such families are needed for practical implementations of multivariate cryptosystems of the El Gamal type. New explicit constructions of such families and families of stable groups and semigroups of transformations of free modules are given. New methods of creation of cryptosystems, which use stable transformation groups and semigroups and homomorphisms between them, are suggested. The security of these schemes is based on a complexity of the decomposition problem for an element of the affine Cremona semigroup into a product of given generators. Proposed schemes can be used for the exchange of messages in a form of elements of a free module and for a secure delivery of multivariate maps, which could be encryption tools and instruments for digital signatures.

Keywordsalgebraic graphs, cryptosystems, key exchange protocols, multivariate cryptography, problem of decomposition of a nonlinear multivariate map into given generators, stable transformation groups and semigroups, tame homomorphisms, wild and tame families of transformations
  1. Ding, J., Gower, J. E. & Schmidt, D. S. (2006). Multivariate public key cryptosystems. Advances in In formation Security, Vol. 25, Springer.
  2. Koblitz, N. (1998). Algebraic aspects of cryptography. Springer. doi: https://doi.org/10.1007/978-3-662-03642-6
  3. Goubin, L., Patarin, J. & Yang, Bo-Yin. (2011). Multivariate cryptography. In Encyclopedia of cryptography and security. 2nd ed. (pp. 824-828). Springer.
  4. Ustimenko, V. (2017). On desynchronised multivariate El Gamal algorithm. Retrieved from https://eprint.iacr.org./2017/712.pdf.
  5. Ustimenko, V. (2017). On the families of stable multivariate transformations of large order and their cryptographical applications. Tatra Mt. Math. Publ., 70, pp. 107-117. doi: https://doi.org/10.1515/tmmp-2017-0021
  6. Ustimenko, V. & Romańczuk, U. (2013). On dynamical systems of large girth or cycle indicator and their applications to multivariate cryptography. In artificial intelligence, evolutionary computing and me taheuristics (pp. 257-285). Berlin: Springer.
  7. Ustimenko, V. A. (2013). On the extremal graph theory and symbolic computations. Dopov. Nac. akad. nauk Ukr. No. 2, pp. 42-49 (in Russian).
  8. Ustimenko, V. A. (2005). Maximality of affine group, and hidden graph cryptosystem. Algebra Discrete Math., No. 1, pp. 133-150.
  9. Ustimenko, V. & Wróblewska, A. (2013). On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree. Annalles UMCS, Informatica, 13, No.1, pp. 63-80. doi: https://doi.org/10.2478/v10065-012-0047-6
  10. Wróblewska, A. (2008). On some properties of graph based public keys. Albanian J. Math., 2, No. 3, pp. 229-234.
  11. Klisowski, M. & Ustimenko, V. (2015). Graph based cubical multivariate maps and their cryptographical applications. In Advances on superelliptic curves and their applications (pp. 305-327). Amsterdam etc.: IOS Press.
  12. Wróblewska, A. & Ustimenko, V. (2014). On new examples of families of multivariate stable maps and their cryptographical applications. Annales UMCS, Informatica. 14, No. 1, pp. 19-36. doi: https://doi.org/10.2478/umcsinfo-2014-0004
  13. Romańczuk-Polubiec, U. & Ustimenko, V. (2015). On two windows multivariate cryptosystem depending on random parameters. Algebra Discrete Math., 19, No. 1, pp. 101-129.
  14. Romańczuk-Polubiec, U. & Ustimenko, V. A. (2015). On new key exchange multivariate protocols based on pseudorandom walks on incidence structures. Dopov. Nac. akad. nauk Ukr., No. 1, pp. 41-49. doi: https://doi.org/10.15407/dopovidi2015.01.041
  15. Ustimenko, V. A. (2015). Explicit constructions of extremal graphs and new multivariate cryptosystems. Stud. Sci. Math. Hung. Spec. iss. Proceedings of The Central European Conference, 2014, Budapest. 52, No. 2, pp. 185-204. doi: https://doi.org/10.1556/012.2015.52.2.1312