The implementation of cubic public keys based on a new family of algebraic graphs

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

Abstrakty

EN

Families of edge transitive algebraic graphs defined over finite commutative rings were used for the development of stream ciphers, public key cryptosystems and key exchange protocols. We present the results of the first implementation of a public key algorithm based on the family of algebraic graphs, which are not edge transitive. The absence of an edge transitive group of symmetries means that the algorithm can not be described in group theoretical terms. We hope that it licates cryptanalysis of the algorithm. We discuss the connections between the security of algorithms and the discrete logarithm problem.The plainspace of the algorithm is Kn, where K is the chosen commutative ring. The graph theoretical encryption corresponds to walk on the bipartite graph with the partition sets which are isomorphic to Kn. We conjugate the chosen graph based encryption map, which is a composition of several elementary cubical polynomial automorphisms of a free module Kn with special invertible affine transformation of Kn. Finally we compute symbolically the corresponding cubic public map g of Kn onto Kn. We evaluate time for the generation of g, and the number of monomial expression in the list of corresponding public rules.

Słowa kluczowe

EN

algebraic graph; public key; cryptosystems; key exchange protocol

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

Twórcy

autor

Klisowski M.

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

autor

Romańczuk U.

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

autor

Ustimenko V.

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

Bibliografia

• [1] Romańczuk U., Ustymenko V., On some cryptographical applications of new family of expanding graphs, Presentation in Conference CECC’2011, Debrecen, Hungary.
• [2] Ustimenko V., Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer, 140(3) (2007): 412-434.
• [3] Kotorowicz S., Ustimenko V., On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings, Condens. Matter Phys. 11(2)(54) (2008): 347–360.
• [4] Klisowski M., Ustimenko V. A., 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, 12 pp.
• [5] Shaska T., Ustimenko V., On some applications of graph theory to cryptography and turbocoding, Albanian J. Math. 2(3) (2008): 249–255, Proceedings of the NATO Advanced Studies Institute: ”New challenges in digital communications”.
• [6] Shaska T., Ustimenko V., On the homogeneous algebraic graphs of large girth and their applications, Linear Algebra Appl. 430(7) (2009): 1826–1837, Special Issue in Honor of Thomas J. Laffey.
• [7] Ustimenko V., On the extremal graph theory for directed graphs and its cryptographical applications, Advances in Coding Theory and Cryptography (T. Shaska, D. W. C. Huffman, Joener, and V. Ustimenko, eds.), Series on Coding Theory and Cryptology, World Scientific 3 (2007): 181–199.
• [8] Ustimenko V., On the extremal regular directed graphs without commutative diagrams and their applications in coding theory and cryptography, Albanian J. Math. 1(4) (2007), Special issue on algebra and computational algebraic geometry.
• [9] Ustimenko V., Algebraic groups and small world graphs of high girth, Albanian J. Math. 3(1) (2009): 25–33.
• [10] Ustimenko V., On the cryptographical properties of extremal algebraic graphs, Algebraic Aspects of Digital Communications (Tanush Shaska and Engjell Hasimaj, eds.), NATO Science for Peace and Security Series - D: Information and Communication Security, 24, IOS Press, (2009): 256–281.
• [11] Bollob´as B., Extremal graph theory, Academic Press, London, (1978).
• [12] Simonovits M., Extremal graph theory, Selected Topics in Graph Theory 2(2) (1983): 161–200 (L. W. Beineke and R. J. Wilson, eds.), Academic Press, London.
• [13] Bien F., Constructions of telephone networks by group representations, Notices Amer. Math. Soc. 3 (1989): 5–22.
• [14] Ore R., Graph theory, Wiley, London (1971).
• [15] Koblitz N., Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, 3 (1998) Springer.
• [16] Ustimenko V., Algebraic graphs and security of digital communications, Institute of Computer Science, University of Maria Curie Sklodowska in Lublin (2011) (supported by European Social Foundation), available at the UMCS web.
• [17] Crandall R., Pomerance C., Prime Numbers. A Computational Perspective, Springer, New York (2001).
• [18] Menezes A. J., van Oorschot P. C. and Vanstone S. A., Handbook of Applied Cryptography, CRC Press, Inc. third edition (1997).
• [19] Lazebnik F., Ustimenko V. A., and Woldar A. J., A new series of dense graphs of high girth, Bull. Amer. Math. Soc. (N.S.) 32(1) (1995): 73–79.
• [20] Kotorowicz J., Ustimenko V., On the properties of stream ciphers based on extremal directed graphs, Cryptography Research Perspective (Roland E. Chen, ed.), Nova Science Publishers (2009): 125–141.
• [21] Patarin J., Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt ’88, Advances in Cryptology — Crypto ’95, Springer (1995): 248-261.
• [22] Touzene A., Ustimenko V., AlRaissi M. and Boudeliouua I., Performance of Algebraic Graphs Based Stream-Ciphers Using Large Finite Fields (to appear).
• [23] Klisowski M., Ustimenko V., On the implementation of cubic public keys based on algebraic graphs over the finite commutative ring and their special symmetries, Presentation
• [24] Kotorowicz S., Roma´nczuk U. and Ustimenko V., On the implementation of stream ciphers based on a new family of algebraic graphs, Presentation in Conference FedCSIS’ 2011, Szczecin, Poland.
• [25] Wróblewska A., Ustymenko V., On the key expansion of D(n;K)-based cryptographical algorithm, Presentation in Conference CECC’2011, Debrecen, Hungary.