On the key exchange with new cubical maps based on graphs

• Autorzy: Romańczuk U. , Ustimenko V.
• Języki publikacji: EN

Abstrakty

EN

Families of edge transitive algebraic graphs Fn(K), over the commutative ring K were used for the graph based cryptographic algorithms. We introduce a key exchange protocol defined in terms of bipartite graph An(K), n ≥ 2 with point set Pn and line set Ln isomorphic to n-dimensional free module Kn. Graphs A(n, K) are not vertex and edge transitive. There is a well defined projective limit lim A(n, K) = A(K), n → ∞ which is an infinite bipatrtite graph with point set P = lim Pn and line set L = limLn. Let K be a commutative ring contain at least 3 regular elements (not zero divisors). For each pair of (n, d), n ≥ 2, n ≥ 1 and sequence of elements α1, α2, …, α2d, such that α1, αi+αi+1, i = 1, 2, …, 2d, i = 1, 2, … 2d-1 and α2d+α1 are regular elements of the ring K. We define polynomial automorphism hn = hn (d, α1, α2, …, α2d) of variety Ln (or Pn). The existence of projective limit lim An(K) guarantees the existence of projective limit h = h(d, α1, α2, …, α2d) = lim hn, n → ∞ which is cubical automorphism of infinite dimensional varieties L (or P). We state that the order of h is an infinity. There is a constant n0 such that hn, n ≥ n0 is a cubical map. Obviously the order of hn is growing with the growth of n and the degree of polynomial map (hn)k from the Cremona group of all polynomial automorphisms of free module Kn with operation of composition is bounded by 3. Let τ be affine automorphism of Kn i.e. the element of Cremona group of degree 1. We suggest symbolic Diffie Hellman key exchange with the use of cyclic subgroup of Cremona group generated by τ-1hnτ. In the case of K = Fp, p is prime, the order of hn is the power of p. So the order is growing with the growth of p. We use computer simulation to evaluate the orders in some cases of K = Zm, where m is a composite integer.

Słowa kluczowe

EN

key exchange; algebraic graph; cryptographic algorithms; bipartite graph

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2011
• Tom: Vol. 11, no. 4
• Strony: 11--19
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Romańczuk U.

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

autor

Ustimenko V.

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

Bibliografia

• [1] Ustimenko V. A., On the Varieties of Parabolic Subgroups, their Generalizations and Combinatorial Applications, Acta Applicandae Mathematicae 52 (1998): 223.
• [2] Ustimenko V. A., Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences 140(N3) (2007): 412.
• [3] Ustimenko V., Algebraic graphs and security of digital communications, University of Maria Curie Sklodowska (2011): 154.
• [4] Wróblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics 2(3) (2008): 229.
• [5] Biggs N., Algebraic Graph Theory (2nd ed), Cambridge, University Press (1993).
• [6] Shaska T., Ustimenko V., On the homogeneous algebraic graphs of large girth and their applications, Linear Algebra and its Applications Article 430(7) (2009), Special Issue in Honor of Thomas J. Laffey.
• [7] Ustimenko V. A., Graphs with Special Arcs and Cryptography, Acta Applicandae Mathematicae 71(N2) (2002): 117.
• [8] Ustimenko V. A., Maximality of affine group, and hidden graph cryptosystems, J. Algebra and Discrete Math. 10 (2004): 51.
• [9] Ustimenko V., CRYPTIM: Graphs as Tools for Symmetric Encryption, in Lecture Notes in Computer Science 2227 (2001): 278.
• [10] 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.
• [11] Ustimenko V. A., On the extremal regular directed graphs without commutative diagrams and their applications in coding theory and cryptography, Albanian. J. of Mathematics, Special Issue "Algebra and Computational Algebraic Geometry" 1(N4) (2007): 387.
• [12] Ustimenko V. A., On the cryptographical properties of extremal 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.
• [13] Ustimenko V. A., Wróblewska A., On the key exchange with nonlinear polynomial maps of degree 4, Albanian Journal of Mathematics, Special Issue, Applications of Computer Algebra 4(4) (2010).
• [14] Romańczuk U., Ustimenko V., On the key exchange with matrices of large order and graph based nonlinear maps, Albanian. J. of Mathematics, Special Issue, Applications of Computer Algebra 4(4) (2010): 203.
• [15] Moore E. H., Tactical Memoranda, Amer. J. Math. 18 (1886): 264.
• [16] Klisowski M., Romańczuk U., Ustimenko V., On the implementation of cubic public keys based on new family of algebraic graphs, Annales UMCS Informatica AI XI(2) (2011): 127.
• [17] J. S. Kotorowicz, U. Romańczuk, V. Ustimenko „On the implementation of stream ciphers based on a new family of algebraic graphs” IEEE Computer Society Press, Proceedings of the Conference CANA, FedSCIS, pp. 485-490
• [18] Klisowski M., Ustimenko V., On the public keys based on the extremal graphs and digraphs, International Multiconference on Computer Science and Informational Technology, October 2010, Wisla, Poland, CANA Proceedings.
• [19] Koblitz N., Algebraic Aspects of Cryptography, Springer (1998): 198.
• [20] Mortimer B., Permutation groups containing affine transformations of the same degree, J. London Math. Soc. 15(N3) (1972): 445.