基于图着色难题构建抗量子签名，抵抗经典与神经网络攻击。
Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks
- 将零知识协议扩展至任意k≥3，用梅克尔树压缩签名
- 对n≥60的图，经典与神经网络攻击均无法破解
- 适合关注抗量子密码与图论应用的研究者
我们提出Eidolon，一种基于NP完全问题k-着色的抗量子签名方案。该构造将Goldreich-Micali-Wigderson零知识协议推广至任意k≥3的情况，结合Fiat-Shamir变换，并采用梅克尔树承诺将签名大小从O(tn)压缩至O(t log n)。通过植入特定着色方案生成困难实例，同时保持随机图的统计特性。针对经典求解器（ILP、DSatur）和自研图神经网络（GNN）攻击者进行了实证安全分析。实验表明，当n≥60时，两种方法均无法恢复与植入解匹配的有效着色，说明精心构造的k-着色实例能有效抵御所考虑的经典与基于学习的密码分析手段。这些结果表明，所构造实例在评估范围内具备抗攻击能力。
原文摘要 · Abstract (English)
We propose Eidolon, a post-quantum signature scheme grounded on the NP-complete k-colorability problem. Our construction generalizes the Goldreich-Micali-Wigderson zero-knowledge protocol to arbitrary k >= 3, applies the Fiat-Shamir transform, and uses Merkle-tree commitments to compress signatures from O(tn) to O(t log n). We generate hard instances by planting a coloring while aiming to preserve the statistical profile of random graphs. We present an empirical security analysis of such a scheme against both classical solvers (ILP, DSatur) and a custom graph neural network (GNN) attacker. Experiments show that for n >= 60, neither approach is able to recover a valid coloring matching the planted solution, suggesting that well-engineered k-coloring instances can resist the considered classical and learning-based cryptanalytic approaches. These experiments indicate that the constructed instances resist the attacks considered in our evaluation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。