On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition

• Autorzy: Ustimenko V.
• Języki publikacji: EN

Abstrakty

EN

Let K be a commutative ring and K^n be a space over K of dimension n. We introduce the concept of a family of multivariate maps f(n) of K^n into itself with invertible decomposition.If f(n) is computable in polynomial time then it can be used as the public rule and the invertible decomposition provides a private key in f(n) based public key infrastructure. Requirementsof polynomial ity of degree and density for f(n) allow to estimate the complexity of encryption procedurefor a public user. The concepts of a stable family and a family of increasing order are motivatedby the studies of discrete logarithm problem in the Cremona group. The statement on the existenceof families of multivariate maps of polynomial degree and polynomial density of increasing order with the invertible decomposition is proved. The proof is supported by explicite construction which canbe used as a new cryptosystem. The presented multivariate encryption maps are induced by special walks in the algebraically dened extremal graphs A(n;K) and D(n;K) of increasing girth.

Słowa kluczowe

EN

multivariate map; invertible decomposition; public key infrastructure

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2014
• Tom: Vol. 14, no. 1
• Strony: 7--17
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Ustimenko V.

• Institute of Computer Science, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland

Bibliografia

• [1] Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, Springer, Advances in Information Security 25 (2006): 260.
• [2] Bollobás B., Extremal Graph Theory, Academic Press, London (1978).
• [3] Erdös’ P., R’enyi A. and S’oc V. T., On a problem of graph theory, Studia. Sci. Math. Hungar 1 (1966): 215-235.
• [4] Erdös’ P., Simonovits M., Compactness results in extremal graph theory, Combinatorica 2(3) (1982): 275-288.
• [5] Simonovitz M., Extermal Graph Theory , In ”Selected Topics in Graph Theory”, 2, edited by Beineke L. W. and Wilson R. J., Academic Press, London (1983): 161-200.
• [6] Ustimenko V., Coordinatisation of Trees and their Quotients, In the ”Voronoj’s Impact on Modern Science”, Kiev, Institute of Mathematics 2 (1998): 125-152.
• [7] Ustimenko V., CRYPTIM: Graphs as Tools for Symmetric Encryption, Lecture Notes in Computer Science, Springer 2227 (2001): 278–287.
• [8] Ustimenko V. Maximality of affine group and hidden graph cryptosystems J. Algebra Discrete Math 1 (2005): 133–150.
• [9] Wróblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics, NATO Advanced Studies Institute: "New challenges in digital communications”2(3) (2008) : 229–234.
• [10] Ustimenko V., Wróblewska A., On some algebraic aspects of data security in cloud computing, Proceedings of International conference֒ "Applications of Computer Algebra”, Malaga (2013): 144–147.
• [11] Romańczuk U., Ustimenko V., On regular forests given in terms of algebraic geometry, new families of expanding graphs with large girth and new multivariate cryptographical algorithms, Proceedings of International conference֒ "Applications of Computer Algebra”, Malaga (2013): 135–139.
• [12] Margulis G., Explicit group-theoretical constructions of combinatorial schemes and their application to desighn of expanders and concentrators, Probl. Peredachi Informatsii., 24, N1, 51-60. English translation publ. Journal of Problems of Information transmission (1988): 39–46.
• [13] Lubotsky A., Philips R., Sarnak P., Ramanujan graphs, J. Comb. Theory 115(2) (1989): 62–89.
• [14] Lazebnik F., Ustimenko V., Woldar A. J., A New Series of Dense Graphs of High Girth, Bull (New Series) of AMS, 32 (1995): 73–79.
• [15] Ustimenko V., Some optimisation problems for graphs and multivariate cryptography (in Russian), In Topics in Graph Theory: A tribute to A.A. and T. E. Zykova on the ocassion of A. A. Zykov birthday, 2013): 15–25, www.math.uiuc.edu/kostochka.
• [16] Ustimenko V., On extremal graph theory and symbolic computations, Dopovidi National Academy of Sci of Ukraine, N2 (in Russian) (2013): 42–49.
• [17] Ustimenko V., On the extremal graph theory for directed graphs and its cryptographical applications In: T. Shaska, W.C. Huffman, D. Joener and V. Ustimenko, Advances in Coding Theory and Cryptography, Series on Coding and Cryptology 3 (2007): 181–200.
• [18] Kotorowicz J., Ustimenko V., On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings, Condenced Matters Physics, Special Issue: Proceedings of the international conferences “Infinite particle systems, Complex systems theory and its application”, Kazimerz Dolny, Poland 2(54) (2008): 347–360.
• [19] Ustimenko V., Romańczuk U., On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, in֒ "Artificial Intelligence, Evolutionary Computing and Metaheuristics ”, In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Springer, 427 (2013): 257–285.
• [20] Ustimenko V., Romańczuk U., On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, in֒ "Artificial Intelligence, Evolutionary Computing and Metaheuristics ”, In the footsteps of Alan Turing Series: Studies in Computational Intelligence 427 (2013): 257–285.
• [21] 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.
• [22] Ustimenko V., On the cryptographical properties of extreme algebraic graphs, in Algebraic Aspects of Digital Communications, IOS Press (Lectures of Advanced NATO Institute, NATO Science for Peace and Security Series - D: Information and Communication Security 24 (2009): 296.