Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks

Computer Science > Cryptography and Security [Submitted on 2 Feb 2026 (v1), last revised 24 Apr 2026 (this version, v2)] Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks Asmaa Cherkaoui, Ramon Flores, Delaram Kahrobaei, Richard Wilson 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. Comments: 20 pages, 4 figures Subjects: Cryptography and Security (cs.CR); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) MSC classes: 94A60, 05C15, 68R10 Cite as: arXiv:2602.02689 [cs.CR]   (or arXiv:2602.02689v2 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2602.02689 Focus to learn more Submission history From: Asmaa Cherkaoui [view email] [v1] Mon, 2 Feb 2026 19:05:50 UTC (728 KB) [v2] Fri, 24 Apr 2026 12:26:54 UTC (452 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-02 Change to browse by: cs cs.AI cs.LG References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)