Hash-Based Signatures
Hash-based signatures are the most conservative post-quantum option. Their security relies on nothing more than the properties of a cryptographic hash function — no new number-theoretic assumptions. That makes them the safest long-term bet for signing, at the cost of larger signatures and, for some variants, careful state management.
Security From a Hash Alone
Most signature schemes rest on a hard mathematical problem (factoring, discrete log, lattices). Hash-based signatures rest only on the preimage and collision resistance of a hash function — properties that are extremely well studied and slow to erode. Even against quantum computers, only Grover's algorithm applies: for an ideal hash function, Grover's search roughly halves the security strength of a preimage search, which can be compensated by increasing the hash output length. There is no quantum analogue of Shor's algorithm that breaks them. Note that the hash-based family provides signatures only (there is no standardized hash-based KEM).
Building Blocks
Hash-based signatures are assembled from a few classic components:
- One-time signatures (WOTS+ / W-OTS) — a key pair that can safely sign exactly one message. Reusing it leaks the private key.
- Few-time signatures (FORS) — a forest of random subsets that can sign a small number of messages, used inside the stateless construction.
- Merkle trees — hash a large set of one-time public keys into a single root, so one short root authenticates many keys.
- XMSS multitree — layers of Merkle trees that extend the number of signatures a single key can produce without an impractically tall tree.
Stateful vs Stateless
The central design tension is whether the signer must remember which one-time keys have been used.
| Aspect | Stateful (LMS, XMSS) | Stateless (SLH-DSA / SPHINCS+) |
|---|---|---|
| State | Must track key index; never reuse | No state to manage |
| Signature size | Smaller | Larger |
| Speed | Fast | Slower signing |
| Risk | Catastrophic if state is lost/cloned and a key is reused | No reuse risk |
| Best for | Controlled environments (firmware signing) | General-purpose signing |
Where They Are Standardized
- SLH-DSA (SPHINCS+) — stateless, FIPS 205. NIST's deliberately non-lattice signature for cryptographic diversity.
- LMS and XMSS — stateful, specified in NIST SP 800-208, well suited to firmware and software signing where the signing environment is controlled.
Because their security model is the simplest and most conservative of any PQC family, hash-based signatures are an ideal hedge against a future break of lattice mathematics.
Standards & references
- FIPS 205 (SLH-DSA) — the stateless hash-based signature standard.
- SPHINCS+ project — the design behind SLH-DSA.
- RFC 8391 (XMSS) — stateful Merkle-tree signatures.
- RFC 8554 (LMS) — Leighton-Micali stateful hash signatures.
- Resources — full standards register
哈希基签名
哈希基签名是最保守的后量子选项。其安全性仅依赖密码哈希函数的性质，不引入任何新的数论假设。这使其成为最稳妥的长期签名选择，代价是签名较大，且某些变体需要谨慎管理状态。
仅凭哈希的安全性
多数签名方案依赖某个困难数学问题（大整数分解、离散对数、格）。哈希基签名只依赖哈希函数的原像与抗碰撞性——这些性质研究极为透彻，且不易被削弱。即便面对量子计算机，也只有 Grover 算法适用：对理想哈希函数，Grover 搜索会把原像搜索的安全强度约减半，因此可通过增大哈希输出长度来补偿。不存在像 Shor 算法那样能攻破它们的量子手段。需注意，哈希无法构造密钥封装机制，该家族仅用于签名。
构件
哈希基签名由若干经典构件拼装而成：
- 一次性签名 WOTS+ / W-OTS——一对密钥只能安全地签署一条消息，重复使用会泄露私钥。
- 少次签名 FORS——由随机子集构成的森林，可签署少量消息，用于无状态构造内部。
- Merkle 树——将大量一次性公钥哈希为单一根，用一个短根即可认证众多密钥。
- XMSS 多树——多层 Merkle 树，在无需构造高得不切实际的单棵树的前提下，扩展单个密钥可产生的签名数量。
有状态与无状态
核心的设计张力在于：签名方是否必须记住哪些一次性密钥已被使用。
| 方面 | 有状态 LMS XMSS | 无状态 SLH-DSA / SPHINCS+ |
|---|---|---|
| 状态 | 必须追踪密钥索引，绝不重用 | 无需管理状态 |
| 签名体积 | 较小 | 较大 |
| 速度 | 快 | 签名较慢 |
| 风险 | 若状态丢失或被克隆导致密钥重用，后果灾难性 | 无重用风险 |
| 适用场景 | 受控环境、固件签名 | 通用签名 |
标准化情况
- SLH-DSA（SPHINCS+）——无状态，FIPS 205。NIST 为密码多样性而有意选用的非格签名。
- LMS 与 XMSS——有状态，规范见 NIST SP 800-208，非常适合签名环境受控的固件与软件签名。
由于其安全模型在所有 PQC 家族中最简单、最保守，哈希基签名是应对格数学未来被攻破的理想对冲手段。
标准与参考
- FIPS 205 SLH-DSA — 无状态哈希基签名标准。
- SPHINCS+ 项目 — SLH-DSA 的设计来源。
- RFC 8391 XMSS — 有状态 Merkle 树签名。
- RFC 8554 LMS — Leighton-Micali 有状态哈希签名。
- 资源链接 — 完整标准登记册