Eidolon: A Practical Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks
This work addresses the need for quantum-resistant cryptography by reviving combinatorial hardness for post-quantum signatures, though it is incremental as it builds on existing protocols.
The authors tackled the problem of creating a practical post-quantum signature scheme by proposing Eidolon, based on the k-colorability problem, which resists both classical solvers and a custom graph neural network attacker for n >= 60, with signatures compressed from O(tn) to O(t log n).
We propose Eidolon, a practical post-quantum signature scheme based 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). Crucially, we generate hard instances via planted "quiet" colorings that preserve the statistical profile of random graphs. We present the first 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 recovers the secret coloring, demonstrating that well-engineered k-coloring instances can resist modern cryptanalysis, including machine learning. This revives combinatorial hardness as a credible foundation for post-quantum signatures.