Quantum-Resistant Short-Lived Certificates

Short-lived certificates play a vital role in current infrastructures, finding a suitable quantum-resistant alternative to the currently used traditional signature schemes is important. This article evaluates the standardized quantum-resistant signature algorithms for this application.

1. Short-Lived Certificates

Short-lived certificates are no different from traditional certificates but with a short validity period. They are used in identity-based infrastructures to grant access to resources for a limited time or, for example, for signing digital contracts. Restrictions are made by including policies within the certificate, to limit what the key can be utilized for.

Short-lived certificates increase security and solve several infrastructural problems which come with key management such as persistence, backup, synchronization, and key revocation. Companies are seeing the value in short-lived certificates and as such increasingly have been adopting them in the last few years.

2. The Threat of Quantum Computing

Due to the threat of a large-scale quantum computer being developed which could break the currently deployed asymmetric cryptography (RSA- and elliptic-curve-based), we must include new, quantum-resistant signature schemes. Indeed, the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), released by the NSA in September 2022, lays out an ambitious transition plan for moving to quantum-resistantcryptography. They do so because of attacks such as harvest now, decrypt later and the realization highlighted by what is known as Mosca’s Theorem. Namely, if we define:

• shelf-life time: the number of years for which the data should be protected.
• migration time: the number of years needed to safely migrate the systems protecting that information.
• threat timeline: the number of years before relevant threat actors can potentially access cryptographically relevant quantum computers.

then Mosca’s Theorem states that if

migration time + shelf-life time > threat timeline

then you are not able to protect your assets against threat actors in possession of a cryptographically relevant quantum computer:

In 2020, the US National Institute of Standards and Technology (NIST) has published SP 800-208 which standardizes the stateful hash-based signatures schemes LMS, HSS, XMSS, and XMSS^MT. In August 2024, NIST finalized standards for ML-DSA (formerly known as Dilithium) and SLH-DSA (formerly known as SPHINCS+) signature schemes. This provides us with a few quantum-resistant candidates to choose from. Among those, only LMS, XMSS and ML-DSA are CNSA 2.0-compliant. Still pending is the standardization (by NIST) of Falcon (soon: FN-DSA). Further, NIST started another process for standardizing additional signature schemes that have qualities not found in the schemes mentioned above.  

3. Choosing a Signature Scheme for Short-Lived Certificates

Let us consider the use of a short-lived certificate when signing a document using an Advanced Electronic Signature – AdES, as regulated through the eIDAS framework (Regulation (EU) 2024/1183, amending Regulation (EU) No 910/2014 ).

That is, we have these operations:

1. Generate keypair.
2. Sign certificate signing request (CSR) using the private key.
3. Have CSR validated and get certificate issued through a certificate authority (CA).
4. Sign document(s) or contract(s).
5. Delete the private key.

All what’s happening after this are signature verifications.

Thus, when looking for a suitable quantum-resistant signature scheme for short-lived certificates we will have to consider key generation time, signing time, and verification time, as well as signature size and public key size as these will remain in the certificate – by the way, the certificate may exist long after it has expired. The size of the private key is not a considerable factor as it can be thrown away after use.

3.1 The Candidates

3.1.1 ML-DSA

For general-purpose signing, NIST recommends ML-DSA. This signature scheme builds on the assumption that the so-called Module-LWE (Module Learning with Errors) problem is hard, which is a variant of the LWE problem. ML-DSA has good performance, although key and signature sizes are significantly larger than what we are used to from the Elliptic Curve Digital Signature Algorithm (ECDSA). If you have no special requirement or constraint this should be your default choice.

 3.1.2 Falcon

Falcon (soon: FN-DSA) is the only signature scheme among those selected for standardization in 2022 (by NIST) that has not been standardized yet. The underlying problem is the shortest integer solution (SIS) problem over so-called NTRU lattices. To be secure against side-channel attacks, Falcon needs constant-time double-precision floating-point arithmetic, which is a highly nontrivial task. This floating-point arithmetic must also be fast to deliver acceptable performance. Falcon does deliver smaller key and signature sizes than ML-DSA, but due to the difficulty in implementation and since it is still not standardized, we would not recommend this.

3.1.3 SLH-DSA

SLH-DSA is a stateless hash-based signature scheme. Its security relies on the second-preimage resistance of the underlying hash functions which makes it a conservative security choice. It has a small public and private key, but unfortunately that is about all positive we can say about SLH-DSA - signatures are large, and key generation, signing, and verification are slow, making SLH-DSA a poor choice for short-lived certificates.

3.1.4 LMS & XMSS

LMS and XMSS are stateful hash-based signature schemes which share the same conservative security as SLH-DSA. Keys are small, signatures are smaller than ML-DSA signatures, signing and verification are fast, while key generation tend to be slower. Importantly, due to the statefulness of the schemes, careful state management is paramount, which can be a difficult task. Also, and contrary to other signature schemes, with the parameter choices at key generation time one commits to a maximum number of signatures that can be made. Both aspects present a challenge for general-purpose signing but are of little relevance in the context of short-lived certificates (see further below).

3.2 Performance Comparison

To compare the performances of the pre-standardized (subsequently standardized - with the exception of Falcon - in August 2024) quantum-resistant signature algorithms, we made some crude measurements using PQShield’s PQCryptoLib v2.2.0, shown in Table 1, while making the ECDSA with the standardized 256-bit curve secp256r1 the baseline for all time measurements. (Note that while secp256r has NIST security level 1, it is vulnerable to quantum computing, whence the exclamation mark.)

Of course, such timings can vary considerably based on the platform and implementation, so these numbers should only be taken as rough estimates. We used a powerful XPS 15 9530 laptop.

Note that no timings are given for SLH-DSA as this algorithm was not supported by PQCryptolib v2.2.0 (but is supported in subsequent versions).

Table 1: PQCryptolib timings for key generation, signing, and verification, as well as signature and public key sizes for ECDSA (baseline), LMS, XMSS, ML-DSA, Falcon, and SLH-DSA.

Data for ML-DSA, FALCON, and SLH-DSA are given for all available NIST security levels, for the sake of illustrating the progression with increasing security level.

3.3 Moving LMS and XMSS into the Spotlight

The LMS and XMSS signature schemes (and their multi-tree variants HSS and XMSS^MT) are often overlooked because they are difficult to handle. Yet, they are still tempting due to their robustness! But what if we only needed an easy-to-forecast number of signatures, and we only needed to handle the state inside a Hardware Security Module (HSM) for a brief period after which the private key is thrown away? Then there would be no need for backup or long-term state management! The exact case for numerous usages of short-lived certificates.

The LMS and XMSS signature schemes are constructed from variants of the Winternitz one-time signature (OTS) scheme, by generating OTS keypairs and structuring them in a Merkle tree to create a shared public key. Because of this construction, only a fixed number of signatures can be created with a given key, and the more signatures you wanted to create in the lifetime of the key, the worse your performance gets. This is because the maximum number of signatures is 2^H where H is the height of the Merkle tree, which also means the larger H, the longer the key generation time. Meanwhile, the sizes of signatures and keys are not as dramatically affected by changes in the tree height. Moreover, the signature size can be controlled (with a trade-off in performance though) by increasing the size of the so-called Winternitz parameter W.

Another parameter that impacts both performance, and signature and key sizes is the length M (in bytes) of the hash function output. However, while neither variations of the tree height H, nor of the Winternitz parameter W impact the security, varying the hash function output M does impact the security level (e.g., M=24 offering NIST security level 3 vs M=32 offering NIST security level 5).

3.3.1 Playing around with parameter-sets

In the context of short-lived certificates, we expect to create only a small number of signatures. Therefore, the multi-tree variants HSS and XMSS^MT are not interesting to us. For the LMS and XMSS signature schemes, we can lower the number of generated OTSs by lowering the height H in expectation of a performance gain.

Now, for historical (not security-related!) reasons, the smallest tree height H that is included in the NIST standard is H=5 for LMS, allowing for 2⁵   = 32 signatures, and H=10 for XMSS, allowing for 2¹⁰   = 1024 signatures, which is much more than we would need. For short-lived certificates, H=2 can be enough! But such small, non-standard tree heights are not available in PQCryptoLib v.2.2.0. So, we utilized Bouncy Castle v1.78, to produce some timings to get an idea how the tree height impacts key generation time for the LMS and XMSS signature schemes. In all cases, baseline is the time for tree height H=5:

Tables 2(a) & 2(b): Bouncy Castle LMS key generation times as a function of the tree height. (Baseline: H=5.)

Table 3: Bouncy Castle XMSS key generation times as a function of the tree height. (Baseline: H=5.)

Looking at Tables 2(a) & 2(b), we indeed observe that LMS-SHA2-M24-H2-W4 and LMS-SHA2-M32-H2-W4 generate keys about 8 times faster than LMS-SHA2-M24-H5-W4 and LMS-SHA2-M32-H5-W4, respectively, this is pretty much as expected given that we generate 8 times fewer OTS keys. This speed-up is consistent throughout: a factor of about 2¹⁸ when switching from H=20 to H=2, a factor of about 2 ¹³ when moving from H=15 to H=2, and about 2⁸ when moving from H=10 to H=2.)

Given the worse overall performance of XMSS, compared to LMS (cf. Table 1), we focus on LMS from now on.

Now, for LMS-SHA2-M24-H2-W4 and LMS-SHA2-M32-H2-W4, let’s do a bold extrapolation from the Bouncy Castle data in Tables 2(a) & 2(b) to the PQCryptoLib data in Table 1:

Table 4: Selected data from Table 1 in comparison with extrapolated data based on Tables 2(a) & 2(b) for LMS with tree height H=2.

The Table 4 data suggest that for short-lived certificates, LMS-SHA2-M32-H2-W4 (security level 5) and LMS-SHA2-M24-H2 (security level 3) are competitive alternatives to ML-DSA-87 and ML-DSA-65, respectively, especially when conservative security assumptions are of importance. Unfortunately, such small tree height is off the current NIST standard, making acceptance and interoperability difficult.

Staying within the NIST standard for stateful hash-based signatures and thus with LMS tree height H=5, there is the option to vary the Winternitz parameterW to achieve faster key generation times in a trade-off with larger signature sizes, and vice versa. The data in Table 5 (generated using PQCryptoLib v.2.2.0) show what can be achieved this way.

Table 5: PQCryptolib LMS key generation times and signature sizes as a function of the Winternitz parameter W.

We maintain that LMS with H=5 is still an interesting alternative to ML-DSA, due to its competitive performance and conservative security.

4 Summary

If your application can handle the signature and key sizes of ML-DSA, this is what you want to use. LMS is a good candidate if you want conservative security, smaller signatures and keypairs, provided you can live with a small performance hit. Of course, with LMS you must handle the state-object, but this is highly simplified in the context of short-lived certificates. It also has the benefit of being simple to understand and implement. The LMS signature scheme with shallow LMS trees of smaller heights than standardized, such as H=2, performs competitively compared to ML-DSA and offers smaller signatures and keypairs. However, due to interoperability concerns we cannot currently recommend this unless you control the entire ecosystem.