Paper 2022/1668
On the families of algebraic graphs with the fastest growth of cycle indicator and their applications
, Royal Holloway University of LondonAbstract
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]$ of $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 indicatorcommutative integrity ringsymbolic computationscryptosystems
- 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}
}
