On Quadratic Equations of the q-Regular Tree and Their Applications in Graph Theory and Cryptography
Mathematics · 10.07.2026 · 14 (14) · 2490
DOI: 10.3390/math14142490 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 10.07.2026. Verfasst von Vasyl Ustimenko und 1 weiteren Autor:innen. Die Arbeit nennt 99 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Center.
Abstract (Originalsprache)
Graphs D(n,q) and their connected components CD(n,q) were defined 30 years ago. We briefly review their applications to Extremal Graph Theory, Spectral Graph Theory, Algebraic Graph Theory, Symmetric Cryptography, and Theory of Low Density Parity Check Codes. We introduce several new algorithms of Noncommutative Cryptography based on these graphs of large girth. In particular we propose a modification of the Diffie–Hellman protocol in terms of the semigroup of walks of even length on the forest obtained as the projective limit of D(n,q) and the homomorphic image of this monoid, acting on the vector space (Fq)n as the transformation group G(n,q) of cubic polynomial transformations. The protocol allows users to compute a collision vector from (Fq)n in time O(n2). The security of these schemes rests on the complexity of the Conjugacy Power Problem for the affine Cremona semigroup of automorphisms of Fq[x1,x2,…,xn]. An inverse protocol of El Gamal type allows one to use this scheme for encryption or the creation of digital signatures. Several obfuscations of these algorithms are given.
Förderung
- National Science Center
Zitieren
APA
Ustimenko, V., & Chojecki, T. (2026). On Quadratic Equations of the q-Regular Tree and Their Applications in Graph Theory and Cryptography. Mathematics, 14(14), 2490. https://doi.org/10.3390/math14142490
Vancouver
Ustimenko V, Chojecki T. On Quadratic Equations of the q-Regular Tree and Their Applications in Graph Theory and Cryptography. Mathematics. 2026;14(14):2490. doi:10.3390/math14142490
BibTeX
@article{Ustimenko2026,
author = {Ustimenko, Vasyl and Chojecki, Tymoteusz},
title = {On Quadratic Equations of the q-Regular Tree and Their Applications in Graph Theory and Cryptography},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {14},
pages = {2490},
doi = {10.3390/math14142490}
}
EUVIMED