Summary
Kyber defines three parameter sets, corresponding to NIST security levels 1, 3, and 5. There is no level 2 or 4 because Kyber does not use hash functions (required for even-numbered levels in NIST's taxonomy).
Parameter Table
| Parameter | ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 |
|---|---|---|---|
| NIST Level | 1 | 3 | 5 |
| Equivalent strength | AES-128 | AES-192 | AES-256 |
| k (module dimension) | 2 | 3 | 4 |
| n (polynomial degree) | 256 | 256 | 256 |
| q (modulus) | 3329 | 3329 | 3329 |
| η (CBD error parameter) | 2 | 3 | 3 |
| du (compression bits for u) | 10 | 10 | 11 |
| dv (compression bits for v) | 4 | 4 | 5 |
| δ (failure probability) | 2⁻¹³⁹ | 2⁻¹⁶⁴ | 2⁻¹⁷⁴ |
Sizes
| ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 |
|---|---|---|
| pk: 800 B | pk: 1184 B | pk: 1568 B |
| sk: 1632 B | sk: 2400 B | sk: 3168 B |
| ct: 768 B | ct: 1088 B | ct: 1568 B |
Comparison with RSA and ECC:
| Scheme | Public key | Private key | Ciphertext |
|---|---|---|---|
| RSA-2048 | 256 B | 512 B | 256 B |
| ECDH P-256 | 32 B | 32 B | 32 B |
| ML-KEM-768 | 1184 B | 2400 B | 1088 B |
Size is the price of quantum resistance. However, Kyber is up to 10× faster than RSA-2048 in key operations.
NIST Levels
NIST defines 5 security levels for the PQC competition:
| Level | Description | Difficulty against |
|---|---|---|
| 1 | At least as hard as breaking AES-128 (exhaustive search) | Classical attacker |
| 2 | At least as hard as breaking SHA-256 (collision) | Classical attacker |
| 3 | At least as hard as breaking AES-192 (exhaustive search) | Classical attacker |
| 4 | At least as hard as breaking SHA-384 (collision) | Classical attacker |
| 5 | At least as hard as breaking AES-256 (exhaustive search) | Classical attacker |
Kyber does not achieve levels 2 and 4 because its security does not depend on collision resistance of hashes. This is not a weakness — it is simply that NIST defined categories based on different cryptographic problems.
Equivalent Strength — The Real Measure
"Equivalent strength" is not exact. The comparison with AES is a lower bound:
- ML-KEM-512: The best known security bound against a classical attacker is ~2¹⁴³ operations. Against a quantum attacker (using Grover on AES-128 key search), ~2¹²⁸. NIST considers it "at least" as strong as AES-128.
- ML-KEM-768: ~2²⁰⁷ classical operations, ~2¹⁹² quantum. Significantly exceeds AES-192.
- ML-KEM-1024: ~2²⁷² classical operations, ~2²⁵⁶ quantum.
Failure Probability
Kyber has a non-zero decryption failure probability: there is a tiny chance that Decaps(sk, Encaps(pk)) does not produce the same key K.
| Parameter | δ | Practical implication |
|---|---|---|
| ML-KEM-512 | 2⁻¹³⁹ | Negligible |
| ML-KEM-768 | 2⁻¹⁶⁴ | Negligible |
| ML-KEM-1024 | 2⁻¹⁷⁴ | Negligible |
In practice, a failure requires an extremely unlikely combination of errors that accumulate to overflow the compression range. A failure means the parties obtain different keys and communication fails (no secret leakage). The higher-level protocol must retransmit.
Recommended Choice
| Context | Recommendation |
|---|---|
| Prototypes, experimentation | ML-KEM-512 |
| General use, production 2024-2030 | ML-KEM-768 |
| Classified data, long-term (>20 years) | ML-KEM-1024 |
| Hybrid with X25519 | X25519Kyber768 |
Note: NIST only certifies ML-KEM-768 and ML-KEM-1024 for US government use. ML-KEM-512 is considered sufficient for low-risk commercial applications.
References
- NIST FIPS 203 (2024). "Module-Lattice-Based Key-Encapsulation Mechanism Standard."
- NIST SP 800-227 (2024). "Recommendations for Key-Encapsulation Mechanisms."
- Alagic, G. et al. (2022). "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process."