Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914621201317888 |
|---|---|
| author | Cherkaoui, Asmaa Flores, Ramon Kahrobaei, Delaram Wilson, Richard |
| author_facet | Cherkaoui, Asmaa Flores, Ramon Kahrobaei, Delaram Wilson, Richard |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_02689 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks Cherkaoui, Asmaa Flores, Ramon Kahrobaei, Delaram Wilson, Richard Cryptography and Security Artificial Intelligence Machine Learning 94A60, 05C15, 68R10 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. |
| title | Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks |
| topic | Cryptography and Security Artificial Intelligence Machine Learning 94A60, 05C15, 68R10 |
| url | https://arxiv.org/abs/2602.02689 |