On New Examples of Families of Multivariate Stable Maps and their Cryptographical Applications

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

Abstrakty

EN

Let K be a general finite commutative ring. We refer to a family g_n, n = 1, 2, . . . of bijective polynomial multivariate maps of K_n as a family with invertible decomposition g_n = g_n¹ g_n² . . . g g_n^k, such that the knowledge of the composition of g_nⁱ allows computation of g_nⁱ for O(n^s) (s > 0) elementary steps. A polynomial map g is stable if all non-identical elements of kind g^t, t > 0 are of the same degree. We construct a new family of stable elements with invertible decomposition. This is the first construction of the family of maps based on walks on the bipartite algebraic graphs defined over K, which are not edge transitive. We describe the application of the above mentioned construction for the development of stream ciphers, public key algorithms and key exchange protocols. The absence of edge transitive group essentially complicates cryptanalysis.

Słowa kluczowe

EN

multivariate map; cryptographical application; stable element; invertible decomposition

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2014
• Tom: Vol. 14, no. 1
• Strony: 19--36
• Opis fizyczny: Bibliogr. 39 poz.

Twórcy

autor

Wróblewska A.

• 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] Bollobás B., Extremal Graph Theory, Academic Press, London (1978).
• [2] Ding J., Gower J. E., Schmidt D. S., Multivariate Public Key Cryptosystems, Springer, Advances in Information Security, 25 (2006).
• [3] Kim Jon-Lark, 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-2388.
• [4] Klisowski M., Ustimenko V. A., On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator, Mathematics in Computer Science, 6(2) (2012): 181-198.
• [5] Koblitz N., Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, 3, Springer (1998).
• [6] Kotorowicz J. S., Ustimenko V., On the properties of stream ciphers based on extremal directed graphs, Cryptography Research Perspective (Roland E. Chen, ed.), Nova Science Publishers, April (2009): 125-141.
• [7] 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.
• [8] Kotorowicz J. S., Ustimenko V., Romaúczk U., On the implementation of stream ciphers based on a new family of algebraic graphs, IEEE Computer Society Press, Proceedings of the Conference CANA, FedSCIS (2011): 485-490.
• [9] Lubotsky A., Philips R., Sarnak P., Ramanujan graphs, J. Comb. Theory., 115(2) (1989): 62-89.
• [10] Lazebnik F., Ustimenko V., Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math., 60 (1995): 275-284.
• [11] Lazebnik F., Ustimenko V. A., Woldar A. J., New Series of Dense Graphs of High Girth, Bull (New Series) of AMS, 32(1) (1995): 73-79.
• [12] Lazebnik F., Ustimenko V. A., Woldar A. J., A Characterization of the Components of the graphs D(k, q), Discrete Mathematics, 157 (1996): 271-283.
• [13] Lazebnik F., Ustimenko V. A., Woldar A. J., Polarities of 2k-cycle-free graphs, Discrete Mathematics, 197/198 (1999): 503-513.
• [14] Margulis G. A., Explicit construction of graphs without short cycles and low density codes, Combinatorica, 2 (1982): 71-78.
• [15] Moore E. H., Tactical Memoranda, Amer. J. Math., 18 (1886): 264-303.
• [16] Romańczuk U., Ustimenko V.: On the key exchange with matrices of large order and graph based nonlinear maps, Proceedings of the conference "Applications of Computer Algebra", Vlora, Special Issue, 4(4) (2010): 203-211.
• [17] Romańczuk U., Ustimenko V., On the family of cubical multivariate cryptosystems based on the algebraic graph over finite commutative rings of characteristic 2, Annales UMCS Informatica AI XII, 3 (2012): 89-106.
• [18] Romańczuk U., Ustimenko V., On the key exchange with new cubical maps based on graphs, Annales UMCS Informatica, 4(11) (2011): 11-19.
• [19] Romańczuk U., Ustimenko V., On regular forests given in terms of algebraic geometry, new families of expanding graphs with large girth and Multivariate cryptographical algorithms, Proceedings of International conference "Applications of Computer Algebra", Malaga (2013): 144-147.
• [20] Romańczuk U., Ustimenko V., 0n the family of cubical multivariate cryptosystems based on exceptional extremal graphs, Third International Conference on Symbolic Computations and Cryptography, Castro Urdiales, Extended Abstracts, (2012): 169-175.
• [21] Ustimenko V., Coordinatisation of Trees and their Quotients, In the "Voronoj's Impact on Modern Science", Kiev, Institute of Mathematics, 2 (1998): 125-152.
• [22] Ustimenko V., CRYPTIM: Graphs as Tools for Symmetric Encryption, in Lecture Notes in Computer Science, Springer, 2227 (2001): 278-287.
• [23] Ustimenko V., Graphs with Special Arcs and Cryptography, Acta Applicandae Mathematicae, 74(2) (2001): 117-153.
• [24] Ustimenko V., Maximality of affine group and hidden graph cryptosystems, J. Algebra Discrete Math., 1 (2005): 133-150.
• [25] Ustimenko V., On the cryptographical properties of extreme 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.
• [26] Ustimenko V., Schubert cells in Lie geometries and key exchange via symbolic computations, Proceedings of the International Conference "Applications of Computer Algebra", Vlora, Albanian Journal of Mathematics, Special Issue, 4(4) (2010): 135-145.
• [27] 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-200.
• [28] Ustimenko V., Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer, 140(3) (2007): 412-434.
• [29] 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 (2007).
• [30] Ustimenko V., Algebraic groups and small world graphs of high girth, Albanian J. Math. 3(1) (2009): 25-33.
• [31] Ustimenko V., On extremal graph theory and symbolic computations Dopovidi National Academy of Sci of Ukraine, (in Russian), 2 (2013): 42-49.
• [32] Ustimenko V., In the K - theory of graph based dynamical systems and its applications, Dopovidi National Academy of Sci of Ukraine, 8 (2013): 44-51.
• [33] Ustimenko V., Romańczuk U., On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, Artificial Intelligence, Evolutionary Computing and Metaheuristics, In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Springer, 427 (2013): 257-285.
• [34] Ustimenko V., Romańczuk U., On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, Artificial Intelligence, Evolutionary Computing and Metaheuristics, In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Springer, 427 (2013): 231-256.
• [35] Ustimenko V., Wróblewska A., On the key exchange with nonlinear polynomial maps of stable degree, Annalles UMCS Informatica AI XI, 2 (2011): 81-93.
• [36] Ustimenko V., Wróblewska A., Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography, Annales UMCS Informatica AI, ISSN 1732-1360.
• [37] Wróblewska A., On some properties of graph based public keys, Albanian Journal of Mathematics, NATO Advanced Studies Institute: "New challenges in digital communications", 2(3) (2008): 229-234.
• [38] Ustimenko V., Wróblewska A., On some algebraic aspects of data security in cloud computing, Proceedings of International conference "Applications of Computer Algebra", Malaga (2013): 144-147.
• [39] Ustimenko V., Wróblewska A., On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree, Annales UMCS Informatica AI XIII, 1 (2013): 63-80.