Learning the Word Problem: Geodesic Lengths and Cryptographic Applications

• URL: http://arxiv.org/abs/2607.26241v2
• Date: Tue, 04 Aug 2026 11:20:47 GMT
• Title: Learning the Word Problem: Geodesic Lengths and Cryptographic Applications
• Abstract summary: This paper introduces WPNet, a novel Graph Neural Network architecture capable of solving the Word Problemally.<n>WPNet is successfully deployed against the Wagner-Magyarik public-key cryptosystem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• GeoGNN: Quantifying and Mitigating Semantic Drift in Text-Attributed Graphs [59.61242815508687]
  Graph neural networks (GNNs) on text--attributed graphs (TAGs) encode node texts using pretrained language models (PLMs) and propagate these embeddings through linear neighborhood aggregation.<n>This work introduces a local PCA-based metric that measures the degree of semantic drift and provides the first quantitative framework to analyze how different aggregation mechanisms affect manifold structure.
  arXiv  Detail & Related papers  (2025-11-12T06:48:43Z)
• Nonlocal Games Through Communication Complexity and Quantum Cryptography [0.0]
  This thesis explores foundational aspects of quantum information theory and quantum cryptography.<n>We aim to distinguish quantum correlations from non-signaling correlations by leveraging the principle of communication complexity.<n>We aim to construct an encryption scheme that prevents two distant parties from simultaneously obtaining information about a shared message.
  arXiv  Detail & Related papers  (2025-10-10T15:07:24Z)
• ALICE: An Interpretable Neural Architecture for Generalization in Substitution Ciphers [0.3403377445166164]
  We present cryptogram solving as an ideal testbed for studying neural network reasoning and generalization.<n>We develop ALICE, a simple encoder-only Transformer that sets a new state-of-the-art for both accuracy and speed on this decryption problem.<n>Surprisingly, ALICE generalizes to unseen ciphers after training on only $sim1500$ unique ciphers.
  arXiv  Detail & Related papers  (2025-09-08T23:33:53Z)
• Singularity Cipher: A Topology-Driven Cryptographic Scheme Based on Visual Paradox and Klein Bottle Illusions [0.0]
  The Singularity Cipher integrates topological transformations and visual paradoxes to achieve multidimensional security.<n>The resulting binary data is encoded using perceptual illusions, such as the missing square paradox, to visually obscure the presence of encrypted content.<n>The paper formalizes the architecture, provides encryption and decryption algorithms, evaluates security properties, and compares the method against classical, post-quantum, and steganographic approaches.
  arXiv  Detail & Related papers  (2025-07-02T04:44:52Z)
• Towards Dynamic Message Passing on Graphs [104.06474765596687]
  We propose a novel dynamic message-passing mechanism for graph neural networks (GNNs)<n>It projects graph nodes and learnable pseudo nodes into a common space with measurable spatial relations between them.<n>With nodes moving in the space, their evolving relations facilitate flexible pathway construction for a dynamic message-passing process.
  arXiv  Detail & Related papers  (2024-10-31T07:20:40Z)
• On the use of dynamical systems in cryptography [0.0]
  This paper provides a new algorithm that can be used to attack -- and hence test the security of -- stream ciphers based on the iteration of a chaotic map of the interval. The second is to cast discrete dynamical systems problems in a modern cryptographic and complexity theoretic language, so that researchers working in chaos-based cryptography can begin designing cryptographic protocols.
  arXiv  Detail & Related papers  (2024-05-05T19:59:49Z)
• Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
  The segmentation ambiguity problem, which arises when using language models based on subwords, leads to occasional decoding failures.<n>We propose a novel secure disambiguation method named SyncPool, which effectively addresses the segmentation ambiguity problem.<n> SyncPool does not change the size of the candidate pool or the distribution of tokens and thus is applicable to provably secure language steganography methods.
  arXiv  Detail & Related papers  (2024-03-26T09:25:57Z)
• Applications of Finite non-Abelian Simple Groups to Cryptography in the Quantum Era [0.0]
  We review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central. We look at constructions based on various group-theoretic factorization problems, review group theoretical hash functions, and discuss fully homomorphic encryption using simple groups.
  arXiv  Detail & Related papers  (2023-08-28T17:30:00Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning [123.06420835072225]
  We construct a new large-scale benchmark, Geometry3K, consisting of 3,002 geometry problems with dense annotation in formal language. We propose a novel geometry solving approach with formal language and symbolic reasoning, called Interpretable Geometry Problem solver (Inter-GPS) Inter-GPS incorporates theorem knowledge as conditional rules and performs symbolic reasoning step by step.
  arXiv  Detail & Related papers  (2021-05-10T07:46:55Z)
• Decrypting Cryptic Crosswords: Semantically Complex Wordplay Puzzles as a Target for NLP [28.479149974110463]
  Cryptic crosswords, the dominant crossword variety in the UK, are a promising target for advancing NLP systems.<n>We present a dataset of cryptic clues as a challenging new benchmark for NLP systems.<n>We also introduce a challenging data split, examine the meta-linguistic capabilities of subword-tokenized models, and investigate model systematicity by perturbing the wordplay part of clues.
  arXiv  Detail & Related papers  (2021-04-17T18:54:00Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.