ERC-8373: Post-Quantum Anchored Key-Binding

Abstract

This ERC specifies a migration path for the signature layer of on-chain and agent identity to post-quantum (PQ) cryptography. A binding statement — a content-addressed, canonically-serialized declaration that a classical key is bound to a PQ key — is anchored to a public timestamped substrate before any cryptanalytic break. Consumers enforce a cutoff: an artifact proven anchored before the cutoff verifies classical-only (the back catalog is never retroactively invalidated); an artifact anchored at or after the cutoff MUST carry a valid PQ companion signature under the binding in force at that artifact's anchor time, or be rejected.

The central design decision is that this is a binding plus cutoff, not a second signature. A supplementary PQ signature is opt-in from the forger's perspective: an attacker who derives the classical key simply omits it, and the omission is indistinguishable from honest pre-migration history. Under this ERC, post-cutoff omission fails closed. When the anchor is an Ethereum transaction sent from the classical address, the anchoring transaction itself is the classical proof-of-possession — one irreversible, timestamped, recomputable fact instead of a second signature to forge around. Every element is re-derivable from public data by any third party.

Motivation

Shor's algorithm breaks the ECDSA and Schnorr signatures underlying Ethereum accounts, most of Web3, and most AI-agent attestation identity. Hash functions survive (Grover's algorithm only halves effective security; 256-bit hashes remain safe). The risk to signature-based identity is prospective forgery, not retroactive decryption: nothing already anchored on-chain is at risk, because a future key-forger cannot backdate into an existing anchor. What breaks is the ability to trust new signatures after a cryptographically-relevant quantum computer exists.

The common proposal — "attach a PQ signature alongside the classical one" — does not close the hole, for a structural reason: verification of the extra signature is opt-in, and a forger opts out. Security must instead live in a pre-published binding and a consumer-enforced cutoff, so that the absence of a valid PQ companion after the cutoff is itself a rejection.

Identity standards in the agent family (ERC-8004 registries, attestation and verification ERCs) all rest on signature-based identity and inherit this exposure. This ERC provides the migration primitive they can share.

Specification

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 and RFC 8174.

Definitions

• Classical key — a secp256k1 key (ECDSA or BIP-340 Schnorr) controlling an identity.
• PQ key — a key under a NIST-finalized post-quantum signature standard: ML-DSA (FIPS 204) or SLH-DSA (FIPS 205).
• Binding statement — the canonical JSON object declaring classical→PQ key binding (below).
• Content-address — sha256(JCS(statement)), where JCS is RFC 8785 JSON Canonicalization (sorted keys, compact separators, literal non-ASCII UTF-8).
• Anchor — publication of a content-address to a public, timestamped, append-only substrate. Anchor time is the substrate's timestamp for that publication (e.g. the Ethereum block timestamp of the anchoring transaction).
• Companion — a detached PQ signature over an artifact's 32-byte content-address.
• Cutoff — a consumer-chosen instant after which classical-only artifacts are rejected.
• In-force binding — the binding governing an artifact, resolved from the anchored binding chain at the artifact's anchor time.

Binding statement

A binding statement is a JSON object. The following members are REQUIRED:

A bound_at timestamp and a profile tag are RECOMMENDED; the profile is the cutoff-enforcement profile identifier (e.g. pq_key_binding.v1) and is the version identifier that governs enforcement — not the namespaced schema. algorithm is a field, not a fork: implementations under different NIST families MUST converge on the same content-address rules through canonicalization alone.

The canonical form is JCS(statement); the binding's identity is content_address = sha256(JCS(statement)). Verifiers MUST recompute the content-address from raw bytes; any key manifest or hosted copy is discovery only, never authority.

Anchoring and proof-of-possession

The binding's content-address MUST be anchored before it is relied upon. When the anchor substrate is an Ethereum transaction (e.g. recording the digest via an anchoring contract), the transaction MUST be sent from the classical address being bound. The anchoring transaction then constitutes the classical proof-of-possession: no separate classical signature over the statement is required, and none should be trusted in its place.

The genesis binding MUST additionally be signed by the PQ key over its own content-address (proof of possession of the PQ key; neither key alone can claim the other).

Anchor availability: an anchor is only a cutoff for a verifier who can fetch it. An on-chain anchor is permissionlessly readable. An implementation using an off-chain timestamp proof MUST serve the proof bytes publicly; an unreachable proof collapses the cutoff to holder-only verification and does not satisfy this ERC.

Companion signatures

A PQ companion is a detached signature over the primary artifact's existing 32-byte content-address (for example, a Nostr event id or an attestation digest) — never an in-object tag. An in-object tag lives inside the id preimage, so retrofitting it re-mints the id and orphans every existing anchor; the detached companion signs the identifier everyone already computes, identically for past and future artifacts.

The cutoff rule

A consumer MUST accept an artifact if and only if:

1. the artifact is proven anchored before the consumer's cutoff (classical-only verification suffices; the back catalog is owed nothing further), or
2. the artifact carries a valid PQ companion under the in-force binding at the artifact's anchor time.

All authority judgments use anchor time, never claimed signature time: a compromised key can backdate a signature; it cannot backdate an anchor. A valid companion under a key that is not the in-force key for that anchor time MUST NOT count. The cutoff is consumer-side policy, not issuer-declared.

The schema member is implementation-namespaced and opaque to cutoff enforcement: an enforcer MUST NOT condition its verdict on schema. Enforcement keys only on anchored times, the content-address, and pq_pubkey; the cutoff profile is the only version identifier that governs. A binding under any namespace — kya.pq_key_binding.v0, a production deployment's own namespace, or one unknown to the verifier — yields the same verdict as the equivalent known-namespace binding. The conformance suite's namespace opacity case is the failing witness: an enforcer that pattern-matches the namespace reds exactly that case.

Rotation, revocation, and in-force resolution

Bindings form an anchored chain. The in-force binding for an artifact is resolved deterministically from the chain at the artifact's anchor time. Resolution MUST run from the chain even at length one.

• Rotation — a new binding statement that links its predecessor (predecessor_content_address) and is dual-signed over its own content-address by the predecessor PQ key (continuity: the retiring key authorizes its successor, so the chain survives a classical break) and the new PQ key (possession). Rotation is forward-acting: artifacts anchored before the rotation continue to resolve to the predecessor.
• Revocation — an anchored revocation record ends a binding's authority at the revocation's anchor time, never retroactively and never at a self-declared time. Artifacts anchored at or after that time are no longer governed by the revoked binding; artifacts anchored earlier remain valid.
• Terminality — a terminal statement is a standing, fail-closed constraint on the future binding path, not a description of present absence. Two intents MUST be distinguished: a deliberate retirement is absolute; a defensive incident-kill is liftable only by a fleet-level seed-rotation path, never by a per-agent path — otherwise the compromised key could resurrect itself.

In-force states. With B the activation anchor of the governing binding and R its revocation anchor (R ≥ B, when a revocation exists), an artifact's anchor time t resolves to exactly one state:

• pre_baseline (t < B) — anchored before any binding governed it; admitted classical-only under the cutoff rule (the innocent back catalog).
• in_force (B ≤ t < R) — governed by the binding; a post-cutoff artifact MUST carry a valid PQ companion under it.
• authority_revoked (t ≥ R, with no separately anchored successor in force) — the binding's authority has ended; the artifact MUST be rejected, even pre-cutoff.

These states are mutually exclusive by construction. The in_force interval is half-open: activation is inclusive, revocation exclusive. The revocation boundary is correspondingly inclusive on the revoked side — an artifact anchored at exactly t == R is authority_revoked, never still in_force. Successor existence and eligibility are separate resolution facts, not a fourth state: an artifact at t ≥ R for which a valid successor was separately anchored resolves to that successor's binding rather than to authority_revoked. A conformant enforcer MUST NOT collapse pre_baseline and authority_revoked into one reason — they are opposite answers (an innocent back catalog versus deliberately ended authority), and their names MUST NOT share a prefix that would invite a later startsWith check to re-conflate them.

Recovery classes

Authority transitions MUST be classified by anchored, falsifiable class declarations (e.g. rotation, revocation, terminal), and each record MUST be judged only against its declared class: a record failing its own class predicate is rejected, never silently relabeled as a neighboring class. This keeps every transition independently auditable by a third party.

The single permitted non-public-recompute step is fleet seed-recovery: replacement keys derive from a secret seed, so a third party cannot re-derive them. The public guarantee for that step is (a) the anchoring transaction is sent by the designated recovery authority (which MUST NOT reduce to the key being replaced) and (b) an anchored commitment (e.g. Merkle root) over the new keys. Implementations MUST state this boundary explicitly rather than imply the recovery is publicly recomputable. A zero-knowledge proof of correct derivation MAY replace operator attestation in future versions.

Verification procedure

A verifier, given an artifact and a consumer cutoff:

1. Recompute the artifact's content-address from raw bytes.
2. Recover the artifact's anchor time from the anchor substrate.
3. If anchor time < cutoff and no revocation ended a governing binding's authority at or before that anchor time: verify classically; accept. (A revocation is the one signal that reaches back across the cutoff — see Rotation, revocation, and in-force resolution.)
4. Otherwise: resolve the in-force binding at the artifact's anchor time from the anchored binding chain (applying rotations, revocations, terminality); recompute the binding's content-address; check the binding's own anchor and proof-of-possession; verify the PQ companion over the artifact's content-address under the in-force pq_pubkey. Accept only if valid; otherwise reject.

A verifier that cannot complete a step (unreachable anchor proof, unresolvable chain) MUST report the artifact unverifiable, distinct from both accept and reject.

Evidence and decision are separate outputs. A verifier's evidence is one of verified, refuted, or unverifiable; the admission decision (admit / refuse) is a projection of that evidence and the cutoff, never an independently settable value. Where evidence and decision are represented as on-chain enumerations, the zero value MUST be the safe one — unverifiable for evidence and refuse for decision — so that an uninitialized, reverted, or unread path degrades to refuse, unverifiable rather than to a silent admit. verified and admit MUST NOT occupy the zero slot; if they did, the default failure mode would be a yes that nobody decided, which is the exact inversion this ERC exists to prevent.

An unverifiable result MUST carry a reason (REQUIRED, not RECOMMENDED): an unverifiable with no reason is the same shape of defect as a rejection covering two facts. Off-chain the reason is a string; on-chain it MUST be a closed enumeration (for example unreachable_anchor, unresolvable_chain, verifier_unavailable), seeded from the causes an implementation actually distinguishes — free text on-chain is not permitted, and the off-chain string MUST project onto the on-chain enumeration without drift.

Rationale

Binding + cutoff, not a second signature. The omission attack is the whole game: any scheme in which the PQ material is optional at verification time protects nothing. The cutoff turns omission into rejection.

Anchor time over signature time. The trustworthy quantity is the one an operator cannot reshape after the fact. Signature timestamps are claims; anchor times are observations.

The anchoring transaction as proof-of-possession. Sending the anchor from the classical address collapses "prove you own the key" and "publish the binding" into one irreversible public fact, removing the last separable signature a forger could work around.

Content-addressing and recomputation. Every object is identified by the hash of its canonical bytes and every verdict is re-derivable from public data. Hashes are the primitive that survives the quantum transition; the design leans the migration entirely on them.

Two families as a structural hedge. In 2026, published cryptanalysis reduced the estimated key-recovery cost of HAWK — a lattice-based hash-and-sign candidate in NIST's additional-signatures process — from 2^64 to 2^38, and the submission team withdrew it. The result does not affect the finalized standards (different problem, different construction), but the lesson is structural: implementations SHOULD pair a finalized standard with a second scheme from a different cryptographic family (e.g. lattice-based ML-DSA alongside hash-based SLH-DSA), so that a break dependent on one family's structure does not transfer to the other.

Related work. A post-quantum public-key registry for Ethereum validators (Lean Consensus) shares this proposal's migration shape: an existing authority pre-registers a post-quantum key with proof of possession ahead of an activation boundary, and post-boundary absence of a valid PQ signature fails closed. It differs in ways this ERC deliberately generalizes. Enforcement there is at the protocol/consensus layer via a fork, network-wide; here it is a consumer-defined cutoff adopted independently, without a coordinated flag day. That design registers validator keys in beacon state, verified by consensus; this ERC binds any application or agent identity, anchored to any public timestamped substrate and verified by recomputation, with no privileged verifier. On temporal authority the contrast is sharpest: the registry's stateful XMSS keys carry an implicit cryptographic expiry — a bounded lifetime that ends when the key's leaves are exhausted, a property of the construction rather than a registry action — while deliberate early or emergency invalidation before expiry remains an open registry-level question there. This ERC's stateless ML-DSA/SLH-DSA keys have no such bounded lifetime, so authority termination is specified explicitly: an anchored revocation record ends a binding's authority at its revocation anchor time, covering end-of-life and compromise through one mechanism.

Backwards Compatibility

No existing artifact is invalidated by the cutoff itself: everything proven anchored before a consumer's cutoff remains verifiable classical-only, permanently — unless a governing binding was revoked at or before the artifact's anchor time, which deliberately ends that binding's authority and overrides back-catalogue admission. The cutoff gates only artifacts anchored at or after it; revocation is the single signal that reaches back across it. Consumers adopt independently, on their own schedule, without coordination; an ecosystem-wide flag day is deliberately not required.

Test Cases

Conformance vectors are provided in the assets directory for this proposal: binding-statement vectors (two independent implementations, two NIST families — ML-DSA-65 and SLH-DSA-SHA2-192s — converging on byte-compatible content-addresses), cutoff-enforcement vectors (admit / reject / unverifiable, including in-force resolution across rotation and revocation, with the refuted and unverifiable cases distinguished rather than collapsed), rotation-chain vectors, and revocation vectors. The cutoff set includes explicit boundary vectors at the activation anchor (t == B, in_force) and the revocation anchor (t == R, authority_revoked — inclusive on the revoked side), so that a fencepost error in the half-open in_force interval reds the suite rather than passing quietly. Each vector states public inputs and the expected verdict; conformance is exact reproduction. The normative cutoff set is pq-key-binding-v1.cutoff-vectors.json (profile pq_key_binding.v1/cutoff-enforcement): it distinguishes the states the earlier v0 set collapsed — refuted versus unverifiable evidence, and a pre-baseline back-catalogue artifact (admits classical-only) versus one anchored at or after revocation (refuted even pre-cutoff) — and adds the t == B and t == R boundary cases. The v0 cutoff set (pq-key-binding-v0.cutoff-vectors.json) is retained unchanged as the frozen base the v1 profile refines, not as a second conformance target.

Reference Implementation

Two independent production implementations converge on this profile: a Nostr-carried ML-DSA-65 binding anchored via OpenTimestamps→Bitcoin, and an EIP-712-carried SLH-DSA-SHA2-192s binding anchored via an on-chain digest record on Ethereum mainnet, with a live cutoff enforcer implementing the verification procedure (including in-force resolution, rotation, and revocation). Vector suites and an executable reference enforcer accompany the conformance assets, alongside a Solidity consumer that reproduces every published cutoff vector on all four of its fields.

Security Considerations

• The omission attack is the primary adversary model; the cutoff rule is its mitigation. Consumers that do not enforce the cutoff gain nothing from the binding's existence — deployment of the consumer rule, not publication of bindings, is what makes the migration operative.
• Anchor availability is load-bearing: a cutoff evaluated against an unfetchable anchor proof is not publicly evaluable. On-chain anchors are RECOMMENDED where permissionless readability matters.
• Recovery authority must not reduce to the secret it replaces. The fleet seed-rotation is anchored by a designated recovery key, proven by its own transaction; compromise of that recovery key is explicitly out of scope for this ERC and MUST be stated as such by implementations.
• Terminality asymmetry (retirement absolute; incident-kill liftable only fleet-level) prevents a compromised per-agent key from resurrecting itself while preserving recoverability from defensive over-reaction.
• Field-element truncation. Implementations binding a 256-bit digest inside a proof system whose scalar field is smaller than 2^256 (e.g. BN254) MUST carry the digest as raw bytes into the in-circuit hash rather than as a single field element; otherwise the value silently reduces mod the field order and off-chain/on-chain recomputation diverges. Small test values mask this; real digests trigger it.
• No "quantum-proof" claim. This ERC migrates the signature layer and rests the migration on hash primitives. It makes no claims about other layers (e.g. key-exchange confidentiality of past traffic).

Copyright

Copyright and related rights waived via CC0.