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

Asmaa Cherkaoui; Delaram Kahrobaei; Ramon Flores; Richard Wilson

arxiv: 2602.02689 · v2 · submitted 2026-02-02 · 💻 cs.CR · cs.AI· cs.LG

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

Asmaa Cherkaoui , Ramon Flores , Delaram Kahrobaei , Richard Wilson This is my paper

Pith reviewed 2026-05-16 07:59 UTC · model grok-4.3

classification 💻 cs.CR cs.AIcs.LG

keywords post-quantum signaturesk-colorabilitygraph neural networksFiat-Shamir transformzero-knowledge proofsplanted problemsMerkle treesdigital signatures

0 comments

The pith

Eidolon turns the NP-complete k-colorability problem into a post-quantum signature scheme whose planted instances resist tested classical solvers and graph neural networks for graphs of size 60 and larger.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces Eidolon, a digital signature scheme whose security rests on the NP-complete k-colorability problem. It generalizes an existing zero-knowledge protocol to handle any number of colors at least three, applies the Fiat-Shamir transform to make it non-interactive, and uses Merkle trees to reduce signature size. Hard instances are produced by planting a secret coloring into a graph while preserving the statistical properties of a random graph. Experiments with integer linear programming, the DSatur heuristic, and a custom graph neural network show that none can recover the planted coloring once the graph has sixty or more vertices. This suggests that carefully constructed instances may remain hard against both traditional and machine-learning-based cryptanalysis.

Core claim

Eidolon is a signature scheme obtained by applying the Fiat-Shamir transform to a generalized Goldreich-Micali-Wigderson protocol for k-colorability and compressing the resulting proofs with Merkle trees. Its security relies on the difficulty of recovering a planted k-coloring from graphs that are statistically close to random graphs. Empirical tests indicate that for graphs with at least 60 vertices, neither integer linear programming solvers, the DSatur coloring heuristic, nor a custom graph neural network can extract the planted coloring.

What carries the argument

The planted k-coloring generator that embeds a valid coloring while matching the edge-density profile of a random graph, together with the Fiat-Shamir transform applied to the generalized zero-knowledge protocol for k-colorability.

If this is right

Signatures compress from linear in the number of vertices to logarithmic using Merkle trees.
The scheme works for any number of colors k at least 3.
Security holds against the tested classical and learning-based attacks when the number of vertices reaches 60 or more.
The construction supplies a concrete post-quantum signature alternative based on a graph coloring problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the planted instances truly inherit random-graph hardness, similar techniques could extend to other NP-complete graph problems for building signatures.
Stronger attackers such as more advanced graph neural network architectures or future quantum algorithms might still break the instances.
Further theoretical analysis could prove that the planted distributions remain computationally indistinguishable from random graphs for the purpose of coloring recovery.

Load-bearing premise

The planted-coloring instances preserve the statistical profile of random graphs sufficiently to inherit their hardness, and that the tested attackers adequately represent the best possible classical and learning-based attacks.

What would settle it

An experiment in which an improved solver or neural network recovers the planted coloring for a significant fraction of graphs with 60 or more vertices would show that the instances do not resist the considered attacks.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Eidolon gives a concrete construction for a k-coloring signature with some experimental data against solvers and a GNN, but security rests on unproven assumptions about planted instances rather than a reduction.

read the letter

The main contribution is a signature scheme that generalizes the Goldreich-Micali-Wigderson zero-knowledge protocol from 3-coloring to arbitrary k, applies Fiat-Shamir, and uses Merkle trees to cut signature size from linear in n to logarithmic. They also describe a planting method to create instances that try to match the edge statistics of random graphs while embedding a known coloring. The experiments test these instances against integer linear programming, the DSatur heuristic, and one custom graph neural network, reporting that none recover the planted solution once n reaches 60 or higher. That supplies a usable data point on resistance to the specific attacks they considered. The work is clear about its engineering choices and reports the attack results in enough detail to be checked by others. The soft spot is the security claim. The paper treats the planted instances as hard because the tested solvers and the GNN fail, yet it gives no reduction showing that an efficient attack on the planted distribution would break random k-coloring, and it reports no checks on higher-order statistics that might reveal the planting. The attacker set is narrow, so the results are suggestive for those particular methods but do not yet establish cryptographic hardness. This paper is for cryptographers who want to see an NP-hard graph problem turned into a signature with some concrete attack data, and for people studying learning-based cryptanalysis. A reader who follows post-quantum signature design or graph-based crypto would get value from the construction details and the reported numbers. It shows honest engagement with the literature and ships a complete scheme plus experiments, so it deserves peer review even if the formal side needs strengthening. I would bring it to a reading group to talk through the planting procedure and whether the GNN is representative. I would not cite it in my own work until a reduction or broader attack analysis appears. Send it to referees rather than desk-reject.

Referee Report

3 major / 2 minor

Summary. The manuscript proposes Eidolon, a post-quantum signature scheme whose security rests on the NP-complete k-colorability problem for k ≥ 3. It generalizes the Goldreich-Micali-Wigderson zero-knowledge protocol, applies the Fiat-Shamir transform, and uses Merkle-tree commitments to reduce signature size to O(t log n). Hard instances are generated by planting a valid coloring while attempting to preserve the edge statistics of random graphs. The central empirical claim is that for n ≥ 60 these instances resist recovery of the planted coloring by ILP solvers, the DSatur heuristic, and one custom graph neural network.

Significance. If the planted instances can be shown to be hard against a representative class of attacks, the construction would supply a new candidate post-quantum signature primitive based on a classical NP-complete graph problem. The timely inclusion of a GNN-based cryptanalytic evaluation and the Merkle-tree compression technique are engineering contributions that could be useful even if the hardness claim requires further substantiation.

major comments (3)

[Security analysis] Security analysis section: the claim that instances with n ≥ 60 resist the considered attacks rests exclusively on experiments with ILP, DSatur, and a single custom GNN. No justification is supplied for why this attacker set is representative of the best classical or learning-based attacks, nor is any reduction given showing that an efficient attack on the planted distribution would imply an attack on uniform random k-colorable graphs.
[Instance generation] Instance generation procedure: the planting method is asserted to preserve the statistical profile of random graphs, yet no quantitative verification (eigenvalue spectra, small-subgraph counts, degree-sequence correlations, or higher-order moments) is reported. Without such checks, detectable biases introduced by planting remain possible and could be exploited by stronger future attacks.
[Security model] Security model: the Fiat-Shamir transform is applied to the generalized GMW protocol, but the manuscript contains no formal reduction or proof (in the random-oracle or standard model) that breaking the signature scheme is computationally equivalent to recovering a planted coloring. The post-quantum security claim therefore depends entirely on the unproven empirical hardness.

minor comments (2)

[Abstract] Abstract: the final sentence repeats the preceding claim about resistance to the considered attacks; a single concise statement would suffice.
[Preliminaries] Notation: the roles of the free parameters k and t in the signature-size expression O(t log n) are introduced but not defined with explicit bounds or dependencies in the preliminaries.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for their thorough and constructive review of our manuscript. We address each major comment point by point below, indicating planned revisions where the manuscript can be strengthened while remaining honest about its empirical focus.

read point-by-point responses

Referee: [Security analysis] Security analysis section: the claim that instances with n ≥ 60 resist the considered attacks rests exclusively on experiments with ILP, DSatur, and a single custom GNN. No justification is supplied for why this attacker set is representative of the best classical or learning-based attacks, nor is any reduction given showing that an efficient attack on the planted distribution would imply an attack on uniform random k-colorable graphs.

Authors: We acknowledge that the evaluated attackers (ILP for exact solving, DSatur for heuristics, and the custom GNN for learning-based methods) do not constitute a comprehensive or formally justified set of all possible attacks. In revision we will expand the security analysis to explain the rationale for these choices in the context of the paper's title and focus on graph neural networks, while explicitly stating that the results are empirical and do not claim exhaustiveness. We do not provide a reduction relating attacks on the planted distribution to the uniform random case, as no such reduction appears in the manuscript. revision: partial
Referee: [Instance generation] Instance generation procedure: the planting method is asserted to preserve the statistical profile of random graphs, yet no quantitative verification (eigenvalue spectra, small-subgraph counts, degree-sequence correlations, or higher-order moments) is reported. Without such checks, detectable biases introduced by planting remain possible and could be exploited by stronger future attacks.

Authors: We agree that the absence of quantitative statistical verification is a gap. The revised manuscript will add explicit comparisons, including degree-sequence distributions, adjacency-matrix eigenvalue spectra, clustering coefficients, and counts of small subgraphs such as triangles and 4-cycles, between the planted instances and uniformly random graphs of the same density. revision: yes
Referee: [Security model] Security model: the Fiat-Shamir transform is applied to the generalized GMW protocol, but the manuscript contains no formal reduction or proof (in the random-oracle or standard model) that breaking the signature scheme is computationally equivalent to recovering a planted coloring. The post-quantum security claim therefore depends entirely on the unproven empirical hardness.

Authors: The construction applies the Fiat-Shamir transform to the generalized interactive zero-knowledge protocol in the standard heuristic manner, but the manuscript provides no formal security reduction or proof in either the random-oracle or standard model. The post-quantum security argument rests on the empirical resistance of the planted instances. We will revise the relevant section to state this limitation explicitly and describe the security as heuristic and empirically supported rather than formally proven. revision: yes

standing simulated objections not resolved

No formal reduction is supplied relating attacks on the planted distribution to attacks on uniform random k-colorable graphs or establishing computational equivalence between breaking the signature scheme and recovering a planted coloring.

Circularity Check

0 steps flagged

No circularity detected; security rests on external empirical testing

full rationale

The paper constructs a signature scheme by generalizing the Goldreich-Micali-Wigderson ZK protocol for k-colorability, applying Fiat-Shamir, and compressing with Merkle trees. Instance generation plants a valid coloring while targeting random-graph statistics, followed by direct empirical evaluation against ILP, DSatur, and a custom GNN. No equations or claims reduce to their own inputs by construction, no parameters are fitted then relabeled as predictions, and no load-bearing self-citations close a loop. The central hardness assertion is supported by reported experimental outcomes on planted instances rather than by self-referential definitions or imported uniqueness theorems.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The central claim rests on the NP-completeness of k-colorability, the security of the Fiat-Shamir transform in the random-oracle model, and the unproven assumption that planted instances remain hard while statistically resembling random graphs.

free parameters (2)

k
Number of colors chosen >=3; directly affects both hardness and protocol generalization.
t
Number of protocol repetitions; controls soundness error and signature size but is not derived from first principles.

axioms (2)

standard math k-colorability is NP-complete for fixed k >= 3
Invoked as the source of computational hardness for the signature scheme.
domain assumption Fiat-Shamir transform yields a secure signature scheme in the random-oracle model
Used to convert the interactive zero-knowledge protocol into a non-interactive signature.

pith-pipeline@v0.9.0 · 5474 in / 1589 out tokens · 37719 ms · 2026-05-16T07:59:28.739080+00:00 · methodology

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

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)