Jordan–Gauss Graphs and Twisted Diffie–Hellman Multivariate Protocols with Stable Generators of Prescribed Degree and Density
Algorithms · 08.11.2026 · 19 (11) · 974
DOI: 10.3390/a19110974 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 08.11.2026. Verfasst von Vasyl Ustimenko und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
A well-known family of algebraic graphs of large girth, D(n,q), has previously been used to implement twisted Diffie–Hellman protocols based on graph-derived stable cubic generators from the affine Cremona semigroup End(Fq[x1,x2,…,xn]). This approach enables Alice and Bob to compute a shared collision tuple in (Fq)n3 in O(n5) time, rather than explicitly constructing the corresponding collision transformation. In this paper, we develop new implementations of twisted Diffie–Hellman protocols, as well as their inverse variants, using families of Jordan–Gauss graphs and stable generators of the corresponding affine Cremona semigroups. We show that Double Schubert graphs DS(k,K), defined over a finite commutative ring K, can be used to construct stable generators of End(K[x1,x2,…,xk(k+1)]) with prescribed degree d and density O(nβ), where n=k(k+1). Sparse elements of AGLn(K) are then used to conjugate these graph-based stable transformations, enabling the communicating parties to efficiently derive shared collision tuples in Knd. We further show that other K-analogues of Jordan–Gauss subgraphs of projective geometry can be used in place of Double Schubert graphs to implement both twisted Diffie–Hellman protocols
Zitieren
APA
Ustimenko, V., & Chojecki, T. (2026). Jordan–Gauss Graphs and Twisted Diffie–Hellman Multivariate Protocols with Stable Generators of Prescribed Degree and Density. Algorithms, 19(11), 974. https://doi.org/10.3390/a19110974
Vancouver
Ustimenko V, Chojecki T. Jordan–Gauss Graphs and Twisted Diffie–Hellman Multivariate Protocols with Stable Generators of Prescribed Degree and Density. Algorithms. 2026;19(11):974. doi:10.3390/a19110974
BibTeX
@article{Ustimenko2026,
author = {Ustimenko, Vasyl and Chojecki, Tymoteusz},
title = {Jordan–Gauss Graphs and Twisted Diffie–Hellman Multivariate Protocols with Stable Generators of Prescribed Degree and Density},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {11},
pages = {974},
doi = {10.3390/a19110974}
}
EUVIMED