Hybrid Post-Quantum Signature Constructions

Technical specification for hybrid digital signature schemes combining classical algorithms (ed25519, sr25519) with post-quantum algorithms (ML-DSA-44, Falcon-512, SHRINCS).

Version: 2.0 · Status: Draft for external review · Date: 2026-07-18

Conventions

The key words MUST, MUST NOT, REQUIRED, SHALL, SHOULD, SHOULD NOT, MAY, and OPTIONAL in this document are to be interpreted as described in RFC 2119 and RFC 8174 when, and only when, they appear in all capitals.

Terms used throughout the SHRINCS additions, defined here on first reference:

SHRINCS — a two-path hash-based signature scheme (ePrint 2025/2203). One committed key carries a cheap bounded stateful path and an expensive stateless break-glass path.
Stateful path / UXMSS / WOTS-C — the everyday path: a WOTS-C one-time signature at one leaf of an unbalanced XMSS-style Merkle tree (UXMSS; XMSS, RFC 8391). WOTS-C replaces Winternitz checksum chains with target-sum grinding: the signer grinds a counter until the message's base-w digits sum to a fixed target, and the verifier checks the sum.
Leaf — one single-use position in the stateful tree. Each stateful signature consumes one leaf; the leaf index equals the signature's authentication-path length.
Stateless path / SPHINCS+C / FORS-C — the recovery path: a full SPHINCS+C signature (ePrint 2022/778). Carries no signer state; bounded by a verifier-tracked few-time budget.
Commitment (publicKeyCommitment) — a 32-byte keccak-256 hash digest binding a SHRINCS public-key bundle plus its profile. A compacting public digest, not a hiding commitment scheme: callers resupply the full bundle at verification and the verifier recomputes and checks the digest.
keyVersion / nonce — per-account replay-scoping counters held by the integrating account or registry (not fields of the cryptographic key). keyVersion is the rotation epoch; both advance on rotation.
Graft — a stateful-only rotation: a fresh stateful tree grafted onto the unchanged stateless half of the bundle.
PathSelector — a one-byte wire field naming which SHRINCS path a composite signature carries (stateful or stateless).

Changelog

Version	Date	Summary
2.0	2026-07-18	Adds two stateful hash-based constructions, H5 (ed25519 + SHRINCS) and H6 (sr25519 + SHRINCS). New sections cover signer-state management, key lifecycle and commitment rotation, two-path acceptance policy, and exhaustion budgets. SHRINCS entries added throughout the inventory, key/signature formats, label registry, API, and tests. The Section 8 and Section 11 code listings now match the implemented `HybridSignatureScheme` trait, and Section 10 now matches the implemented hard-only key derivation. The H1–H4 wire format is unchanged: the version prefix stays `0x01` and existing labels are untouched; every SHRINCS addition is a new registry entry.
2.0	2026-07-18	Sections 3, 4, and 22: informative additions (ticketing-5vm.1) documenting the Falcon/FN-DSA pre-standardization rationale for the H2/H4 spec-only, no-implementation status; Section 14 Falcon validator SCA threat model + normative deployment gate; Section 8 use-case matrix + Section 4 status conditionality for H2/H4 (ticketing-5vm.6); Section 5 normative Substrate AccountId derivation + full-PK envelope + dual-check for H1–H4 (H3 as deployed); Section 19.4 H5/H6 bridge (ticketing-5vm.9); Section 8: Substrate SignedPayload >256-byte pre-hash rule for external signers (H1–H6); Section 13 cross-language note (ticketing-5vm.10); Section 14: Falcon leakage mechanisms, named key-recovery/fault results (7 confirmed papers, corrected keygen/signing attribution), countermeasure status; Section 1: informative Falcon SCA reference table (ticketing-5vm.7); Section 3: multivariate (SNOVA/NOVA) evaluated-and-not-selected record with Li–Ding cryptanalysis + dated NIST Round-3 status; Section 1: ePrint 2024/110 reference row (ticketing-5vm.8); Section 11: new 'Crate Selection Record (H1–H4)' subsection — normalized 100-point rubric, adoption bands, six hard-filter criteria (ticketing-5vm.2); Section 11 crate-selection record: rejected FFI candidates (oqs/liboqs-rust, pqcrypto-*) + normative wasm32-unknown-unknown adoption gate; Section 13 target-triple note (ticketing-5vm.3); Section 11 crate-selection record: per-crate audit/maturity table (fips204, fn-dsa, ml-dsa; as of 2026-07) + compensating controls; Section 14 implementation-maturity entry (ticketing-5vm.4); Section 11 crate-selection record: ML-DSA dual-candidate record (ml-dsa vs fips204; shipped = fips204 0.4.6) + ML-DSA-default/Falcon-conditional deployment policy + classical-half guidance (ticketing-5vm.5); Section 11: Substrate deployment identifier registry (crypto-IDs h144/h344, key types, both CLI token sets); Section 4 deployed role map; Section 7/8 namespace pointers (ticketing-5vm.13); Section 11: H1/H3 keystore precedents subsection (long-PK persistence, crypto-ID routing, seed-only Pair) before the H5/H6 keystore requirements; Section 5 cross-link (ticketing-5vm.12); Section 16: migration-cost record from the H3 rollout (transaction_version break, polkadot-js signFake sizing, open consensus soak) + H5/H6 scale-up; Section 4 pointer (ticketing-5vm.14); Section 14: deployment-state caveats (equivocation reporting disabled; no runtime validator rotation); Section 19.5 dated qualifier; Section 22: rotation/equivocation + SDK-pin open items (ticketing-5vm.15).
1.x	2026-07-02	Prior version (H1–H4 only).

1. Scope & References

Scope

This document specifies six hybrid signature constructions for the substrate ecosystem. H1–H4 pair a classical scheme with a lattice scheme; H5–H6 pair a classical scheme with the hash-based SHRINCS scheme. Each construction pairs one classical signature scheme with one post-quantum signature scheme, producing a composite signature that is EUF-CMA secure if at least one component scheme remains secure — for the stateful hash-based constructions H5/H6, conditional on state discipline (Section 2).

In scope: Key generation, signing (hedged and deterministic modes for H1–H4; single-mode stateful signing for H5/H6), verification, serialization, domain separation, seed derivation, signer-state management for stateful components, and language-specific implementation guidance for Rust and Go.