Signature Placement in Post-Quantum TLS Certificate Hierarchies: An Experimental Study of ML-DSA and SLH-DSA in TLS 1.3 Authentication

1. Problem Statement

The migration of TLS 1.3 to post-quantum cryptography (PQC) is often viewed as a simple algorithm substitution problem (replacing classical signatures with PQC ones). However, this paper argues that in certificate-based authentication, the practical impact of a signature algorithm depends heavily on where it is placed within the certificate hierarchy (Root, Intermediate, or Leaf) and how that placement affects the live handshake.

The core problem is that different PQC signature families have vastly different computational profiles and sizes. Specifically, SLH-DSA (stateless hash-based, e.g., SPHINCS+) is significantly larger and computationally heavier than ML-DSA (lattice-based, e.g., Dilithium). The paper investigates whether the operational cost of TLS authentication is determined merely by the presence of a heavy algorithm in the chain, or by its specific placement in the interactive server leaf certificate.

2. Methodology

The study employs a controlled, reproducible experimental framework using OpenSSL 3 and the oqsprovider (Open Quantum Safe) stack.

• Experimental Setup:

  • Environment: Bare-metal local laboratory to minimize network noise and isolate cryptographic costs.
  • Algorithms: Comparison of ML-DSA and SLH-DSA for signatures, and ML-KEM for key exchange.
  • Key Exchange Modes: Classical (X25519), Hybrid (X25519 + ML-KEM), and Pure Post-Quantum (ML-KEM).
  • Hierarchy Variations: The study constructs certificate chains of varying depths (2 and 3) and permutations of signature algorithms across Root, Intermediate, and Leaf positions.

• Experimental Campaigns:

  1. Campaign A (Leaf-Only): Isolates the effect of swapping the leaf signature from ML-DSA to SLH-DSA while keeping the rest of the chain constant.
  2. Campaign B (Full Hierarchy Matrix): Evaluates complete hierarchy strategies (e.g., Root-SLH/Leaf-ML vs. Root-ML/Leaf-SLH) under a hybrid key exchange regime.
  3. Campaign C (Depth Comparison): Analyzes how chain depth (2 vs. 3) affects latency and transport, specifically looking at how "effective chain exposure" (what the client actually receives) differs from logical hierarchy depth.
  4. Campaign D (KEX Exploration): Tests if changing the key exchange mode (Classical vs. Hybrid vs. Pure PQC) alters the dominant cost patterns established by signature placement.

• Metrics:

  • Latency: Mean and P95 handshake times.
  • Transport: Bytes read/written, chain size in DER.
  • Workload Decomposition: Client vs. Server task-clock, CPU cycles, and instructions (using perf counters) to determine where the computational burden lies.
  • Operational Translation: Derived metrics for capacity loss (handshakes per core-second) and infrastructure multipliers.

3. Key Contributions

1. Hierarchy-Sensitive Analysis: Shifts the focus from flat primitive benchmarking to signature placement within the certificate chain as the primary explanatory variable for performance.
2. Discovery of a "Leaf-SLH Regime": Identifies a distinct, catastrophic operational regime that occurs only when SLH-DSA is placed in the server leaf certificate, regardless of the key exchange mode or chain depth.
3. Workload Decomposition: Provides empirical evidence that the heavy regime is not a transport issue or a client-validation issue, but an overwhelmingly server-bound cryptographic compute phenomenon.
4. Operational Viability Framework: Translates microsecond-level latency data into infrastructure capacity metrics (e.g., "2500x more infrastructure required"), demonstrating that some PQC strategies are operationally unviable for interactive front-ends.
5. Effective Chain Exposure: Highlights that logical hierarchy depth does not equal effective chain exposure; removing a heavy Root from the transmitted chain (by adding an Intermediate) can actually reduce latency in specific configurations.

4. Key Results

A. The "Leaf-SLH" Discontinuity

The most significant finding is a massive performance discontinuity based on placement:

• ML-DSA in Leaf: Handshake latency remains in the sub-millisecond to low-millisecond range (e.g., ~0.8 ms).
• SLH-DSA in Leaf: Handshake latency explodes to the ~1.4 second range (an increase of ~1,700x to 2,100x).
• Upper-Layer SLH: Placing SLH-DSA in the Root or Intermediate (while keeping ML-DSA in the Leaf) results in a bounded penalty (latency increases to ~2–3 ms, roughly 3x baseline), which remains operationally plausible.

B. Transport vs. Computation

• Transport Overhead: While SLH-DSA certificates are larger, the increase in transmitted bytes (approx. 3x) does not explain the 1,700x latency increase.
• Cryptographic Cost: In Leaf-SLH scenarios, the server-side task-clock increases by ~2,500x compared to the baseline. The latency is driven by the server's computational burden of signing/verifying the heavy leaf signature, not by network transmission time.

C. Client/Server Decomposition

• Balanced (All-ML): Workload is roughly split between client and server.
• Client-Skewed (Root-SLH/Leaf-ML): The client bears more validation cost, but the server remains efficient.
• Server-Bound (Leaf-SLH): The server consumes ~99.8% of the total elapsed time. The client is effectively idle, waiting for the server to complete the cryptographic operation.

D. Capacity and Economic Impact

• Capacity Collapse: A server using a Leaf-SLH configuration can handle only ~0.04% of the handshakes per second compared to an All-ML configuration.
• Infrastructure Multiplier: To maintain the same throughput, a service using Leaf-SLH would require ~2,500x more server capacity (or cost) than one using ML-DSA in the leaf.
• Economic Translation: For high-volume services, the cost per million handshakes jumps from ~$0.006 (All-ML) to ~$15.60 (Leaf-SLH).

5. Significance and Implications

The paper fundamentally changes how PQC migration in TLS should be approached:

1. Placement > Presence: It is not sufficient to simply "adopt" a PQC algorithm. The position of that algorithm in the PKI hierarchy is the critical design decision.
2. Hybrid Hierarchy Strategy: The paper advocates for mixed hierarchies where heavier, more conservative algorithms (like SLH-DSA) are confined to upper trust layers (Root/Intermediate), while the interactive server leaf uses lighter, faster algorithms (like ML-DSA).
3. Operational Reality Check: Strategies that place SLH-DSA in the leaf are deemed "Unsuitable for interactive TLS front-ends." They represent a "scaling pathology" that would make high-volume services economically and technically unviable.
4. Design Guidance: For organizations migrating to PQC, the optimal strategy is likely a Root-SLH / Intermediate-ML / Leaf-ML configuration. This preserves the security benefits of SLH-DSA in the trust anchor while maintaining interactive performance at the edge.

Conclusion: Post-quantum TLS migration is a cryptographic design problem concerning certificate hierarchy and chain exposure, not merely an algorithm selection problem. Ignoring signature placement leads to deployment strategies that are mathematically secure but operationally impossible for interactive services.