On the families of algebraic graphs with the fastest growth of cycle indicator and their applications

Vasyl Ustimenko

Paper 2022/1668

On the families of algebraic graphs with the fastest growth of cycle indicator and their applications

Vasyl Ustimenko

, Royal Holloway University of London

Abstract

Symbolic computations with the usage of bipartite algebraic graphs A(n, F_q) and A(n, F_q[x_1, x_2, ..., x_n]) were used for the development of various cryptographic algorithms because the length of their minimal cycle (the girth) tends to infinity when n is growing. It motivates studies of graphs A(n, K) defined over arbitrary integrity ring K. We show that the cycle indicator of A(n, K), i. e. maximal value of minimal cycles through the given vertex is >2n. We justify that the girth indicator of line [0,0,..., 0]A(n, K)$ is > 2n and the girth indicator of point (0,0, ..., 0) of this graph is at least 2n. From this result instantly follows that the girth of known edge transitive graphs D(n, K) defined over integrity ring K is at least 2[(n+5)]/2. We consider some inequalities defined in terms of a girth, a diameter and the girth indicator of homogeneous algebraic graphs and formulate some conjectures.

Note: This is corrected and expanded version of the previous manuscript.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: graphs with large girth indicator commutative integrity ring symbolic computations cryptosystems
Contact author(s): vasylustimenko @ yahoo pl
History: 2022-12-30: revised; 2022-11-30: received; See all versions
Short URL: https://ia.cr/2022/1668
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1668,
      author = {Vasyl Ustimenko},
      title = {On the families of algebraic graphs with the fastest growth of cycle indicator and their applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1668},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1668}
}