NIST Advances Fourteen Post-Quantum Signature Schemes
/ 4 min read
Quick take - On October 24, 2024, the National Institute of Standards and Technology (NIST) advanced fourteen post-quantum signature schemes to the second round of its competition, aiming to standardize algorithms that can withstand potential quantum computer attacks while addressing challenges related to data size and performance in digital communications.
Fast Facts
- NIST advanced fourteen post-quantum signature schemes to the second round of its “signatures on ramp” competition, aiming to standardize algorithms resistant to quantum attacks.
- The initiative responds to the urgent need for robust post-quantum signatures, particularly for securing Transport Layer Security (TLS) in digital communications.
- Current evaluations show that none of the post-quantum algorithms yet match the performance of classical elliptic curve signatures, with candidates like ML-DSA and SLH-DSA facing challenges related to size and computational overhead.
- NIST plans two migrations for TLS: one for post-quantum key agreement and another for post-quantum signatures, emphasizing the importance of efficient data handling to avoid performance issues.
- A large-scale experiment indicated that even a small increase in certificate chain size could significantly slow TLS handshake times, raising concerns about user experience and data usage.
NIST Advances Post-Quantum Signature Schemes
On October 24, 2024, the National Institute of Standards and Technology (NIST) announced the advancement of fourteen post-quantum signature schemes to the second round of the “signatures on ramp” competition. This initiative is a key step towards standardizing algorithms designed to withstand potential quantum computer attacks. The announcement comes in response to the growing need for robust post-quantum signature schemes.
Importance of Post-Quantum Algorithms
NIST has already standardized four such schemes and is in the process of drafting a standard for a fifth, known as Falcon. Post-quantum algorithms play a crucial role in securing digital communications, particularly in the context of Transport Layer Security (TLS), which is essential for safeguarding Internet browsing. Many of the advanced schemes under consideration require significantly larger data sizes to be transmitted over networks. Previous studies have indicated that nearly half of the data sent over QUIC connections is dedicated to certificates, underscoring the importance of efficient data handling in the development of these algorithms.
NIST is planning two migrations for TLS. One migration is for post-quantum key agreement, which is considered urgent due to the immediate threat posed by quantum computing. The other migration is for post-quantum signatures, which, while less urgent, remains critical to address before quantum computers become widely available.
Evaluating New Signature Algorithms
The TLS handshake process is notably complex, involving multiple signatures and public keys, requiring a minimum of five signatures and two public keys to establish a secure connection. The newly evaluated post-quantum signature algorithms are being compared against classical algorithms vulnerable to quantum attacks. Current evaluations indicate that none of the post-quantum algorithms yet match the performance of classical elliptic curve signatures.
Among the candidates, ML-DSA stands out as a viable general-purpose option; however, it features larger signature and public key sizes. SLH-DSA, based solely on hashes, offers well-understood security but comes with significant size and computational overhead. Falcon, while promising, faces challenges in terms of signing speed and implementation complexity. Other notable candidates include stateful hash-based signatures like XMSS and LMS, which carry security advantages but necessitate careful management to prevent vulnerabilities. NIST is also considering code-based signature schemes such as CROSS and LESS, along with multi-party computation in the head (MPCitH) schemes, with FAEST emerging as a strong contender due to its superior performance metrics.
Impact on TLS Performance
A blog post discussing these advancements highlights the impact of increased data sizes on TLS performance. It notes that adding more than 10kB to certificate chains could lead to failures in client and middlebox communications. A large-scale experiment demonstrated that even a 9kB increase could slow TLS handshake times by approximately 15%. Chrome has set a benchmark for maximum TLS handshake time regression at 10%, reporting a 4% slowdown following the deployment of post-quantum key agreements. The median certificate chain size currently stands at 3.2kB, and utilizing algorithms like ML-DSA may more than double the bytes transmitted in many connections, raising concerns about user experience and data usage.
The blog concludes by emphasizing the ongoing improvements in post-quantum signature algorithms and the critical need for further research and development to address these challenges effectively.
Original Source: Read the Full Article Here
