On the extremal graph theory for directed graphs and its cryptographical applications
2007; World Scientific; Linguagem: Inglês
10.1142/9789812772022_0012
ISSN1793-2238
Autores Tópico(s)Coding theory and cryptography
ResumoSeries on Coding Theory and CryptologyAdvances in Coding Theory and Cryptography, pp. 181-199 (2007) No AccessOn the extremal graph theory for directed graphs and its cryptographical applicationsV. A. UstimenkoV. A. UstimenkoUniversity of Maria Curie-Sklodowska, Lublin, Polandhttps://doi.org/10.1142/9789812772022_0012Cited by:12 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: The paper is devoted to the graph based cryptography. The girth of a directed graph (girth indicator) is defined via its smallest commutative diagram. The analogue of Erdøos's Even Circuit Theorem for directed graphs allows to establish upper bound on the size of directed graphs with a fixed girth indicator. Size of members of infinite family of directed regular graphs of high girth is close to an upper bound. Finite automata related to members of such a family of algebraic graphs over chosen commutative ring can be used effectively for the design of cryptographical algorithm for different problems of data security (stream ciphers, data base encryption, public key mode an digital signatures). The explicit construction of infinite family of algebraic graphs of high girth defined over the arbitrarily chosen ring is given. Some results on their properties, based on theoretical studies or software implementations are given. Keywords: Extremal graph theorydirected graphs of large girthalgebraic graphs over commutative ringsgraph based cryptographycoding theory FiguresReferencesRelatedDetailsCited By 12A Survey on some Applications of Graph Theory in CryptographyP.L.K. Priyadarsini2 June 2015 | Journal of Discrete Mathematical Sciences and Cryptography, Vol. 18, No. 3On walks of variable length in the Schubert incidence systems and multivariate flow ciphersV.A. Ustimenko15 August 2016 | Reports of the National Academy of Sciences of Ukraine, Vol. 25, No. 3On Multivariate Cryptosystems Based on Polynomially Compressed Maps with Invertible DecompositionUrszula Romańczuk-Polubiec and Vasyl Ustimenko1 Jan 2014On Dynamical Systems of Large Girth or Cycle Indicator and Their Applications to Multivariate CryptographyVasyl Ustimenko and Urszula Romańczuk1 Jan 2013On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption MachinesVasyl Ustimenko and Urszula Romańczuk1 Jan 2013On Families of Graphs of Large Cycle Indicator, Matrices of Large Order and Key Exchange Protocols With Nonlinear Polynomial Maps of Small DegreeUrszula Romańczuk and Vasyl Ustimenko22 July 2012 | Mathematics in Computer Science, Vol. 6, No. 2On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle IndicatorMichał Klisowski and Vasyl Ustimenko22 July 2012 | Mathematics in Computer Science, Vol. 6, No. 2On the key expansion of D(n, K)-based cryptographical algorithmVasyl Ustimenko and Aneta Wróblewska1 Jan 2011 | Annales UMCS, Informatica, Vol. 11, No. 2On the key exchange with new cubical maps based on graphsUrszula Romańczuk and Vasyl Ustimenko1 Jan 2011 | Annales UMCS, Informatica, Vol. 11, No. 4On the implementation of public keys algorithms based on algebraic graphs over finite commutative ringsMichal Klisowski and Vasyl Ustimenko1 Oct 2010On the hidden discrete logarithm for some polynomial stream ciphersVasyl Ustimenko1 Oct 2008On Small World Semiplanes with Generalised Schubert CellsVyacheslav Futorny and Vasyl Ustimenko6 June 2007 | Acta Applicandae Mathematicae, Vol. 98, No. 1 Advances in Coding Theory and CryptographyMetrics History KeywordsExtremal graph theorydirected graphs of large girthalgebraic graphs over commutative ringsgraph based cryptographycoding theoryPDF download
Referência(s)