11 minute read

Post Quantum Cryptography Logo

Post Quantum Cryptography

Introduction

Digital signatures are foundational to modern computing: TLS, software updates, secure messaging, blockchains, and more all depend on signatures. Large-scale quantum computers threaten many number-theory-based schemes (RSA, DSA, ECDSA) due to Shor’s algorithm. Hash-based signatures — notably the SPHINCS family — remain a conservative, well-understood option because their security reduces to the hash function.

This post uses the label “SHL-DSA” to refer to stateless, SPHINCS-like hash-based signatures. Below you’ll find precise algorithmic steps, parameter guidance, signature layout, and implementation notes to help understand, evaluate, or adopt these schemes.

1. Why choose stateless hash-based signatures?

  • Minimal assumptions: security reduces to hash properties (preimage, second-preimage, collision resistance).
  • Quantum resistance: no known quantum algorithm comparable to Shor’s algorithm; best generic quantum attack against hash preimages is Grover’s algorithm (square-root speedup).
  • Stateless operation: unlike traditional stateful hash schemes, SPHINCS-style schemes are designed so the signer does not need to keep per-signature state.

Trade-off: larger signatures and heavier signing work in exchange for conservative, well-understood security.

2. Core components (concise)

  • WOTS+ — Winternitz one-time signature (hash-chain based); signs short values using chains of hash function applications.
  • FORS — Forest of Random Subsets; compresses a message digest into a small number of tree roots with small signatures.
  • Hypertree — stacked Merkle trees that enable many WOTS+ keypairs to be authenticated under a single small public root.

These components are composed so that a message is first compressed with FORS, then the resulting roots are signed with WOTS+, and Merkle auth paths connect WOTS+ leaves to the public hypertree root.

3. Algorithmic pseudocode

The following is a concise, implementation-oriented pseudocode description of a stateless hash-based signature (SPHINCS-like). It is written to be explicit about seeds, role-specific derivations, and the data flowing through FORS, WOTS+, and the hypertree.

Assumptions and notation:

  • $H$ : cryptographic hash or XOF (e.g. SHA-256 or SHAKE256)
  • $\mathrm{PRF}$ : PRF derived from $H$ used for deterministic randomizers
  • $n$ : hash output size in bytes
  • $w$ : Winternitz parameter
  • $k,a$ : FORS parameters (k trees of height a)
  • $L$ : number of hypertree layers
  • $h[0..L-1]$ : per-layer Merkle heights

The pseudocode below uses helper routines that are defined informally:

  • KDF(seed) -> (sk_seed, sk_prf, pk_seed)
  • DeriveWOTSSeed(sk_seed, pk_seed, leaf_index) -> wots_seed
  • WOTS_GenPK(wots_seed, pk_seed) -> wots_pk
  • WOTS_Sign(wots_seed, message_digest) -> wots_signature
  • WOTS_Verify(wots_pk, message_digest, wots_signature) -> leaf_value
  • BuildMerkleTree(leaves[]) -> (root, auth_paths[])
  • FORS_Sign(mhash, sk_seed, pk_seed) -> (sig_fors, root_fors)
  • FORS_Verify(sig_fors, mhash, pk_seed) -> root_fors
function KeyGen(seed):
  (sk_seed, sk_prf, pk_seed) = KDF(seed)

  # --- build leaf values for the bottom layer ---
  for leaf_index in 0 .. (2^{sum(h)} - 1):
    wots_seed = DeriveWOTSSeed(sk_seed, pk_seed, leaf_index)
    wots_pk = WOTS_GenPK(wots_seed, pk_seed)
    leaf[leaf_index] = H_leaf(pk_seed || wots_pk)   # domain-separated leaf hash

  # --- build hypertree: layer-by-layer Merkle roots ---
  for layer in 0 .. L-1:
    (root[layer], auth_paths[layer]) = BuildMerkleTree(leafs_for_layer(layer))
    # prepare leaves for next layer (e.g., root values of groups)
    leafs_for_layer(layer+1) = derive_parent_leaves(root[layer])

  R = root[L-1]  # hypertree root (public)
  sk = (sk_seed, sk_prf, pk_seed, R)
  pk = (pk_seed, R)
  return (sk, pk)


function Sign(sk, message):
  (sk_seed, sk_prf, pk_seed, R) = sk

  optrand = PRF(sk_prf, message)            # optional deterministic randomizer (n bytes)
  mhash = H(optrand || pk_seed || message)  # message digest input to FORS

  (sig_fors, root_0) = FORS_Sign(mhash, sk_seed, pk_seed)

  signature = []
  append(signature, optrand)
  append(signature, sig_fors)

  # Choose a leaf index deterministically (stateless derivation)
  leaf_index = DeriveLeafIndex(sk_prf, message, optrand)

  current_root = root_0
  idx = leaf_index
  for layer in 0 .. L-1:
    wots_seed = DeriveWOTSSeed(sk_seed, pk_seed, idx)
    sig_wots = WOTS_Sign(wots_seed, current_root)
    auth_path = GetAuthPath(idx, layer)          # precomputed or on-demand

    append(signature, sig_wots)
    append(signature, auth_path)

    # compute parent root from wots public key and auth_path
    leaf_value = WOTS_GenPK(wots_seed, pk_seed)  # or reconstruct via verify
    current_root = ComputeRootFromLeafAndPath(leaf_value, auth_path, idx)
    idx = idx >> h[layer]   # move to index of parent in next layer

  return serialize(signature)


function Verify(pk, message, signature_bytes):
  (pk_seed, R) = pk
  (optrand, sig_fors, per_layer_blocks) = parse(signature_bytes)

  mhash = H(optrand || pk_seed || message)
  root_0 = FORS_Verify(sig_fors, mhash, pk_seed)

  current_root = root_0
  idx = DeriveLeafIndexFromSignatureInfo(signature_bytes)  # depends on derivation

  for layer in 0 .. L-1:
    (sig_wots, auth_path) = extract_block(per_layer_blocks, layer)
    leaf_value = WOTS_Verify(sig_wots, current_root, pk_seed)
    current_root = ComputeRootFromLeafAndPath(leaf_value, auth_path, idx)
    idx = idx >> h[layer]

  # final check
  if current_root == R:
    return VALID
  else:
    return INVALID

Notes:

  • DeriveLeafIndex must be deterministic and stateless (derived from sk_prf, message, and/or optrand) so the signer can compute which leaves to use without state.
  • GetAuthPath may be computed on-demand from sk_seed (recomputing leaves) or read from a precomputed tree; implementations often use memory/time trade-offs here.
  • All hash inputs should use explicit domain separation tags (PRF vs chain vs leaf vs tree node) to avoid cross-role collisions.

This pseudocode is intentionally implementation-oriented and omits low-level optimizations (parallelism, incremental tree builds, cacheing). It can be used as the basis for a reference implementation or to map library-specific parameter sets into concrete buffer sizes and sequence ordering.

3.1 Detailed architecture diagram

The diagram below shows the three main phases — Key Generation, Signing, and Verification — and the data flow between FORS, WOTS+, and the hypertree layers. Node labels include common size/operation annotations (e.g. WOTS+ and auth-path sizes) to help reason about costs.

Overview

Notes:

  • $n$ is the hash output length in bytes (e.g. 32 for SHA-256 variants).
  • $len$ is the WOTS+ length (depends on $w$ and $N$).
  • $k$, $a$ are FORS parameters (number of trees and per-tree height).
  • $h_i$ are per-layer Merkle heights; $L$ is the number of layers.

4. Signature format and size considerations

Typical signature structure:

  • $optrand$ or message randomizer (optional/deterministic $\mathrm{PRF}$ output)
  • $\mathrm{sig}_{\text{fors}}$ (FORS signatures)
  • Repeated blocks per hypertree layer: $\mathrm{sig}_{\text{wots},i}$ + $\text{auth_path}_i$

Size drivers:

  • WOTS+ length (depends on Winternitz parameter $w$).
  • Number and size of FORS trees.
  • Hypertree height and number of layers (L).

Approximate signature sizes depend on chosen parameters and hash output length (32 bytes for SHA-256 variants). Implementations usually document sizes for preset parameter choices; expect signatures in the single- to multi-kilobyte range (commonly 8–40 KB depending on security level and compactness goals).

5. Parameter trade-offs (practical guidance)

  • Winternitz $w$: larger $w$ → smaller signatures, slower signing.
  • FORS configuration: more trees of shallower height reduce signing time but increase signature length.
  • Hypertree layering: increasing L (more layers) reduces per-layer tree height (and memory pressure during tree generation) but increases number of WOTS+ signatures and auth paths in the final signature.

Practical advice: prefer library-provided parameter sets (these are tuned for balanced trade-offs and security margins) rather than creating custom sets from scratch.

6. Implementation tips and performance

  • Key generation can be expensive (building many leaves). Use incremental or on-demand leaf computation when possible.
  • Parallelize leaf and chain computations to improve keygen and signing throughput.
  • Use constant-time operations for secret-dependent steps; protect WOTS+ secret chains and PRF outputs from side channels.
  • Consider deterministic signing (PRF-based randomizer) for reproducibility and to avoid reliance on runtime entropy.
  • Domain separation for different hash usages (PRF vs chain vs leaf) is important to prevent unintended interactions.

7. Security sketch

Forging a SHL‑DSA signature generally implies breaking one of the following:

  • FORS (forge a FORS signature / find preimages for those roots),
  • WOTS+ (invert a hash chain or produce a signature for a public key without the secret), or
  • Hash collisions that break Merkle or PRF binding.

Quantumly, Grover’s algorithm reduces the effective security of hash preimage resistance by ~1/2 of the bit-length, so choose parameters accordingly to preserve desired post-quantum security levels.

8. Practical example (liboqs / pyoqs)

This section explains the typical byte layout of a SPHINCS-style signature and shows a small Python helper that computes offsets and slices the opaque signature returned by liboqs/pyoqs for inspection or debugging. Exact sizes depend on the parameter set; the code below computes sizes from the core parameters so you can adapt it to any profile.

Typical signature field sequence (byte order):

  • $optrand$ (optional randomizer): $n$ bytes
  • $\mathrm{sig}_{\text{fors}}$ (FORS secret leaves + auth paths): approximately $k(1+a)\cdot n$ bytes
  • For each hypertree layer $i=0,\ldots,L-1$:
    • $\mathrm{sig}_{\text{wots},i}$ (WOTS+ signature): $\text{len}\cdot n$ bytes
    • $\text{auth_path}_i$ (Merkle auth path): $h_i\cdot n$ bytes

The helper below computes $\text{len}$ (WOTS+ length) and the offsets for each piece.

import math
import oqs

def compute_wots_len(N, w):
  # N: hash output length in bits, w: Winternitz parameter
  len1 = math.ceil(N / math.log2(w))
  len2 = math.floor(math.log2(len1 * (w - 1)) / math.log2(w)) + 1
  return int(len1 + len2)

def compute_signature_layout(N_bits, w, k, a, L, h_list):
  # N_bits: hash output length in bits (e.g., 256),
  # w: Winternitz parameter, k: FORS trees, a: FORS tree height,
  # L: number of hypertree layers, h_list: list of h_i for each layer
  n = N_bits // 8
  wots_len = compute_wots_len(N_bits, w)

  offset = 0
  layout = []

  # optrand (randomizer)
  layout.append(('optrand', offset, offset + n))
  offset += n

  # FORS signature
  fors_size = k * (1 + a) * n
  layout.append(('sig_fors', offset, offset + fors_size))
  offset += fors_size

  # Per-layer WOTS+ + auth path
  for i in range(L):
    wots_size = wots_len * n
    auth_size = h_list[i] * n
    layout.append((f'sig_wots_{i}', offset, offset + wots_size))
    offset += wots_size
    layout.append((f'auth_path_{i}', offset, offset + auth_size))
    offset += auth_size

  return layout

# Example usage: adapt parameters to the chosen SPHINCS+ profile
N_bits = 256  # SHA-256 based variants
w = 16        # example Winternitz parameter
k = 12        # example FORS number of trees
a = 5         # example FORS height
L = 4         # example number of hypertree layers
h_list = [10, 10, 10, 10]  # example per-layer heights

layout = compute_signature_layout(N_bits, w, k, a, L, h_list)
print('Layout fields and byte ranges:')
for name, start, end in layout:
  print(f"{name}: offset {start} .. {end} (len={end-start} bytes)")

# Sign and parse with pyoqs/liboqs (algorithm must match chosen params)
alg = 'SPHINCS+-sha2-128s-robust'  # replace as appropriate
message = b'Example message for parsing demo'
with oqs.Signature(alg) as signer:
  pk = signer.generate_keypair()
  signature = signer.sign(message)

print('\nTotal signature length:', len(signature))
for name, start, end in layout:
  field = signature[start:end]
  print(f"{name}: {len(field)} bytes (hex-prefix: {field[:8].hex()})")

# Note: the offsets computed above assume the chosen params match the
# algorithm used by `liboqs`. If you pick a liboqs algorithm, consult its
# parameter documentation or the SPHINCS+ spec to map alg -> (N,w,k,a,L,h_list).

This parsing approach is useful for debugging, educational inspection, or validating that the signature contains the expected number of WOTS+ and FORS blocks. For production code, avoid parsing signatures manually unless you fully control and trust the parameter mapping; instead use the library’s verify function which interprets the format correctly.

9. Adoption checklist

  • Use a vetted implementation (liboqs, upstream SPHINCS+ reference code, or audited libraries).
  • Select a standard parameter set provided by the implementation.
  • Measure signature sizes and signing/verification throughput on your hardware.
  • For transition, consider hybrid signatures (classical + post-quantum).
  • Include domain separation, side-channel protections, and deterministic signing where appropriate.

Appendix: Mathematical description

Below are mathematical descriptions of the main components and a compact formula for signature size. In what follows let $N$ be the hash/XOF output length in bits and let $n = N/8$ be the hash output length in bytes. Let $w$ be the Winternitz parameter, $L$ the number of hypertree layers, and let $h_i$ be the Merkle tree height for layer $i$ (so $\sum_{i=0}^{L-1} h_i$ is the total hypertree height). Let FORS use $k$ trees each of height $a$.

WOTS+ parameters and lengths: \(\begin{aligned} ext{len}_1 &= \left\lceil\frac{N}{\log_2 w}\right\rceil, \\ ext{len}_2 &= \left\lfloor\frac{\log_2\big(\text{len}_1\,(w-1)\big)}{\log_2 w}\right\rfloor + 1, \\ ext{len} &= \text{len}_1 + \text{len}_2. \end{aligned}\)

Each WOTS+ signature consists of $\text{len}$ hash outputs (each $n$ bytes). Thus the WOTS+ signature size in bytes is \(S_{\mathrm{WOTS+}} = n\cdot\text{len}.\)

WOTS+ chain function and signature elements (compact): \(\begin{aligned} ext{chain}(x, t) &= F^{t}(x) \quad(\text{$t$ iterations of the tweakable hash }F), \\ ext{pk}_i &= F^{w-1}(\text{sk}_i), \\ ext{sig}_i &= F^{a_i}(\text{sk}_i)\quad\text{where } a_i\in[0,w-1]\text{ from base-}w\text{ encoding.} \end{aligned}\)

Base-$w$ encoding (message digest to chain lengths): if $m$ is the $N$-bit digest then represent $m$ in base $w$ to produce digits $c_0,\dots,c_{\text{len}_1-1}$ and compute a checksum over those digits to produce the $\text{len}_2$ checksum digits.

FORS (forest of $k$ trees of height $a$): For each tree $j\in{0,\dots,k-1}$ the signer reveals one secret leaf value $s_{j}$ (size $n$ bytes) and the authentication path of length $a$. The verifier recomputes the tree root $r_j$ from the revealed leaf and the path. The FORS public key is then \(\mathrm{PK}_{\mathrm{FORS}} = H\big(r_0\,\|\,r_1\,\|\,\cdots\,\|\,r_{k-1}\big)\) where $|$ denotes byte concatenation and $H(\cdot)$ includes domain separation.

FORS signature size in bytes (approx): \(S_{\mathrm{FORS}} = k\cdot (1 + a)\cdot n\) since each tree contributes one secret leaf ($n$ bytes) plus $a$ hashes for the auth path ($a\cdot n$ bytes).

Hypertree (stacked Merkle trees) contribution to signature: For each layer $i$ the signature includes one WOTS+ signature and an authentication path of length $h_i$ (each node hashed to $n$ bytes). Thus layer $i$ contributes \(S_{\text{layer }i} = n\cdot\text{len} + n\cdot h_i = n\,(\text{len} + h_i).\)

Total signature size (bytes), including an $n$-byte randomizer $r$ (if used), is therefore approximately: \(\begin{aligned} S_{\text{sig}} &= n \; \Big(1 \;+\; k(1+a) \; + \; \sum_{i=0}^{L-1} (\text{len} + h_i) \Big) \\ &= n \; \Big(1 \;+\; k(1+a) \; + \; L\,\text{len} \; + \; \sum_{i=0}^{L-1} h_i \Big). \end{aligned}\)

Public key size (typical): one hash output (the hypertree root) plus the public seed; in practice $\approx n$ bytes.

Merkle parent and domain separation (formal): let $\mathrm{DOM}$ denote a fixed domain-separation tag for tree-node hashing, then \(h_{\text{parent}} = H\big(\mathrm{DOM}\,\|\,h_{\text{left}}\,\|\,h_{\text{right}}\big).\)

Quantum security adjustment (Grover): if the hash/XOF has output length $N$ bits, generic quantum preimage search gives an attacker advantage analogous to $2^{N/2}$ classical effort. To achieve $r$ bits of security against quantum attackers, choose $N$ such that \(\frac{N}{2} \ge r \quad\Longrightarrow\quad N \ge 2r.\) Example: $r=128$ bits quantum security requires $N\ge 256$ (i.e. $n\ge 32$ bytes).

Side-channel and domain-separation notes (mathematical): denote distinct hash primitives for different roles using tags $\tau_{\mathrm{PRF}},\tau_{\mathrm{chain}},\tau_{\mathrm{leaf}},\tau_{\mathrm{tree}}$. Define role-specific hashes \(H_{\tau}(x) := H\big(\tau\,\|\,x\big)\) so that each use of the hash/XOF is provably separated in proofs and avoids cross-role collisions.

Summary: the formulas above let you compute expected sizes for any parameter choice $(N,w,k,a,L,{h_i})$ and reason about signing cost (chain evaluations) versus signature size (number of hash outputs transmitted). Use library-provided parameter profiles (SPHINCS+ presets) to avoid error-prone manual tuning.