Introduction
After an eight-year evaluation process involving hundreds of submissions from the global cryptographic community, NIST finalized its first set of post-quantum cryptographic standards in 2024. These algorithms are designed to resist both classical and quantum attacks, providing the foundation for the largest cryptographic migration in computing history.
Three primary algorithms emerged from the NIST competition, each serving a different cryptographic function. Understanding their mathematical foundations, performance characteristics, and implementation considerations is essential for security engineers planning post-quantum migrations.
CRYSTALS-Kyber (ML-KEM)
CRYSTALS-Kyber, standardized as ML-KEM (Module Lattice-based Key Encapsulation Mechanism), is the primary algorithm for key exchange and key encapsulation. Its security is based on the Module Learning With Errors (MLWE) problem, which is believed to be hard for both classical and quantum computers.
Kyber offers three security levels: Kyber-512 (NIST Level 1, roughly equivalent to AES-128), Kyber-768 (Level 3, equivalent to AES-192), and Kyber-1024 (Level 5, equivalent to AES-256). Key sizes are larger than RSA or ECC but performance is competitive, with encapsulation and decapsulation operations completing in microseconds on modern hardware.
- Public Key Size: 800 to 1,568 bytes depending on security level (compared to 256 bytes for ECC-256)
- Ciphertext Size: 768 to 1,568 bytes per encapsulation
- Performance: Key generation, encapsulation, and decapsulation all complete in under 100 microseconds
- Use Cases: TLS key exchange, VPN tunnel establishment, secure messaging key agreement
CRYSTALS-Dilithium (ML-DSA)
CRYSTALS-Dilithium, standardized as ML-DSA (Module Lattice-based Digital Signature Algorithm), is the primary algorithm for digital signatures. Like Kyber, its security is based on lattice problems, specifically the Module Learning With Errors and Module Short Integer Solution problems.
Dilithium is recommended as the default signature algorithm for most applications. Its signatures are larger than RSA or ECDSA signatures but verification is extremely fast. This makes it well-suited for certificate validation, code signing, and any application where signatures are verified more frequently than they are generated.
Migration Note: Dilithium signature sizes (2,420 to 4,595 bytes) are significantly larger than ECDSA signatures (64 bytes). This impacts certificate chain sizes, TLS handshake overhead, and storage requirements. Organizations must evaluate bandwidth and storage impacts as part of their PQC migration planning.
SPHINCS+ (SLH-DSA)
SPHINCS+, standardized as SLH-DSA (Stateless Hash-based Digital Signature Algorithm), provides an alternative signature algorithm based entirely on hash functions. Unlike lattice-based schemes, the security of SPHINCS+ relies only on the security of its underlying hash function—a well-understood and highly conservative foundation.
SPHINCS+ serves as a hedge against potential future breakthroughs in lattice cryptanalysis. If the lattice problems underlying Kyber and Dilithium are someday found to be weaker than believed, SPHINCS+ provides a fallback that remains secure. The tradeoff is larger signatures and slower signing performance compared to Dilithium.
- Security Basis: Hash function security only—the most conservative and well-studied cryptographic assumption
- Signature Size: 7,856 to 49,856 bytes depending on security level and parameter set
- Performance: Slower signing than Dilithium but acceptable for applications with infrequent signing
- Role: Backup algorithm providing algorithmic diversity against lattice-based cryptanalysis breakthroughs
Implementing PQC
Implementing post-quantum cryptography in practice requires updating cryptographic libraries, modifying protocol implementations, and testing for compatibility. Libraries like liboqs (Open Quantum Safe) provide reference implementations of all NIST-standardized algorithms, with bindings available for Python, Rust, Go, and other languages.
The most practical starting point for many organizations is hybrid key exchange in TLS, which combines a classical algorithm (like ECDH) with a post-quantum algorithm (like Kyber). This approach provides quantum resistance while maintaining backward compatibility and protecting against potential weaknesses in the new algorithms.
- Library Selection: Choose implementations from liboqs, PQClean, or vendor-specific libraries with FIPS certification
- Hybrid Deployment: Combine classical and PQC algorithms during the transition period for defense in depth
- Performance Testing: Benchmark PQC operations under production-like load to identify bottlenecks from larger keys and signatures
- Interoperability Testing: Verify PQC implementations work across all clients, servers, and intermediary systems in the deployment
The transition to post-quantum cryptography is not a one-time event but an ongoing process that requires crypto-agility—the ability to rapidly swap cryptographic algorithms as standards evolve and new threats emerge.