Pith Number

pith:R7INXMD4

pith:2026:R7INXMD4O7XGDOHPEKVZQLVLGI

not attested not anchored not stored refs pending

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

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.

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

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{R7INXMD4O7XGDOHPEKVZQLVLGI}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

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.

C2weakest assumption

That the planted-coloring instances preserve the statistical profile of random graphs sufficiently to inherit their hardness, and that the tested attackers (ILP, DSatur, and one custom GNN) adequately represent the best possible classical and learning-based attacks.

C3one line summary

Eidolon is a post-quantum signature scheme based on planted k-colorable graphs whose empirical tests show resistance to classical solvers and a custom GNN attacker for n >= 60.

Receipt and verification

First computed	2026-06-02T02:04:13.755701Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

8fd0dbb07c77ee61b8ef22ab982eab321563154bace47213a17c893865662d98

Aliases

arxiv: 2602.02689 · arxiv_version: 2602.02689v2 · doi: 10.48550/arxiv.2602.02689 · pith_short_12: R7INXMD4O7XG · pith_short_16: R7INXMD4O7XGDOHP · pith_short_8: R7INXMD4

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/R7INXMD4O7XGDOHPEKVZQLVLGI \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 8fd0dbb07c77ee61b8ef22ab982eab321563154bace47213a17c893865662d98

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "bc2a1bf347170f24f4562853fa24c42cdac85ec433f258afa83ccc19d0096dc3",
    "cross_cats_sorted": [
      "cs.AI",
      "cs.LG"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.CR",
    "submitted_at": "2026-02-02T19:05:50Z",
    "title_canon_sha256": "a292b74e559308e3dcd18e87bcd95a9bf1034fad1144d76923fa7486e623082d"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2602.02689",
    "kind": "arxiv",
    "version": 2
  }
}