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

Asmaa Cherkaoui; Ramón Flores; Delaram Kahrobaei; Richard C. Wilson

Paper 2026/173

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

Asmaa Cherkaoui, University Hassan II, Casablanca, Morocco

Ramón Flores, University of Seville, Spain

Delaram Kahrobaei, City University of New York, USA, New York University, USA, University of York, United Kingdom

Richard C. Wilson, University of York, United Kingdom

Abstract

We propose Eidolon, a post-quantum signature scheme grounded in the NP-complete $k$-colorability problem. Our construction generalizes the Goldreich–Micali–Wigderson zero-knowledge protocol to arbitrary $k \geq 3$, applies the Fiat–Shamir transform, and uses Merkle-tree commitments to compress signatures from $O(tn)$ to $O(t \log n)$. We generate 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 \geq 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Proceedings of the International Workshop on the Arithmetic of Finite Fields (WAIFI 2026), Lecture Notes in Computer Science, Vol. 16611, Springer, 2026.
DOI: 10.1007/978-3-032-27574-5_3
Keywords: Post-quantum cryptography k-colorability zero-knowledge proofs Fiat–Shamir transform graph neural networks.
Contact author(s): esma1maysan @ gmail com
ramonjflores @ us es
delaram kahrobaei @ qc cuny edu
richard wilson @ york ac uk
History: 2026-05-31: last of 2 revisions; 2026-02-02: received; See all versions
Short URL: https://ia.cr/2026/173
License: CC BY

BibTeX

@misc{cryptoeprint:2026/173,
      author = {Asmaa Cherkaoui and Ramón Flores and Delaram Kahrobaei and Richard C. Wilson},
      title = {Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/173},
      year = {2026},
      doi = {10.1007/978-3-032-27574-5_3},
      url = {https://eprint.iacr.org/2026/173}
}