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

arXiv: https://arxiv.org/abs/2602.02689 · HTML: https://mlsanity.com/paper/2602.02689/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 30 references that are in the map.
- First posted on arXiv 2 Feb 2026.

## Builds on (most cited first, 6 of 6)

- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Solving the Conjugacy Decision Problem via Machine Learning](https://mlsanity.com/paper/1705.10417/) (2017)
- [New Integer Linear Programming Models for the Vertex Coloring Problem](https://mlsanity.com/paper/1706.10191/) (2017)
- [Group-based Cryptography in the Quantum Era](https://mlsanity.com/paper/2202.05917/) (2022)
- [A Customized SAT-based Solver for Graph Coloring](https://mlsanity.com/paper/2504.04821/) (2025)

## Abstract (arXiv)

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.