On new multivariate cryptosystems based on hidden Eulerian equations

1Ustimenko, VA
1Institute of Telecommunications and Global Information Space of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2017, 5:17-24
Section: Information Science and Cybernetics
Language: English
We propose new multivariate cryptosystems over an n-dimensional free module over the arithmetical ring Zm based on the idea of hidden discrete logarithm for ${Z_{m}}^{*}$. These cryptosystems are based on the hidden Eulerian equations. If m is a "sufficiently large" product of at least two large primes, then the solution of the equation is hard without knowledge of the decomposition of m. In the Postquantum Era, one can solve the factorization problem for m and the discrete logarithm problem for ${Z_{m}}^{*}$. However, it does not lead to the straightforward break of such cryptosystem, because of the parameter α is unknown. Some examples of such cryptosystems were already proposed. We define their modifications and generalizations based on the idea of Eulerian transformations, which allow us to use asymmetric algorithms based on families of nonlinear multiplicatively injective maps with prescribed polynomial density and degree bounded by constant.
Keywords: algebraic graphs, complexity estimates, hidden discrete logarithm problem, hidden Eulerian equations, multivariate cryptography, postquantum cryptography, public keys
  1. Ding, J., Gower, J. E. & Schmidt, D. S. (2006). Multivariate Public Key Cryptosystems, Advances in In formation Security. Vol. 25. Berlin: Springer.
  2. Goubin, L., Patarin, J. & Yang, Bo-Yin (2011). Multivariate Cryptography. Encyclopedia of Cryptography and Security. Berlin: Springer, pp. 824-828.
  3. Porras, J., Baena, J.B. & Ding, J. (2015). New Candidates for Multivariate Trapdoor Functions. Rev. Colomb. Mat., 49, No. 1, pp. 57-76. https://doi.org/10.15446/recolma.v49n1.54163
  4. Ustimenko, V. (2015). Explicit constructions of extremal graphs and new multivariate cryptosystems. Stud. Sci. Math. Hung., 52, Iss. 2, pp. 185-204. https://doi.org/10.1556/012.2015.52.2.1312
  5. Ustimenko, V. (2014). On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition. Annales of UMCS, Informatica, 14, No. 1, pp. 7-18. https://doi.org/10.2478/umcsinfo-2014-0001
  6. Patarin, J. (1997). The Oil and Vinegar digital signatures, Dagstuhl Workshop on Cryptography. Wadern.
  7. Kipnis, A. & Shamir, A. (1998). Cryptanalysis of the Oil and Vinegar Signature Scheme. Advances in Cryptology-Crypto 98. Lecture Notes in Computer Science. Vol. 1462. Berlin: Springer, pp. 257-266. https://doi.org/10.1007/bfb0055733
  8. Bulygin, S., Petzoldt, A. & Buchmann, J. (2010). G. Gong, K.C. Gupta (Ed.). Progress in Cryptology — INDOCRYPT. Lecture notes in Computer Science. Vol. 6498. Berlin: Springer, pp. 17-32.
  9. 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.
  10. Ustimenko, V. A. (2015). On Schubert cells in Grassmanians and new algorithms of multivariate cryptography. Tr. Inst. Mat., Minsk, 23, No. 2, pp. 137-148.
  11. Ustimenko, V. (2015). On algebraic graph theory and non-bijective multivariate maps in cryptography. Al geb ra Discrete Math., 20, No. 1, pp. 152-170.
  12. Ustimenko, V. & Wroblewska, A. (2011). Performance of algebraic graphs based stream-ciphers using large finite fields. Annales of UMCS, Informatica, 11, No. 2, pp. 81-93.
  13. Ustimenko, V. & Romanczuk, U. (2013). On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography. Artif. Intell., Evol. Comput. and Metaheuristics, Studies in Computational Intelligence. Vol. 427. Berlin: Springer, pp. 231-256. https://doi.org/10.1007/978-3-642-29694-9_10
  14. Wroblewska, A. (2008). On some properties of graph based public keys. Albanian J. Math., 2, No. 3, pp. 229-234.
  15. Ustimenko, V. A. (2005). Maximality of affine group, and hidden graph cryptosystem. Algebra Discrete Math., No. 1, pp. 133-150.