On the key expansion of D(n, K)-based cryptographical algorithm

• Autorzy: Ustimenko V. , Wróblewska A.
• Języki publikacji: EN

Abstrakty

EN

The family of algebraic graphs D(n, K) defined over finite commutative ring K have been used in different cryptographical algorithms (private and public keys, key exchange protocols). The encryption maps correspond to special walks on this graph. We expand the class of encryption maps via the use of edge transitive automorphism group G(n, K) of D(n, K). The graph D(n, K) and related directed graphs are disconnected. So private keys corresponding to walks preserve each connected component. The group G(n, K) of transformations generated by an expanded set of encryption maps acts transitively on the plainspace. Thus we have a great difference with block ciphers, any plaintexts can be transformed to an arbitrarily chosen ciphertex by an encryption map. The plainspace for the D(n, K) graph based encryption is a free module P over the ring K. The group G(n, K) is a subgroup of Cremona group of all polynomial automorphisms. The maximal degree for a polynomial from G(n, K) is 3. We discuss the Diffie-Hellman algorithm based on the discrete logarithm problem for the group τ-1Gτ, where τ is invertible affine transformation of free module P i.e. polynomial automorphism of degree 1. We consider some relations for the discrete logarithm problem for G(n, K) and public key algorithm based on the D(n, K) graphs.

Słowa kluczowe

EN

cryptographic algorithm; algebraic graph; encryption map

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2011
• Tom: Vol. 11, no. 2
• Strony: 95--111
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Ustimenko V.

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

autor

Wróblewska A.

• Institute of Fundamental Technological Research Polish Academy of Sciences, ul. Pawinskiego 5B; 02-106 Warszawa, Poland

Bibliografia

• [1] Ustimenko V., CRYPTIM: Graphs as Tools for Symmetric Encryption, in Lecture Notes in Computer Science, Springer 2227 (2001): 278.
• [2] Ustimenko V., On the graph based cryptography and symbolic computations, Serdica Journal of Computing, Proceedings of International Conference on Application of Computer Algebra, ACA-2006, Varna, N1 (2007).
• [3] Ustimenko V., Wroblewska A., On the key exchange with nonlinear polynomial maps of stable degree, Fundamenta Informaticae, to appear
• [4] Ustimenko V. A., On the cryptographical properties of extremal algebraic graphs, in Algebraic Aspects of Digital Communications, NATO Science for Peace and Security Series - D: Information and Communication Security, 24 (2009): 296.
• [5] Wroblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics 2(3) (2008): 229.
• [6] B. Bollobas, Extremal Graph Theory, Academic Press, London (1978).
• [7] Margulis G. A., Explicit construction of graphs without short cycles and low density codes, Combinatorica 2 (1982): 71.
• [8] Lubotsky A., Philips R. and Sarnak P., Ramanujan graphs, J. Comb. Theory. 115(2) (1989): 62.
• [9] Guinand P., Lodge J., Tanner Type Codes Arising from Large Girth Graphs, Proceedings of the 1997 Canadian Workshop on Information Theory (CWIT ’97), Toronto, Ontario, Canada, June 3-6 (1997): 5.
• [10] Guinand P., Lodge J., Graph Theoretic Construction of Generalized Product Codes, Proceedings of the 1997 IEEE International Symposium on Information Theory (ISIT ’97), Ulm, Germany, June 29-July 4 (1997): 111.
• [11] Kim Jon-Lark, Peled U. N., Perepelitsa I., Pless V. and Friedland S., Explicit construction of families of LDPC codes with no 4-cycles , Information Theory, IEEE Transactions, 50(10) (2004): 2378.
• [12] Ustimenko V. A., Coordinatisation of regular tree and its quotients, in ”Voronoi’s impact on modern science, eds P. Engel and H. Syta, book 2, National Acad. of Sci, Institute of Matematics (1998): 228.
• [13] Ustimenko V., Graphs with Special Arcs and Cryptography, Acta Applicandae Mathematicae 74(2) (2002): 117.
• [14] Kotorowicz S., Ustimenko V., On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings, Condensed Matter Physics 11(2(54)) (2008): 347.
• [15] Ustimenko V. A., Maximality of affine group, and hidden graph cryptosystems, J. Algebra and Discrete Math. 10 (2004): 51.
• [16] Ustimenko V. A., Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences 140(3) (2007): 412.
• [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.
• [18] Klisowski M., Ustimenko V., On the implementation of public keys algorithms based on algebraic graphs over finite commutative rings, Proceedings of International CANA conference, Wisla (2010).
• [19] Ustimenko V., Wroblewska 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).
• [20] Biggs N.L., Graphs with large girth, Ars Combinatoria, 25C (1988): 73.
• [21] Moore E. H., Tactical Memoranda, Amer. J. Math., 18 (1886): 264.
• [22] Lazebnik F., Ustimenko V. A. and Woldar A. J., A Characterization of the Components of the graphs D(k; q), Discrete Mathematics 157 (1996): 271.
• [23] Lazebnik F., Ustimenko V., Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. 60 (1995): 275.