Paper 2024/1156

On affine forestry over integral domains and families of deep Jordan-Gauss graphs

Tymoteusz Chojecki, Maria Curie-Sklodowska University, Lublin, Poland
Grahame Erskine, Open University, Milton Keynes, UK
James Tuite, Open University, Milton Keynes, UK
Vasyl Ustimenko, Royal Holloway, University of London, UK
Abstract

Let K be a commutative ring. We refer to a connected bipartite graph G = G_n(K) with partition sets P = K^n (points) and L = K^n (lines) as an affine graph over K of dimension dim(G) = n if the neighbourhood of each vertex is isomorphic to K. We refer to G as an algebraic affine graph over K if the incidence between a point (x_1, x_2, . . . , x_n) and line [y_1, y_2, . . . , y_n] is defined via a system of polynomial equations of the kind f_i = 0 where f_i ∈ K[x_1, x_2, . . . , x_n, y_1, y_2, . . . , y_n]. We say that an affine algebraic graph is a Jordan-Gauss graph over K if the incidences between points and lines are given by a quadratic system of polynomial equations, and the neighbourhood of each vertex is given as a solution set of the system of linear equations in row-echelon form. For each integral domain K we consider the known explicit construction of the family of Jordan-Gauss graphs A(n, K), n = 2, 3, . . . with cycle indicator ≥ 2n + 2. Additionally several constructions of families of edge intransitive Jordan-Gauss graphs over K of increasing girth with well defined projective limit will be presented. This projective limit is a forest defined by the system of algebraic equations. In the case K = F_q, q ≥ 3 we present results of computer experiments for the evaluation of girth, cycle indicator, diameter and the second largest eigenvalue of the constructed graphs, and we formulate several conjectures on their properties. One of the conjectures is that the girth of A(n, F_q) is 2[(n+ 5)/2]. We discuss briefly some applications of Jordan-Gauss graphs of large girth to Graph Theory, Algebraic Geometry and the theory of LDPC codes; and we consider ideas to use groups related to these graphs in Noncommutative Cryptography and Stream Ciphers Design.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
algebraic graphs of large girthgraph based cryptographyNoncommutative Cryptographystream ciphersLDPC codes
Contact author(s)
chojecki tymoteusz @ gmail com
grahame erskine @ open ac uk
james t tuite @ open ac uk
Vasyl Ustymenko @ rhul ac uk
History
2024-11-27: revised
2024-07-16: received
See all versions
Short URL
https://ia.cr/2024/1156
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1156,
      author = {Tymoteusz Chojecki and Grahame Erskine and James Tuite and Vasyl Ustimenko},
      title = {On affine forestry over integral domains and families of deep Jordan-Gauss graphs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1156},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1156}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.