Proposal: Hybrid Post-Quantum Signatures

Research
1

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).

A notion document with commenting enabled is available here: https://app.notion.com/p/Hybrid-Post-Quantum-Signature-Constructions-330db8c6a0888106abe9d5d75631a03e?source=copy_link

Editors welcomed, just reply here or drop comments in notion.

1. Scope & References

Scope

This document specifies four hybrid signature constructions for the substrate ecosystem. 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.

In scope: Key generation, signing (hedged and deterministic modes), verification, serialization, domain separation, seed derivation, and language-specific implementation guidance for Rust and Go.

Out of scope: Hybrid NIKE/key exchange, key encapsulation (KEM), standalone PQ algorithm deployment, and signature aggregation (BLS).

Normative References

Reference Title
FIPS 204 Module-Lattice-Based Digital Signature Standard (ML-DSA)
FIPS 206 (draft) FN-DSA (Falcon) Digital Signature Standard
RFC 8032 Edwards-Curve Digital Signature Algorithm (EdDSA)
draft-ietf-lamps-pq-composite-sigs Composite ML-DSA Digital Signatures
ePrint 2023/422 A Differential Fault Attack against Deterministic Falcon Signatures
schnorrkel Schnorr-Ristretto (sr25519) specification

Reference Implementations

Algorithm Rust Crate Repository
ed25519 ed25519-zebra paritytech/substrate (sp_core::ed25519)
sr25519 schnorrkel paritytech/substrate (sp_core::sr25519)
ML-DSA-44 fips204 integritychain/fips204
Falcon-512 fn-dsa pornin/rust-fn-dsa

2. Motivation

Threat Model

A Cryptographically Relevant Quantum Computer (CRQC) can break ed25519 and sr25519 via Shor’s algorithm. Post-quantum algorithms (ML-DSA-44, Falcon-512) are resistant to known quantum attacks but are newer and less battle-tested than classical schemes.

Security Goal

EUF-CMA (Existential Unforgeability under Chosen Message Attack) security if at least one component scheme remains secure. If either the classical or post-quantum algorithm is broken, the composite signature remains unforgeable through the surviving component.

Why Hybrid

  • Hedge against cryptanalytic breakthroughs in either classical or PQ algorithms
  • PQ algorithms have shorter deployment history — hybrid construction provides a safety net
  • Matches the IETF composite signature approach (draft-ietf-lamps-pq-composite-sigs)

Rest of document in notion: https://app.notion.com/p/Hybrid-Post-Quantum-Signature-Constructions-330db8c6a0888106abe9d5d75631a03e?source=copy_link

3

Go Implementation Guidance

Interface Design

Following the existing nike.Nike pattern from nike/interfaces.go:

type HybridSigScheme interface {
    PublicKeySize() int
    PrivateKeySize() int
    SignatureMaxSize() int

    NewKeypair(rng io.Reader) (PrivateKey, PublicKey)
    FromSeed(seed []byte) (PrivateKey, PublicKey, error)

    Sign(privKey PrivateKey, msg []byte,
        rng io.Reader) ([]byte, error)

    SignDeterministic(privKey PrivateKey, msg []byte,
        nonce []byte) ([]byte, error)

    Verify(pubKey PublicKey, msg []byte,
        sig []byte) bool

    VerifyDeterministic(pubKey PublicKey, msg []byte,
        sig []byte, expectedNonce []byte) bool

    UnmarshalBinaryPublicKey(b []byte) (PublicKey, error)
    UnmarshalBinaryPrivateKey(b []byte) (PrivateKey, error)
}

Struct Composition

Following the scheme{first, second} pattern from hybrid.go:

type hybridSigScheme struct {
    name      string
    classical SignatureScheme
    pq        SignatureScheme
    label     []byte
}

Error Handling

Use github.com/pkg/errors for wrapping:

errors.WithMessage(err, "hybrid sign: classical component failed")
errors.WithMessage(err, "hybrid sign: pq component failed")

Use github.com/goccy/go-json instead of encoding/json (per codebase conventions).

1 Like