On algebraic graph theory and non-bijective multivariate maps in cryptography

Vasyl Ustimenko

Algebra and discrete mathematics, Tome 20 (2015) no. 1, pp. 152-170.

Résumé

Special family of non-bijective multivariate maps $F_n$ of ${Z_m}^n$ into itself is constructed for $n = 2, 3, \dots$ and composite $m$. The map $F_n$ is injective on $\Omega_n=\{{\rm x}|x_1+x_2 + \dots x_n \in {Z_m}^* \}$ and solution of the equation $F_n({\rm x})={\rm b}, {\rm x}\in \Omega_n$ can be reduced to the solution of equation $z^r=\alpha$, $z \in {Z_m}^*$, $(r, \phi(m))=1$. The “hidden RSA cryptosystem” is proposed. Similar construction is suggested for the case $\Omega_n={{Z_m}^*}^n$.

Détail

Keywords: multivariate cryptography, linguistic graphs, hidden Eulerian equation, hidden discrete logarithm problem.

Bibliographie

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

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

[3] V. A. Ustimenko, “Graphs with Special Arcs and Cryptography”, Acta Applicandae Mathematicae, 71:2, November (2002), 117–153 | DOI | MR

[4] Ustimenko V., “On the extremal graph theory for directed graphs and its cryptographical applications”, Advances in Coding Theory and Cryptography, Series on Coding and Cryptology, 3, eds. T. Shaska, W. C. Huffman, D. Joener and V. Ustimenko, 2007, 181–200 | DOI | MR

[5] V. A. Ustimenko, “On the flag geometry of simple group of Lie type and Multivariate Cryptography”, Algebra and Discrete Mathematics, 19:1 (2015), 130–144 | MR | Zbl

[6] V. Ustimenko, “On walks of variable length in Schubert incidence systems and multivariate flow ciphers”, Dopovidi of Nathional Acad. Sci. of Ukraine, 2014, no. 3, 55–150

[7] Koblitz N., Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, 3, Springer, 1998 | DOI | MR | Zbl

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

[9] Patarin J., The Oil i Vinegar digital signatures, Presented at Dagstuhl Workshop on Cryptography, 1997

[10] 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

[11] S. Bulygin, A. Petzoldt, and J. Buchmann, “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

[12] U. Romanczuk-Polubiec, V. Ustimenko, “On two windows multivariate cryptosystem depending on random parameters”, Algebra and Discrete Mathematics, 19:1 (2015), 101–129 | MR | Zbl

[13] F. Harary, Graph Theory, Addison-Wesley Publishing Co, Reading, MA, 1966 | MR

[14] V. Ustimenko, “Maximality of affine group, hidden graph cryptosystem and graph's stream ciphers”, Journal of Algebra and Discrete Mathematics, 1 (2005), 51–65 | MR

[15] F. Lazebnik, V. Ustimenko and A. J. Woldar, “A new series of dense graphs of high girth”, Bulletin of the AMS, 32:1 (1995), 73–79 | DOI | MR | Zbl

[16] F. Lazebnik, V. Ustimenko, “Explicit construction of graphs with arbitrary large girth and of large size”, Discrete Applied Mathematics, 60 (1995), 275–284 | DOI | MR | Zbl

[17] Ustimenko V., “Coordinatisation of Trees and their Quotients”, The “Voronoj's Impact on Modern Science”, v. 2, Institute of Mathematics, Kiev, 1998, 125–152 | Zbl

[18] V. Ustimenko, “CRYPTIM: Graphs as Tools for Symmetric Encryption”, Lecture Notes in Computer Science, 2227, Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes, Springer, 2001, 278–286 | DOI | MR | Zbl

[19] Ustimenko V. A., “Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography”, Journal of Mathematical Sciences, 140:3 (2007), 412–434 | DOI | MR | Zbl

[20] Ustimenko V. A., “On the graph based cryptography and symbolic computations”, ACA-2006 (Varna), Serdica Journal of Computing, Proceedings of International Conference on Application of Computer Algebra, no. 1, 2007 | MR

[21] Ustimenko V., Romańczuk U., “On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography”, Artificial Intelligence, Evolutionary Computing and Metaheuristics. In the footsteps of Alan Turing Series, Studies in Computational Intelligence, 427, Springer, 2013, 257–285 | DOI | Zbl

[22] Ustimenko V., Romańczuk U., “On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography”, Artificial Intelligence, Evolutionary Computing and Metaheuristics. In the footsteps of Alan Turing Series, Studies in Computational Intelligence, 427, Springer, 2013, 257–285 | DOI | Zbl

[23] V. Ustimenko, “On the cryptographical properties of extreme algebraic graphs”, Algebraic Aspects of Digital Communications, Lectures of Advanced NATO Institute, NATO Science for Peace and Security, Series Information and Communication Security, 24, July, IOS Press, 2009, 296 pp. | MR | Zbl

[24] U. Romanczuk-Polubiec, V. Ustimenko, “On Multivariate Cryptosystems Based on Polynomially Compressed Maps with Invertible Decompositions”, Cryptography and Security Systems, Third International Conference, CSS 2014 (Lublin, Poland, September 22–24), Communications in Computer and Information Science, 448, 2014, 23–37 | DOI

[25] M. Klisowski, V. Ustimenko, “Graph based cubical multivariate maps and their cryptographical applications”, Advances on Superelliptic curves and their Applicationsions, NATO Science for Peace and Security series, Information and Communication Security, 41, IOS Press, 2015, 305–327

[26] A. Tousene, V. Ustimenko, “CRYPTALL — a System to Encrypt All types of Data”, Notices of Kiev-Mohyla Academy, 23 (2004), 12–15

[27] A. Touzene, V. Ustimenko, “Graph Based Private Key Crypto System”, International Journal on Computer Research, 13:3 (2006), 275–282, Nova Science Publisher

[28] J. Kotorowicz, V. Ustimenko, “On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings” (Kazimerz Dolny, Poland 2006), Condenced Matters Physics, 11:2(54), Special Issue: Proceedings of the international conferences “Infinite particle systems, Complex systems theory and its application” (2008), 347–360 | DOI

[29] V. Ustimenko, S. Kotorowicz, “On the properties of Stream Ciphers Based on Extremal Directed graphs”, Cryptography Research Perspectives, ed. Ronald E. Chen, Nova Publishers, 2008

[30] A. Touzene, V. Ustimenko, Marwa AlRaisi, Imene Boudelioua, “Performance of Algebraic Graphs Based Stream-Ciphers Using Large Finite Fields”, Annalles UMCS Informatica, X1:2 (2011), 81–93 | Zbl

[31] Klisowski M., Ustimenko V., “On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator”, Mathematics in Computer Science, 6:2 (2012), 181–198 | DOI | MR | Zbl

[32] Ustimenko V. A., “Algebraic groups and small world graphs of high girth”, Albanian J. Math., 3:1 (2009), 25–33 | MR | Zbl

[33] V. A. Ustimenko, A. Wroblevska, On the key exchange with nonlinear polynomial map of stable degree, arXiv: 1304.2920v1