EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Jordan–Gauss Graphs and Twisted Diffie–Hellman Multivariate Protocols with Stable Generators of Prescribed Degree and Density

Vasyl Ustimenko, Tymoteusz Chojecki

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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