On multivariate public keys based on a pair of transformations with density gap

1Ustimenko, VA
1Institute of Telecommunications and Global Information Space of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2018, 9:21-27
Section: Information Science and Cybernetics
Language: English

We propose an algorithm of generation of the stable families of bijective polynomial maps f(n) of the n-dimensional affine space over a commutative ring K together with their inverse transformations. All maps are given in a standard basis, in which their degrees and densities are calculated. The method allows us to generate transformations f(n) of the linear density with degree given by the prescribed linear function d(n) and with exponential density for f(n)–1. In the case of K = Fq, we can select f(n) of the exponential order. The scheme of generation of public keys of multivariate cryptography of the form g(n) = T1f(n)T2, where T1 is a monomial linear transformation of Kn, and the degree of T2 is equal to 1, is proposed. The estimates of complexity show that the time of execution of the encryption rule coincides with the time of computation of the value of a quadratic multivariate map. The decryption procedure based on the knowledge of a generation algorithm is even faster. The security rests on the idea of the insufficiency of adversary's computational resources to restore the inverse map with exponential density and unbounded degree and on the absence of the known general polynomial algorithms to solve this task.

Keywords: algebraic graphs, estimates of comp lexity, multivariate cryptography, post-quantum cryptography, public keys
  1. Machi, A. (2012). Algebra for symbolic computation. Springer.
  2. Ding, J., Gower, J. E. & Schmidt, D. S. (2006). Multivariate public key cryptosystems. Advances in Information Security, Vol. 25. Springer.
  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 the families of stable multivariate transformations of large order and their cryptographical applications. Tatra Mt. Math. Publ., 70, pp. 107-117.
  5. Ustimenko, V. A. (2015). On Schubert cells in Grassmannians and new algorithm of multivariate cryptography. Tr. Inst. Mat., 23, No. 2, pp. 137-148.
  6. Ustimenko, V. A. (1998). On the varieties of parabolic subgroups, their generalizations and combinatorial applications. Acta Appl. Math., 52, pp. 223-238.
  7. Ustimenko, V. (2017). On desynchronised multivariate El Gamal algorithm. Retrieved from https://eprint.iacr.org/2017/712.pdf
  8. Cossidente, A. & de Ressmine, M. J. (2004). Remarks on Singer cycle groups and their normalizers. Designs Codes Cryptogr., 32, pp. 97-102.
  9. Kantor, W. (1982). Linear groups containing a Singer cycle. J. Algebra, 62, pp. 232-234.
  10. Ustimenko, V. (2015). On algebraic graph theory and non–bijective maps in cryptography. Algebra Discrete Math., 20, No. 1, pp. 152-170.
  11. Ustimenko, V. (2017). On new multivariate cryptosystems with nonlinearity gap. Algebra Discrete Math., 23, No. 2, pp. 331-348.
  12. Ustimenko, V. (2017). On new multivariate cryptosystems based on hidden Eulerian equations. Dopov. Nac. akad. nauk Ukr., No. 5, pp. 17-24. doi: https://doi.org/10.15407/dopovidi2017.05.017
  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. 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 Metaheuristics (pp. 257-285). Berlin: Springer.
  15. Polak, M., Romańczuk, U., Ustimenko, V. & Wróblewska, A. (2013). On the applications of extremal graph theory to coding theory and cryptography. Electron. Notes Discrete Math., 43, pp. 329-342.