EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Quadratic Equations of the q-Regular Tree and Their Applications in Graph Theory and Cryptography

Vasyl Ustimenko, Tymoteusz Chojecki

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →