On new multivariate cryptosystems with nonlinearity gap

Vasyl Ustimenko

Algebra and discrete mathematics, Tome 23 (2017) no. 2, pp. 331-348.

Résumé

The pair of families of bijective multivariate maps of kind $F_n$ and ${F_n}^{-1}$ on affine space $K^n$ over finite commutative ring $K$ given in their standard forms has a nonlinearity gap if the degree of $F_n$ is bounded from above by independent constant $d$ and degree of $F^{-1}$ is bounded from below by $c^n$, $c>1$. We introduce examples of such pairs with invertible decomposition $F_n ={G^1}_n{G^2}_n\dots {G^k}_n$, i.e. the decomposition which allows to compute the value of ${F^n}^{-1}$ in given point $\mathrm{p}=(p_1, p_2, \dots, p_n)$ in a polynomial time $O(n^2)$. The pair of families ${F_n}$, $F'_n$ of nonbijective polynomial maps of affine space $K^n$ such that composition $F_nF'_n$ leaves each element of ${K^*}^n$ unchanged such that $\operatorname{deg}(F_n)$ is bounded by independent constant but $\operatorname{deg}(F'_n)$ is of an exponential size and there is a decomposition ${G^1}_n{G^2}_n\dots {G^k}_n$ of $F_n$ which allows to compute the reimage of vector from $F({K^*}^n)$ in time $0(n^2)$. We introduce examples of such families in cases of rings $K=F_q$ and $K=Z_m$.

Détail

Keywords: multivariate cryptography, linguistic graphs, multivariate stable maps.

Bibliographie

[1] Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, Advances in Information Security, 25, Springer, 2006, 259 pp. | MR | Zbl

[2] Goubin L., Patarin J., Bo-Yin Yang, “Multivariate Cryptography”, Encyclopedia of Cryptography and Security, 2nd ed., 2011, 824–828

[3] Porras J., Baena J., Ding J., “New Candidates for Multivariate Trapdoor Functions”, Revista Colombiana de Matematicas, 49:1, November (2015), 57–76 | DOI | MR | Zbl

[4] Ustimenko V. A., “Explicit constructions of extremal graphs and new multivariate cryptosystems” (Budapest, 2014), Studia Scientiarum Mathematicarum Hungarica, 52:2, Proceedings of The Central European Conference on Cryptology (2015), 185–204 | DOI | MR | Zbl

[5] Ustimenko V., “On Multivariate Cryptosystems Based on Computable Maps with Invertible Decompositions”, Annales of UMCS. Informatica, 14, Proceedings of International Conference Cryptography and Security Systems (2014), 7–18 | DOI | MR

[6] Patarin J., “The Oil and Vinegar digital signatures”, Dagstuhl Workshop on Cryptography, 1997

[7] Kipnis A., Shamir A., “Cryptanalisis of the Oil and Vinegar Signature Scheme”, Advances in Cryptology, Crypto 96, Lecture Notes in Computer Science, 1462, 1996, 257–266 | DOI | MR

[8] Bulygin S., Petzoldt A. and Buchmann J., “Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks”, Progress in Cryptology – INDOCRYPT, Lecture notes in Computer Science, 6498, eds. Guang Gong and Kishan Chand Gupta, 2010, 17–32 | DOI | MR | Zbl

[9] Romańczuk-Polubiec U., Ustimenko V., “On two windows multivariate cryptosystem depending on random parameters”, Algebra Discrete Math., 19:1 (2015), 101–129 | MR | Zbl

[10] Ustimenko V., “On Shubert cells in grassmanians and new algorithm of multivariate cryptography”, Proceedings of Institute of Mathematics, 23:2 (2015), 137–148, Minsk | MR

[11] Ustimenko V., “On algebraic graph theory and non-bijective maps in cryptography”, Algebra and Discrete Mathematics, 20:1 (2015), 152–170 | MR | Zbl

[12] Ustimenko V., Wroblewska A., “On the key exchange with nonlinear polynomial maps of stable degree”, Annalles UMCS Informatica. Sec. AI, XI:2 (2011), 81–93 | MR | Zbl

[13] Ustimenko V., Romanczuk U., “On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography”, Artificial Intelligence, Evolutionary Computing and Metaheuristics, Footsteps of Alan Turing Series: Studies in Computational Intelligence, 427, January, Springer, 2013, 257–285 | Zbl

[14] Wroblewska A., “On some properties of graph based public keys”, Albanian Journal of Mathematics, 2:3 (2008), 229–234 ; New challenges in digital communications, Proceedings of NATO Advanced Studies Institute | MR | Zbl

[15] Ustimenko V. A., “Maximality of affine group and hidden graph cryptosystems”, Algebra Discrete Math., 2005, no. 1, 133–150 | MR | Zbl

[16] Ustimenko V. A., “On new multivariate cryptosystems based on hidden Eulerian equations”, Dop. Nat. Acad. Sci. Ukraine, 2017, no. 5, 17–24 (English) | Zbl

[17] V. I. Sushchansky, V. A. Ustimenko, “On the characterization of types of Boolean functions”, Calculations in Algebra and Combinatorics, Inst.Cyb., NAN Ukr., Kiev, 1979, 44–51

[18] L. A. Kaluznin, V. I. Sushchansky, V. A. Ustimenko, “Exponentiation in permutation group theory and its applications”, Proceedings of the Sixth Soviet Union Conference on the group theory, Inst. Math. Ukr. Acad. Sci., Kiev, 1979, 135–145

[19] L. A. Kaluznin, V. I. Sushchansky, V. A. Ustimenko, “On the system of computer programs for studies of permutation groups”, Proceedings of the Conference on Interactive Systems (Borjomi, March 1981), Tbilisi, Georgia, USSR, 32–37 | MR

[20] L. A. Kaluznin, V. I. Sushchansky, V. Ustimenko, “Computer science and its applications to the theory of permutation groups”, Kibernetika, 1982, no. 6, 63–84