Eidolon: Post-Quantum Signature Based on k-Colorability
A novel post-quantum signature scheme named Eidolon has been introduced, based on the NP-complete k-colorability challenge. This construction extends the Goldreich-Micali-Wigderson zero-knowledge protocol to any k ≥ 3, incorporates the Fiat-Shamir transformation, and utilizes Merkle-tree commitments to reduce signature sizes from O(tn) to O(t log n). To generate difficult instances, a coloring is embedded while maintaining the statistical characteristics of random graphs. An empirical security evaluation against classical solvers (ILP, DSatur) and a specialized graph neural network (GNN) attacker indicates that for n ≥ 60, neither method succeeds in retrieving a valid coloring that corresponds to the planted solution, implying robustness against both classical and learning-based cryptanalytic techniques.
Key facts
- Eidolon is a post-quantum signature scheme based on k-colorability.
- It generalizes the Goldreich-Micali-Wigderson zero-knowledge protocol to k ≥ 3.
- Applies Fiat-Shamir transform and Merkle-tree commitments for signature compression.
- Compression reduces signature size from O(tn) to O(t log n).
- Hard instances are generated by planting a coloring while preserving random graph statistics.
- Security tested against ILP, DSatur, and a custom GNN attacker.
- For n ≥ 60, no attacker recovered a valid coloring.
- Scheme resists considered classical and learning-based attacks.
Entities
—