On new multivariate cryptosystems based on hidden Eulerian equations
DOI:
https://doi.org/10.15407/dopovidi2017.05.017Keywords:
algebraic graphs, complexity estimates, hidden discrete logarithm problem, hidden Eulerian equations, multivariate cryptography, postquantum cryptography, public keysAbstract
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 Zm∗. 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 Zm∗. 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.
Downloads
References
Ding, J., Gower, J. E. & Schmidt, D. S. (2006). Multivariate Public Key Cryptosystems, Advances in In formation Security. Vol. 25. Berlin: Springer.
Goubin, L., Patarin, J. & Yang, Bo-Yin (2011). Multivariate Cryptography. Encyclopedia of Cryptography and Security. Berlin: Springer, pp. 824-828.
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
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
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
Patarin, J. (1997). The Oil and Vinegar digital signatures, Dagstuhl Workshop on Cryptography. Wadern.
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
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.
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.
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.
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.
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.
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
Wroblewska, A. (2008). On some properties of graph based public keys. Albanian J. Math., 2, No. 3, pp. 229-234.
Ustimenko, V. A. (2005). Maximality of affine group, and hidden graph cryptosystem. Algebra Discrete Math., No. 1, pp. 133-150.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
