用图神经网络破解群论中的词问题，威胁后量子密码安全
Learning the Word Problem: Geodesic Lengths and Cryptographic Applications
- 将未约化词映射为动态图，通过连续嵌入空间识别最短等价词
- 在BS(1,2)和阿廷群上准确预测词的测地长度，精度超95%
- 成功攻击威格纳-马加里克公钥密码系统，揭示结构漏洞
词问题自一个多世纪以来一直是数学研究的重点，最初推动了组合群论的发展，近年来更成为后量子密码学（PQC）的基础难解假设。尽管通常不可判定，但某些无限非交换群族具有可解或算法快速的词问题，使其成为密码设计的理想平台。本文提出WPNet，一种新型图神经网络架构，可启发式求解词问题，在Baumslag-Solitar群$BS(1,2)$和阿廷群上得到验证。通过将未约化词映射为动态图结构，模型学习在连续嵌入空间中聚类代数等价元素，有效识别词的测地代表元，而无需执行离散约化步骤。作为应用，模型变体可预测两种群中未约化词的测地长度。为展示这种结构泄漏的密码学严重性，WPNet成功部署于威格纳-马加里克公钥密码系统，实现有效攻击。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。