In late October, the U.S. National Institute of Standards and Technology (NIST) announced that 14 post-quantum algorithms for digital signatures have advanced to the second round of the ‘signatures on ramp’ competition. These algorithms are designed to ensure the security of our digital communications in the future era of quantum computers. Previously, four quantum secure algorithms have been standardised: ML-DSA, SLH-DSA, XMSS and LHS, while work on Falcon is the fifth. Bas Westerbaan, Research Engineer at Cloudflare, provides insight into the importance and status of quantum secure digital signatures.
The role of digital signatures in TLS
When someone visits a website, a TLS (Transport Layer Security) connection is established between the browser and the server. With this digital signature, the server signs the exchanged communication and presents a TLS-leaf certificate to show that it is authorised to operate the website. This certificate is signed by a certificate authority (CA). Often this is not directly by the root CA, but through a third-party CA certificate.
In addition, a TLS-leaf certificate must contain a minimum of two Signed Certificate Timestamps (SCTs), which show that the certificate was publicly registered in Certificate Transparency (CT) logs. This may increase to three or more SCTs in the coming years. Finally, the server may include an OCSP step to demonstrate that the certificate has not been revoked. Thus, a minimum of five signatures and two public keys are sent over the network to establish a new TLS connection.
Different types of digital signatures
Within TLS, both online and offline digital signatures are used. The signature to transmit information is generated online with every incoming TLS connection, so fast signing is essential. The other signatures are generated offline, often weeks, months or years in advance, so speed of signing is less critical. With offline signatures, fast verification is more important than fast signing.
Evaluation of quantum secure signatures
The 14 algorithms that reached the second round of NIST’s competition vary in performance and size. A key challenge is that many of these algorithms have much larger signatures and public keys compared to classical algorithms such as RSA or ECDSA. This leads to an increase in the amount of data sent over the network during the TLS handshake, which of course can affect performance.
The lattice-based ML-DSA (formerly Dilithium) has relatively large signatures and public keys, but is simple in implementation and requires little computing power. SLH-DSA (previously SPHINCS+) is based on hash functions and thus enjoys high confidence in security, but has large signatures and requires more computing power for signing and verification.
Falcon offers smaller signatures and fast verification, but requires complex and subtle implementation for secure signing, making it less suitable for online digital signatures.
Impact on the TLS handshake
Adding larger quantum secure signatures for the TLS handshake, as mentioned, can greatly increase the amount of data sent during the handshake. Experiments show that nearly half of the data sent over more than half of current QUIC connections already consists of certificates. Adding even larger digital signatures will further increase this overhead, which could adversely affect connection performance.
Future challenges
Although the migration to quantum-secure cryptography for digital signatures is less urgent than that to quantum-secure key exchange, it will be more challenging in practice. This is due to the complexity of associated certificate management, the sizes of signatures and the involvement of multiple parties, such as different certification authorities, browsers and servers.
Good performance is essential to the success of quantum secure cryptography for TLS. As a result, fundamental changes to TLS are now under discussion to reduce the number of digital signatures. The next few years will be crucial for evaluating and standardising these algorithms and changes to TLS to ensure that all of our Internet communications remain secure in the future with quantum computing.
