On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree

• Autorzy: Ustimenko V. , Wroblewska A.

Identyfikatory

DOI

10.2478/v10065-012-0047-6

• Języki publikacji: EN

Abstrakty

EN

We say that the sequence g_n, n≥3, n→∞ of polynomial transformation bijective mapsof free module Kgⁿ over commutative ring K is a sequence of stable degree if the order of g_n is growing with n and the degree of each nonidentical polynomial map of kind g^k_n is an independent constant c. Transformation b = τg_n^kτ−1, where τ is the affine bijection, n is large and k is relatively small, can be used as a base of group theoretical Diffie-Hellman key exchange algorithm for the Cremona group C(Kⁿ) of all regular automorphisms of Kⁿ. The specific feature of this method is that the order of the base may be unknown for the adversary because of the complexity of its computation. The exchange can be implemented by tools of Computer Algebra (symbolic computations). The adversary can not use the degree of right handside in b^x = d to evaluate unknown x in this form for the discrete logarithm problem. In the paper we introduce the explicit constructions of sequences of elements of stable degree for the cases c = 3 and c = n+2/4 for each commutative ring K containing at least 3 regular elements and discuss the implementation of related key exchange and multivariate map algorithms.

Słowa kluczowe

EN

key exchange; polynomial mapping; stable degree

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2013
• Tom: Vol. 13, no. 1
• Strony: 63--80
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Ustimenko V.

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

autor

Wroblewska A.

• Institute of Fundamental Technological Research, Polish Academy of Sciences ul. Pawinskiego 5B; 02-106 Warszawa, Poland
• Institute of Mathematics, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland

Bibliografia

• [1] Moore E. H., Tactical Memoranda, Amer. J. Math. 18 (1886): 264.
• [2] 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.
• [3] Wroblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics 2(3) (2008): 229.
• [4] Bollobás B., Extremal Graph Theory, Academic Press, London (1978).
• [5] Margulis G. A., Explicit construction of graphs without short cycles and low density codes, Combinatorica 2 (1982): 71.
• [6] Lubotsky A., Philips R., Sarnak P., Ramanujan graphs, J. Comb. Theory. 115(2) (1989): 62.
• [7] Guinand P. S., 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.
• [8] Guinand P. S., 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.
• [9] 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.
• [10] 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).
• [11] 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.
• [12] Ustimenko V. A., CRYPTIM: Graphs as Tools for Symmetric Encryption, in Lecture Notes in Computer Science 2227 (2001): 278.
• [13] Ustimenko V. A., 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., 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).
• [17] Ustimenko V. A., Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer 140(3) (2007): 412.
• [18] Ustimenko V. A., 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.
• [19] Biggs N. L., Graphs with large girth, Ars Combinatoria 25C (1988): 73.
• [20] Lazebnik F., Ustimenko V. A., Woldar A. J., A Characterization of the Components of the graphs D(k, q), Discrete Mathematics 157 (1996): 271.
• [21] Lazebnik F., Ustimenko V., Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. 60 (1995): 275.