Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography

• Autorzy: Ustimenko V. , Wroblewska A.

Identyfikatory

DOI

10.2478/v10065-012-0030-2

• Języki publikacji: EN

Abstrakty

EN

Let K be a finite commutative ring and f = f(n) a bijective polynomial map f(n) of the Cartesian power K^n onto itself of a small degree c and of a large order. Let f^y be a multiple composition of f with itself in the group of all polynomial automorphisms, of free module K^n. The discrete logarithm problem with the pseudorandom base f(n) (solvef^y = b for y) is a hard task if n is sufficiently large. We will use families of algebraic graphs defined over K and corresponding dynamical systems for the explicit constructions of such maps f(n) of a large order with c = 2 such that all nonidentical powers f^y are quadratic polynomial maps. The above mentioned result is used in the cryptographical algorithms based on the maps f(n) – in the symbolic key exchange protocols and public keys algorithms.

Słowa kluczowe

EN

discrete logarithm; cryptographic algorithm; cryptography; public key cryptography

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 3
• Strony: 65--74
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Ustimenko V.

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

autor

Wroblewska A.

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

Bibliografia

• [1] Klisowski M., Ustimenko V., On the implementation of public keys algorithms based on algebraic graphs over finite commutative rings, Proceedings of International CANA conference, Wisła (2010).
• [2] 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.
• [3] Lazebnik F., Ustimenko V., Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. 60 (1995): 275.
• [4] Ustimenko V., CRYPTIM: Graphs as Tools for Symmetric Encryption, Lecture Notes in Computer Science 2227 (2001): 278.
• [5] Wroblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics 2 (3) (2008): 229.
• [6] Bollobás B., Extremal Graph Theory, Academic Press,
• [7] Margulis G. A., Explicit construction of graphs without short cycles and low density codes, Combirica 2 (1982): 71.
• [8] Lubotsky A., Philips R., 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 J. L., Peled U. N., Perepelitsa I., Pless V., 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] Ustimenko V. A., Maximality of affine group, and hidden graph cryptosystems, J.Algebra and Discrete Math. 10 (2004): 51.
• [15] 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).
• [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] 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.
• [19] Biggs N. L., Graphs with large girth, Ars Combinatoria 25C (1988): 73.
• [20] Moore E. H., Tactical Memoranda, Amer. J. Math. 18 (1886): 264.
• [21] Lazebnik F., Ustimenko V. A., Woldar A. J., A Characterization of the Components of the graphs D(k, q), Discrete Mathematics 157 (1996): 271.