Learning the Word Problem: Geodesic Lengths and Cryptographic Applications

arXiv:2607.26241 · cs.CR, cs.LG, math.GR · Submitted 2026-07-28 · Read on arXiv

Elisabeth Fink

cs.CR, cs.LG, math.GR

Submitted: 2026-07-28

Comments: 21 pages, 3 figures, 4 tables

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: The Word Problem has been a subject of intensive mathematical study for over a century, initially driving advances in combinatorial group theory and more recently emerging as a foundational hardness

Terminology

Abstract

The Word Problem has been a subject of intensive mathematical study for over a century, initially driving advances in combinatorial group theory and more recently emerging as a foundational hardness assumption in post-quantum cryptography (PQC). While generally undecidable, several families of infinite non-abelian groups exhibit solvable or algorithmically fast word problems, making them attractive platforms for cryptographic design. This paper introduces WPNet, a novel Graph Neural Network architecture capable of solving the Word Problem heuristically, which is demonstrated on the Baumslag-Solitar group BS(1,2) and on an Artin group. By mapping unreduced words to dynamic graph structures, the model learns to cluster algebraically equivalent elements in a continuous embedding space, effectively identifying the geodesic representative of a word without executing discrete reduction steps. As an application, a model variant is developed that can predict the geodesic length of an unreduced word in both groups. To demonstrate the cryptographic severity of this structural leakage, WPNet is successfully deployed against the Wagner-Magyarik public-key cryptosystem.

Sources

Related papers