# ML-KEM-512 Parameters, Sizes, and When to Use It **Source**: https://quantumsequrity.com/blog/ml-kem-512-deep-dive **Category**: PQC Algorithms --- [← Back to Blog](../../blog.html) PQC Algorithms # ML-KEM-512 Parameters, Sizes, and When to Use It 10 min read ML-KEM-512 is the smallest and fastest of the three ML-KEM parameter sets standardized by NIST in FIPS 203 in August 2024. It produces an 800-byte public key, a 768-byte ciphertext, and a 1632-byte secret key, with operations completing in microseconds on a modern CPU. The trade-off is that it sits at NIST Category 1, equivalent to AES-128 against a quantum adversary running Grover's algorithm. For most consumer and IoT use cases, that is more than enough. For long-lived sensitive data or government use, you want ML-KEM-768 or ML-KEM-1024 instead. This article walks through every parameter, every byte size, and every constraint, and tells you exactly when ML-KEM-512 is the right choice and when it is not. ## The Compact Sedan Analogy Imagine three cars in the same product line: a compact sedan, a midsize sedan, and a full-size SUV. They share a chassis, an engine family, and a brand. The sedan is fast, fuel-efficient, easy to park, and good for daily commuting. The SUV is heavier, slower to accelerate, and more expensive, but carries more cargo and is better in storms. ML-KEM-512, ML-KEM-768, and ML-KEM-1024 are the same car family. ML-KEM-512 is the compact sedan: smallest keys, smallest ciphertexts, fastest operations, lowest security level (still strong enough for most needs). ML-KEM-1024 is the SUV: largest keys, largest ciphertexts, slowest operations, highest security. ML-KEM-768 is the midsize compromise. ### Where ML-KEM-512 Earns Its Keep In any setting where bandwidth, storage, or compute are scarce: small embedded devices, mobile apps over cellular, low-power sensors, smart cards. The sub-1-kilobyte sizes mean ML-KEM-512 fits comfortably in single TLS records or single Bluetooth Low Energy packets. Larger parameter sets do not, which forces fragmentation. ## The Numbers in Detail ML-KEM-512 parameters from FIPS 203, Section 8: | Parameter | Value | Notes | |-----------|-------|-------| | n (polynomial degree) | 256 | Same across all three parameter sets | | q (modulus) | 3329 | Same across all three parameter sets | | k (module rank) | 2 | Smaller than 3 (768) or 4 (1024) | | eta1 | 3 | Centered binomial distribution width for secret key | | eta2 | 2 | Centered binomial distribution width for noise | | du | 10 | Compression bits for ciphertext component u | | dv | 4 | Compression bits for ciphertext component v | | Public key | 800 bytes | (k * 12 * 32) + 32 = 768 + 32 | | Secret key | 1632 bytes | Includes encrypted public key copy and z value | | Ciphertext | 768 bytes | (du * k * 32) + (dv * 32) = 640 + 128 | | Shared secret | 32 bytes | After SHA3-256 expansion | | Decryption failure probability | < 2^(-139) | Practical security: virtually zero | The "module rank" k is the headline difference between parameter sets. Doubling k roughly doubles the lattice dimension and brings exponentially more security against attackers who try to solve the underlying lattice problem. Going from k=2 to k=3 to k=4 gives the three security categories. ### Centered Binomial Distribution The "centered binomial distribution" with parameter eta means: sample (a + b) - (c + d), where a, b, c, d are independent uniform bits. The result lies in [-eta, eta] with a binomial-shaped probability. ML-KEM uses this distribution because it is easy to sample, has small variance, and cleanly fits the noise budgets of the proof. For ML-KEM-512, eta1=3 (used in keygen and encryption) and eta2=2 (used for ciphertext masking). ## Security Level: NIST Category 1 NIST defined five security categories in their PQC standardization process. Category 1 means the scheme is at least as hard to break as AES-128 in terms of computational effort. ML-KEM-512 sits squarely at Category 1. | Category | Reference | Approximate bit-strength | |----------|-----------|--------------------------| | Category 1 | AES-128 key search | ~128 bits classical, ~64 quantum (Grover) | | Category 2 | SHA-256 collision search | ~128 bits | | Category 3 | AES-192 key search | ~192 bits classical, ~96 quantum | | Category 4 | SHA-384 collision search | ~192 bits | | Category 5 | AES-256 key search | ~256 bits classical, ~128 quantum | NIST's analysis in FIPS 203 estimates ML-KEM-512 has roughly 2^151 classical bit-strength and 2^139 quantum bit-strength against the best known lattice attacks. This is well above the Category 1 threshold of 2^128 classical / 2^64 quantum that AES-128 sets. ### What This Means in Plain Language ML-KEM-512 is roughly as secure as AES-128 in a quantum-future world. It is more than enough for daily personal use, mobile traffic, IoT communication, and most enterprise traffic. It is not enough for data that must remain secret for 50+ years or for systems that protect national-security material. Those need ML-KEM-768 or ML-KEM-1024. ## Speed: How Fast Is It? Numbers from the official Open Quantum Safe project liboqs benchmarks (rough averages on a Skylake-class x86 CPU at 3 GHz): | Operation | ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 | |-----------|------------|------------|-------------| | Keygen | ~14 microseconds | ~25 microseconds | ~38 microseconds | | Encapsulate | ~16 microseconds | ~28 microseconds | ~44 microseconds | | Decapsulate | ~12 microseconds | ~22 microseconds | ~36 microseconds | These are far below TLS round-trip latencies (hundreds of microseconds at minimum), so the choice between parameter sets does not change perceived web performance. The difference matters more in batch operations and constrained-CPU embedded systems. ## When to Pick ML-KEM-512 Pick ML-KEM-512 when: - You are building a free-tier consumer product with personal-data protection (this is QNSQY Free's default). - You are deploying to mobile, IoT, or smart-card form factors with strict size and power budgets. - The data lifetime is under 10 years. - Bandwidth or storage cost is a real constraint. - Compatibility with TLS 1.3's smallest hybrid groups is desired (X25519 + ML-KEM-512 is a candidate). ## When NOT to Pick ML-KEM-512 Avoid ML-KEM-512 when: - The data must remain confidential for 25+ years (medical records, government archives, treaty texts). - The system protects critical national infrastructure or military communications. - Regulatory frameworks like CNSA 2.0 mandate higher categories. CNSA 2.0 explicitly requires Category 5 for national security, which means ML-KEM-1024. - You expect a quantum-computing leap in the next decade. Conservative customers prefer the bigger parameter set. ## How QNSQY Uses ML-KEM-512 QNSQY's Free tier uses ML-KEM-512 as the default KEM, paired with X25519 in hybrid mode. The pairing ensures that even if lattice cryptanalysis advances unexpectedly, the file remains secure under classical X25519 against today's attackers. Conversely, if a quantum adversary solves X25519, the file remains secure under ML-KEM-512. | QNSQY Tier | Default KEM | Other KEMs available | File size limit | |------------|-------------|----------------------|------------------| | Free | ML-KEM-512 hybrid | None | 100MB | | Pro | ML-KEM-512/768/1024 hybrid | None pure-PQC | 10GB | | Business | All hybrid + pure-PQC modes + HQC variants | Yes | Unlimited | Pro and Business unlock larger ML-KEM parameter sets and pure-PQC modes (no classical backup). The hybrid-default is the conservative recommendation from CISA, NSA, and ENISA during the migration phase, where each post-quantum algorithm is paired with a classical algorithm to mitigate any unexpected break in either family. ### Why X25519 Pairs Well with ML-KEM-512 X25519 has a 32-byte public key and 32-byte shared secret, which combines cleanly with ML-KEM-512's 800-byte public key and 32-byte shared secret. The hybrid is barely heavier than ML-KEM-512 alone in real bandwidth. Browsers like Chrome have shipped X25519 + ML-KEM-768 hybrid, and the 512 variant is similar in spirit but lighter. ## Side-Channel and Implementation Considerations ML-KEM-512 has known timing-attack surfaces in naive implementations, particularly in the inverse Number Theoretic Transform and in the rejection sampling. NIST's FIPS 203 specification includes constant-time guidance, and reference implementations (the official "kyber" repo, plus liboqs and pqcrypto-kyber) follow it. QNSQY uses the audited pqcrypto-mlkem implementation, which has been reviewed by multiple independent security teams and is constant-time on supported CPUs. For embedded targets without constant-time multiply support, additional masking is needed. | Side channel | Mitigation in QNSQY | |--------------|---------------------| | Timing | Constant-time arithmetic, branchless decoding | | Power analysis | Application-level (out of scope for software lib) | | Cache | Constant-time secret-dependent table lookups | | Fault injection | Fail-fast on decryption failures | ## How ML-KEM-512 Performs the Encapsulation Step The encapsulation step takes a public key and produces both a ciphertext and a shared secret. Internally it follows the Fujisaki-Okamoto transform, which converts a chosen-plaintext-secure (CPA) primitive into a chosen-ciphertext-secure (CCA) one. The flow looks like this. First, the encapsulator generates a 32-byte random message m. Second, it derives randomness r from m using SHAKE-256. Third, it runs the underlying CPA encryption on m using r as the randomness, producing the ciphertext. Fourth, it derives the shared secret K from m and the ciphertext using another SHAKE-256 call. The receiver runs the corresponding decapsulation. It runs CPA decryption to recover a candidate m'. It re-derives randomness r' from m' and re-encrypts m' to get a candidate ciphertext c'. If c' matches the received ciphertext, the receiver returns the same shared secret K. If it does not match, the receiver returns a deterministic but unrelated value (the "implicit reject" mechanism). This implicit reject is what gives ML-KEM its CCA security: an attacker who modifies the ciphertext in transit cannot tell whether a real reject happened or a quiet substitution occurred, because the receiver always returns something that looks like a valid shared secret. ## What "Module-LWE" Actually Means in Plain Words Module Learning With Errors is the hardness assumption underlying ML-KEM-512. The plain-words version: you have a secret vector of small integers and a public matrix. You compute the public matrix times the secret vector and add a tiny amount of noise. The result is the public key. The hardness assumption is that, given the public matrix and the noisy product, no efficient algorithm can recover the secret vector. The "module" part refers to using polynomials with bounded coefficients instead of plain integers. Each entry of the secret vector is a polynomial in the ring Z[X]/(X^256 + 1) modulo q=3329. Working with polynomials gives a friendlier algebraic structure that lets the algorithm pack many lattice operations into single arithmetic steps, improving speed without weakening security. The "errors" part is essential: if there were no noise, the public key would let anyone recover the secret by simple linear algebra. Adding small random noise makes the equation underdetermined and turns it into a hard problem. The noise has to be small enough that decryption still works, large enough that the equation is hard, and chosen from a specific distribution that the security proof requires. The centered binomial distribution with eta=3 (for ML-KEM-512) is the choice that balances all three requirements. ## Frequently Asked Questions ### What does the "512" in ML-KEM-512 mean? It refers to the historical name "Kyber-512" in the original Kyber submission. It is loosely the bit-strength against the best classical attacks at the time of submission. NIST renamed Kyber to ML-KEM and kept the parameter labels. ### Is ML-KEM-512 strong enough for HIPAA-protected data? For active patient records with normal threat models, yes. For long-term archival of identifying medical history, the conservative choice is ML-KEM-768 or ML-KEM-1024 to align with the 50+ year retention requirements that some health authorities specify. ### Does ML-KEM-512 use elliptic curves? No. ML-KEM-512 is purely lattice-based. Hybrid mode pairs it with X25519, which is elliptic-curve-based. The two run independently and their shared secrets are concatenated and hashed to produce the final symmetric key. ### What is the failure rate of ML-KEM-512? Decryption failure probability is below 2^(-139), which is effectively zero in any realistic operating lifetime. The IND-CCA2 transformation (Fujisaki-Okamoto) ensures that even if a failure occurs, no useful information leaks to an attacker. ### Can I switch from ML-KEM-512 to ML-KEM-768 later? Yes. QNSQY Pro and Business support all three ML-KEM parameter sets. You can re-encrypt files at the higher level whenever you upgrade tiers. Existing Free-tier files remain decryptable on the lower parameters. ## Sources 1. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (August 2024). [https://csrc.nist.gov/pubs/fips/203/final](https://csrc.nist.gov/pubs/fips/203/final) 2. NIST IR 8413, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process (2022). [https://csrc.nist.gov/pubs/ir/8413/upd1/final](https://csrc.nist.gov/pubs/ir/8413/upd1/final) 3. NSA CNSA 2.0 Cybersecurity Advisory (September 2022). [https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF](https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF) 4. Bos, J. et al. "CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation." NIST PQC Round 3 Submission (2021). [https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf) 5. Cloudflare Research, "Post-quantum cryptography with X25519MLKEM768" (2024). [https://blog.cloudflare.com/post-quantum-key-agreement/](https://blog.cloudflare.com/post-quantum-key-agreement/) ## Related Articles - [ML-KEM Explained](../ml-kem-explained.html) - [Hybrid Encryption Explained](../hybrid-encryption.html) - [Lattice-Based Cryptography Explained](../lattice-based-cryptography-explained.html) - [What Is Post-Quantum Cryptography](../what-is-post-quantum-cryptography.html) - [NIST FIPS Guide](../nist-fips-guide.html) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)