First Post-Quantum Algorithm Certificate issued by CAVP

By Joachim Vandersmissen

 

On July 14, atsec obtained the first validation certificate for a post-quantum cryptographic algorithm: A4204. We used the Automated Cryptographic Validation Protocol (ACVP) to verify the correctness of the LMS (Leighton-Micali Signature) key pair generation, signature generation, and signature verification implementations in the QASM Hardware Security Module, developed by Crypto4A Technologies. This milestone represents an important step in the ongoing transition from traditional public-key cryptography to quantum-resistant algorithms.

The LMS scheme is a digital signature scheme based on secure hash functions and Merkle trees. It was first published in 1995 by Leighton and Micali and is based on the famous one-time signature scheme proposed by Lamport in 1979. Among quantum-resistant public-key algorithms, these schemes provide a distinct advantage: the post-quantum security of the scheme relies exclusively on the security of the underlying hash function. No other number-theoretic hardness assumptions are required. This is very attractive, as all modern hash functions with an output size of more than 256 bits are believed to be quantum safe. However, there are also drawbacks. In particular, LMS is a stateful signature scheme. In other words, it maintains an internal state that must be protected in hardware. Still, the benefits of hash-based cryptography significantly outweigh the costs, which lead to LMS (and XMSS) being standardized by NIST in 2020 (SP 800-208).

In May 2022, SP 800-208 was added to SP 800-140C, which specifies the algorithms approved for usage in FIPS 140-3 cryptographic modules. This also paved the way for LMS and XMSS to be tested by the Cryptographic Algorithm Validation Program (CAVP). The CAVP verifies the correct implementation of cryptographic algorithms and their components. Initial support for the LMS scheme was added in March 2023 and made available for production usage in April. We would like to thank the CAVP for their diligent work and excellent support to make this achievement possible.

Quantum computers represent a significant risk to classical public-key cryptography, a risk which cannot be ignored. Last year, the Commercial National Security Algorithm (CNSA) Suite 2.0 was published, which envisions a complete transition to post-quantum cryptography by 2033. We applaud Crypto4A Technologies for its proactive approach to offer this quantum-resistant signature scheme to its customers well ahead of the deadline.