Attacks on PQC Schemes | Post-Quantum Cryptography

Overview

Post-quantum cryptographic algorithms are not immune to attack — they are simply resistant to attacks by quantum computers running Shor’s algorithm. Every PQC scheme faces a rich ecosystem of threats: mathematical cryptanalysis that targets the underlying hard problems, side-channel attacks that exploit physical implementation characteristics, fault injection attacks that corrupt computation to leak secrets, and protocol-level attacks that circumvent the cryptography entirely.

Understanding these attacks is essential for anyone deploying PQC in production. The NIST standardized algorithms — ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205), and the forthcoming FN-DSA — were selected partly because they have survived extensive cryptanalysis. But “survived” does not mean “invulnerable.” Other schemes that appeared equally strong — SIKE and Rainbow — were catastrophically broken after years of scrutiny, reminding the community that confidence in any cryptographic scheme is provisional.

This page provides a comprehensive treatment of the attack landscape against PQC: the mathematical foundations of lattice reduction and code-based attacks, the spectacular breaks of SIKE and Rainbow, side-channel and implementation attacks against the NIST standards, protocol-level threats during the transition period, and the mitigations that practitioners must deploy to defend against each category. For background on the specific algorithms discussed, see Lattice-Based Cryptography, Hash-Based Signatures, and Code-Based Cryptography. For the broader context of the standardization process, see NIST PQC Standardization.

1. Attack Taxonomy

Before examining specific attacks, it helps to see how they relate to one another. The following taxonomy organizes attacks by the layer they target.

graph TD
    ROOT["Attacks on PQC Schemes"] --> MATH["Mathematical Cryptanalysis"]
    ROOT --> SC["Side-Channel Attacks"]
    ROOT --> IMPL["Implementation Attacks"]
    ROOT --> PROTO["Protocol-Level Attacks"]

    MATH --> LATTICE["Lattice Reduction"]
    MATH --> ISD["Information Set Decoding"]
    MATH --> ALG["Algebraic Attacks"]
    MATH --> ISO["Isogeny Attacks"]

    LATTICE --> BKZ["BKZ / BKZ 2.0"]
    LATTICE --> PRIMAL["Primal Attack"]
    LATTICE --> DUAL["Dual Attack"]
    LATTICE --> CORESVP["Core-SVP Methodology"]

    ISD --> PRANGE["Prange's Algorithm"]
    ISD --> STERN["Stern / Dumer"]
    ISD --> MMT["MMT / BJMM"]

    SC --> TIMING["Timing Attacks"]
    SC --> POWER["Power Analysis (SPA/DPA)"]
    SC --> EM["EM Emanation"]
    SC --> CACHE["Cache-Timing"]

    IMPL --> FAULT["Fault Injection"]
    IMPL --> KEYMIS["Key Mismatch"]
    IMPL --> COMP["Comparison Leaks"]

    PROTO --> DOWN["Downgrade Attacks"]
    PROTO --> STRIP["Hybrid Stripping"]
    PROTO --> CERT["Certificate Substitution"]
    PROTO --> ROLL["Version Rollback"]

    style ROOT fill:#1a1a2e,stroke:#e94560,color:#eee
    style MATH fill:#1a1a2e,stroke:#00d4aa,color:#eee
    style SC fill:#1a1a2e,stroke:#00d4aa,color:#eee
    style IMPL fill:#1a1a2e,stroke:#00d4aa,color:#eee
    style PROTO fill:#1a1a2e,stroke:#00d4aa,color:#eee
    style LATTICE fill:#1a1a2e,stroke:#0f3460,color:#eee
    style ISD fill:#1a1a2e,stroke:#0f3460,color:#eee
    style ALG fill:#1a1a2e,stroke:#0f3460,color:#eee
    style ISO fill:#1a1a2e,stroke:#0f3460,color:#eee
    style BKZ fill:#16213e,stroke:#0f3460,color:#aaa
    style PRIMAL fill:#16213e,stroke:#0f3460,color:#aaa
    style DUAL fill:#16213e,stroke:#0f3460,color:#aaa
    style CORESVP fill:#16213e,stroke:#0f3460,color:#aaa
    style PRANGE fill:#16213e,stroke:#0f3460,color:#aaa
    style STERN fill:#16213e,stroke:#0f3460,color:#aaa
    style MMT fill:#16213e,stroke:#0f3460,color:#aaa
    style TIMING fill:#16213e,stroke:#0f3460,color:#aaa
    style POWER fill:#16213e,stroke:#0f3460,color:#aaa
    style EM fill:#16213e,stroke:#0f3460,color:#aaa
    style CACHE fill:#16213e,stroke:#0f3460,color:#aaa
    style FAULT fill:#16213e,stroke:#0f3460,color:#aaa
    style KEYMIS fill:#16213e,stroke:#0f3460,color:#aaa
    style COMP fill:#16213e,stroke:#0f3460,color:#aaa
    style DOWN fill:#16213e,stroke:#0f3460,color:#aaa
    style STRIP fill:#16213e,stroke:#0f3460,color:#aaa
    style CERT fill:#16213e,stroke:#0f3460,color:#aaa
    style ROLL fill:#16213e,stroke:#0f3460,color:#aaa

Each category demands different mitigations. A mathematically secure algorithm can be broken by a timing side channel; a side-channel-hardened implementation can be defeated by a protocol downgrade. Defense in depth is not optional — it is the only viable strategy.

2. Mathematical Attacks on Lattice-Based Schemes

Lattice-based schemes (ML-KEM, ML-DSA, FN-DSA) derive their security from the hardness of lattice problems — specifically, the Learning With Errors (LWE) problem and its structured variants (Module-LWE, Ring-LWE, NTRU). The primary mathematical attack strategy against these schemes is lattice reduction: transforming a lattice basis into one with shorter vectors, ideally short enough to recover the secret key or decrypt a ciphertext.

2.1 The BKZ Algorithm and Its Variants

The Block Kravchuk-Zolotarev (BKZ) algorithm, introduced by Schnorr and Euchner in 1994, is the foundation of all practical lattice attacks. BKZ extends the classical LLL algorithm by processing the lattice in overlapping blocks of dimension beta (the block size), calling an exact Shortest Vector Problem (SVP) oracle within each block.

How BKZ works:

Start with an LLL-reduced basis
Select a block of beta consecutive basis vectors (a projected sublattice)
Solve exact SVP in that block (using enumeration or sieving)
Insert the short vector found back into the basis
Move to the next block and repeat
Continue cycling through the basis until no further improvement is made

The quality of the output basis depends critically on the block size beta. Larger blocks produce shorter vectors but at exponential cost — the SVP subroutine in dimension beta runs in time approximately 2^(0.292 * beta) using the best known sieving algorithms (or 2^(0.265 * beta) using quantum sieving via Grover speedups on classical sieving).

BKZ 2.0 (Chen and Nguyen, 2011) introduced several practical improvements:

Early termination heuristics — stop when the basis stops improving measurably
Recursive preprocessing — use BKZ with a smaller block size to preprocess each block before solving SVP, reducing the effective cost of the SVP call
Pruned enumeration — use extreme pruning strategies (Gama, Nguyen, Regev, 2010) to speed up the SVP oracle at the cost of making it probabilistic
Dimension-for-free optimization — exploit the fact that the first few vectors of a BKZ-reduced basis are typically shorter than the Gaussian heuristic predicts, effectively gaining several dimensions of reduction “for free”

Progressive BKZ further refines the approach by gradually increasing the block size during execution, starting with small (cheap) blocks and progressing to larger (expensive) ones. This avoids wasting computation on large-block-size SVP calls early in the reduction when the basis is still far from reduced.

In practice, the BKZ hierarchy looks like this:

LLL  →  BKZ (original)  →  BKZ 2.0  →  Progressive BKZ
                                              ↓
                                    Current best classical
                                    lattice attack methodology

2.2 The Core-SVP Methodology

Core-SVP (core Shortest Vector Problem) is the standard methodology used by NIST and the cryptographic community to estimate the concrete security of lattice-based schemes. The approach works as follows:

Model the attack as BKZ. Determine the minimum BKZ block size beta required to recover the secret (either via the primal attack, dual attack, or a hybrid approach — see below).
Estimate the cost of each SVP oracle call. The cost of solving exact SVP in dimension beta is modeled as 2^(c * beta + o(beta)) for a constant c that depends on the algorithm used:
- Classical sieving: c = 0.292 (best known: list-decoding sieve, Becker-Ducas-Gama-Laarhoven 2016)
- Quantum sieving: c = 0.265 (Grover-speedup on classical sieving — Laarhoven 2015)
- Classical enumeration: c ≈ 0.187 × beta (superexponential — worse than sieving for large beta but competitive for small beta)
The Core-SVP cost is 2^(c * beta). This deliberately ignores polynomial factors, the number of BKZ tours, memory costs for sieving, and other sub-exponential factors. It is a conservative lower bound on the attacker’s cost.

The Core-SVP cost serves as the security level claim. For example, ML-KEM-768 targets NIST Security Level 3, meaning the best known attack (classical or quantum) requires at least Core-SVP effort comparable to 2^192 classical operations or the equivalent quantum work.

Important caveats with Core-SVP:

It is deliberately optimistic for the attacker (conservative for the defender): it undercounts the actual work required
It ignores memory costs, which are enormous for sieving algorithms (exponential in beta)
It assumes the attacker can make a single SVP call, ignoring the iterative nature of BKZ
Improvements to sieving algorithms directly impact Core-SVP estimates

2.3 The Primal Attack

The primal attack is the most straightforward lattice attack strategy against LWE-based schemes. Given a public key that encodes an LWE instance (A, b = As + e), the attacker constructs a lattice from the public matrix A and attempts to find the short error vector e (or the short secret s) using BKZ lattice reduction.

Specifically, the attacker builds a lattice from the matrix:

    ┌         ┐
    │  A  | I  │
L = │  q  | 0  │
    └         ┘

The target vector (e, s) is a short vector in (a shifted version of) this lattice. If BKZ with block size beta can find vectors short enough to recover e or s, the scheme is broken.

The required block size beta depends on the lattice dimension d, the modulus q, and the size of the secret/error distribution. For ML-KEM-768, the estimated required block size is approximately beta ≈ 850–900, which translates to a Core-SVP cost of roughly 2^(0.292 × 870) ≈ 2^254 classical operations — well above the targeted 192-bit security level.

2.4 The Dual Attack and the MATZOV Controversy

The dual attack takes a different approach. Instead of finding a short vector in the lattice (which would directly reveal the secret), the attacker finds a short vector in the dual lattice — a vector v such that v · A ≡ 0 (mod q). Such a vector acts as a “distinguisher”: computing v · b yields a value that is either uniformly random (if b is random) or has a small, biased distribution (if b = As + e for short s, e). By collecting enough such dual vectors, the attacker can distinguish LWE samples from random, and with further refinement, recover the secret.

The MATZOV paper (2022): In April 2022, a team from the Belgian MATZOV group (part of the Belgian military intelligence service) published a report claiming that a refined dual attack — combining dual lattice reduction with a “modulus switching” and “secret enumeration” strategy — significantly reduced the security estimates for NIST’s lattice-based schemes. Their key claims:

ML-KEM-512 (then called Kyber-512): security reduced to approximately 118 bits (below the 128-bit NIST Level 1 target)
ML-KEM-768: security reduced to approximately 183 bits (still above the 192-bit Level 3 target, but with reduced margin)
The improvement came from combining a dual-lattice distinguisher with FFT-based exhaustive search over a portion of the secret

The community response was vigorous and ultimately skeptical:

Ducas and Pulles (2023) showed that the MATZOV analysis relied on independence assumptions that do not hold in practice. Specifically, the dual attack’s distinguishing advantage is computed by assuming that certain quantities are independent, but Ducas and Pulles demonstrated that the actual advantage is significantly lower when correlations are properly accounted for.
The “average vs. worst case” issue: The MATZOV estimates computed the expected advantage of the distinguisher averaged over secret choices. Ducas and Pulles argued that the correct quantity is the advantage for any specific secret — and this is substantially smaller.
NIST’s response: NIST acknowledged the MATZOV work but ultimately did not change the security level claims for ML-KEM. In their final standard (FIPS 203), NIST stated that the primal attack remains the most relevant threat and that the dual attack advantage claimed by MATZOV was overstated due to the flawed independence assumption.
The current consensus (as of 2025) is that the dual attack is not significantly better than the primal attack for the parameter sets chosen by NIST. The MATZOV controversy served as a valuable stress test but did not result in parameter changes.

This episode illustrates an important principle: security estimates for lattice-based cryptography are not settled science. They depend on modeling assumptions that are actively debated, and even small methodological differences can shift estimates by tens of bits. The community continues to refine these estimates, and cryptographic agility — the ability to update parameters or switch algorithms — remains essential. See Migration Strategies for practical guidance.

2.5 Algebraic Attacks on Structured Lattices

ML-KEM, ML-DSA, and FN-DSA do not use generic lattices. They use structured lattices — specifically, module lattices over polynomial rings like Z_q[X]/(X^n + 1). This algebraic structure enables efficient implementations (operations become polynomial multiplications, computable via NTT in O(n log n) time) but also raises a persistent concern: does the structure help the attacker?

The known algebraic attacks against structured lattices include:

Ideal lattice attacks: For Ring-LWE (used in FN-DSA’s NTRU structure), the algebraic structure of ideal lattices allows the use of the principal ideal SVP algorithm. For cyclotomic fields of conductor that is a prime power (which includes the rings used in NIST standards), the best known algebraic attacks (Cramer, Ducas, Peikert, Regev 2016; Cramer, Ducas, Wesolowski 2017) can find moderately short vectors in ideal lattices faster than in generic lattices — but only by a sub-exponential factor. Concretely, the speedup is approximately 2^(n^(1/2)) over generic lattice algorithms, which is vastly insufficient to threaten the NIST parameter choices (which have security margins of 2^50 or more above the relevant thresholds).
Module structure exploitation: ML-KEM and ML-DSA use Module-LWE, where the module rank k provides an additional security parameter. No known attack exploits the module structure beyond what is already captured by reducing Module-LWE to Ring-LWE (which adds a factor of k to the effective dimension).
Overstretched NTRU: For NTRU-based schemes (like FN-DSA), if the modulus q is too large relative to the dimension n (i.e., the parameters are “overstretched”), a subfield attack (Albrecht, Bai, Ducas 2016) can exploit the algebraic structure to find short vectors faster. The FN-DSA parameters are specifically chosen to avoid this regime.

Bottom line: As of 2025, no algebraic attack fundamentally breaks the security of the NIST lattice-based standards. The structured lattice concern has motivated a cautious approach — NIST chose conservative parameters with substantial security margins — and the inclusion of hash-based SLH-DSA as a standard provides a fallback if algebraic attacks improve.

2.6 Information Set Decoding (ISD) for Code-Based Schemes

Code-based cryptography (Classic McEliece, HQC) relies on the hardness of decoding a random linear code — a problem that has resisted efficient solutions for over 60 years. The primary classical attack family is Information Set Decoding (ISD).

How ISD works:

Given a syndrome decoding problem — find a word of weight t that maps to a given syndrome under a parity-check matrix H — ISD proceeds by:

Guess a set of k positions (an “information set”) that contain no error positions
Invert the corresponding submatrix of H to recover a candidate error vector
Check whether the candidate has the correct weight

The probability that a random information set is error-free is approximately (1 - t/n)^k, which is exponentially small for interesting parameters. The art of ISD is in improving the success probability per iteration and reducing the cost per iteration.

Evolution of ISD algorithms:

Algorithm	Year	Key Innovation	Asymptotic Exponent
Prange	1962	Basic information set decoding	0.1207
Lee-Brickell	1988	Add small weight to information set	0.1164
Stern	1989	Birthday-based collision search	0.1059
Dumer	1991	Generalized Stern splitting	0.1048
MMT	2011	Multi-level collision matching	0.0494 (for specific parameters)
BJMM	2012	Nearest neighbor search + representations	0.0473 (for specific parameters)
May-Ozerov	2015	Nearest neighbor with locality-sensitive filtering	Improved constant
Both-May	2018	Depth-2 nearest neighbor	Best known classical

(Asymptotic exponents are for specific parameter regimes and code rates; they are not directly comparable across all parameters.)

Quantum ISD: Applying Grover’s algorithm to ISD provides a quadratic speedup on the search component, but the overall speedup is less than quadratic because ISD also involves significant linear algebra. The best quantum ISD analyses (Kachigar-Tillich 2017, Perriello-Barenghi-Pelosi 2021) suggest that quantum speedups against code-based schemes are modest — roughly halving the security level in bits — which is already accounted for in the parameter choices for Classic McEliece and HQC.

For HQC specifically (NIST’s selected code-based KEM), the quasi-cyclic structure introduces the same type of concern as structured lattices: does the structure help? Current analysis suggests not, as the quasi-cyclic structure does not provide known shortcuts beyond generic ISD. See Code-Based Cryptography for the mathematical details of these schemes.

Classic McEliece’s exceptional security posture: The McEliece cryptosystem (1978) uses binary Goppa codes, and its security has been studied for over 45 years. Despite this extraordinary scrutiny, the best known attack remains generic ISD — no structural attack exploiting the Goppa code structure has improved on it. This gives Classic McEliece arguably the highest confidence of any PQC scheme, at the cost of very large public keys (ranging from 261 KB to 1.3 MB depending on the security level).

2.7 The Lattice Estimator: Practical Security Assessment

The Lattice Estimator (formerly lattice-estimator, maintained by Albrecht et al.) is an open-source tool that automates the process of estimating the concrete security of lattice-based schemes. It implements all major attack strategies — primal, dual, hybrid, and algebraic — against LWE, NTRU, and related problems.

The Lattice Estimator is the de facto standard tool used by:

NIST for evaluating candidate submissions
Scheme designers for parameter selection
Cryptanalysts for benchmarking new attack techniques

How to interpret Lattice Estimator output:

The tool reports the estimated cost of the best known attack for each strategy, in terms of:

rop (ring operations): the total number of arithmetic operations
mem (memory): the memory required in bits
beta (block size): the BKZ block size required
d (lattice dimension): the dimension of the lattice used in the attack

The minimum over all strategies gives the estimated security level. For ML-KEM-768, a typical Lattice Estimator run produces:

Primal attack:   rop = 2^189.5,  beta = 851,  d = 1536
Dual attack:     rop = 2^193.2,  beta = 867,  d = 1536

This confirms that the primal attack is slightly more efficient than the dual attack for these parameters, and the security level is approximately 189–193 bits (well above the 192-bit NIST Level 3 target when accounting for the Core-SVP convention).

Caution: The Lattice Estimator’s output depends on the modeling assumptions built into the tool. As the MATZOV controversy demonstrated, different modeling choices (especially for the dual attack) can produce significantly different estimates. The Estimator is a valuable benchmarking tool, not an oracle. Cross-referencing its output with independent analyses and recent publications is essential for high-stakes security decisions.

3. Case Studies of Broken Schemes

The history of PQC is punctuated by spectacular breaks that remind the community of the gap between theoretical security arguments and cryptanalytic reality. Two cases stand out for their impact and the lessons they offer.

3.1 SIKE/SIDH: From NIST Finalist to Total Break

SIKE (Supersingular Isogeny Key Encapsulation) was one of the most theoretically elegant post-quantum proposals. Built on the Supersingular Isogeny Diffie-Hellman (SIDH) protocol proposed by Jao and De Feo in 2011, SIKE offered the smallest key sizes and ciphertexts of any PQC candidate — just a few hundred bytes — making it extremely attractive for bandwidth-constrained applications.

SIKE advanced to the fourth round of NIST’s PQC standardization as one of four finalists under consideration for a second KEM standard alongside Kyber (now ML-KEM). It had been studied for over a decade. Multiple teams had analyzed its security. It appeared to rest on a genuinely hard problem.

The break (July-August 2022):

On July 30, 2022, Wouter Castryck and Thomas Decru posted a preprint titled “An efficient key recovery attack on SIDH.” The paper demonstrated a polynomial-time attack that completely broke SIDH (and therefore SIKE) for all standardized parameter sets.

How the attack works:

The fundamental vulnerability was that SIDH reveals too much auxiliary information. To enable the key exchange, SIDH publishes the images of certain torsion points under the secret isogeny. Castryck and Decru showed that this auxiliary information — combined with a deep result from arithmetic geometry known as Kani’s theorem (1997) — allows the attacker to reconstruct the secret isogeny.

Kani’s theorem relates isogenies between elliptic curves to isogenies between products of elliptic curves (abelian surfaces). The key insight was:

The published torsion point images define a relationship between elliptic curves that can be “lifted” to a relationship between abelian surfaces
This higher-dimensional relationship corresponds to an isogeny between products of elliptic curves
The higher-dimensional isogeny can be efficiently computed using existing algorithms for abelian surfaces
The secret isogeny can then be recovered from the higher-dimensional computation

Timeline:

Date	Event
2011	SIDH proposed by Jao and De Feo
2017	SIKE submitted to NIST PQC Round 1
2019	SIKE advances to Round 2
2020	SIKE advances to Round 3
2022 (Mar)	SIKE advances to Round 4 as alternate KEM candidate
2022 (Jul 30)	Castryck-Decru preprint posted
2022 (Aug 1)	Maino-Martindale independent attack posted
2022 (Aug 5)	Robert generalizes the attack
2022 (Aug 5)	Working SageMath implementation breaks SIKEp434 in minutes on a laptop
2022 (Oct)	NIST officially removes SIKE from consideration

The speed of the collapse was breathtaking. Within a week of the initial preprint, multiple independent teams had reproduced the attack, generalized it, and demonstrated practical implementations that broke SIKE parameters in minutes. A scheme that had survived a decade of analysis was completely destroyed in days.

Lessons from SIKE:

Auxiliary information is dangerous. SIDH’s publication of torsion point images was known to be a potential concern, but the community underestimated how severely it could be exploited.
Connections to other areas of mathematics matter. The attack came from arithmetic geometry (Kani’s theorem), not from the isogeny-walking or endomorphism ring computation techniques that the community had been analyzing. The “unknown unknown” — an attack from an unexpected mathematical direction — is a real threat.
Young hard problems are risky. The supersingular isogeny problem had been studied for far less time than lattice problems, factoring, or coding theory. A decade of analysis is not enough to establish confidence comparable to problems studied for 40+ years.
Small key sizes are not free. SIKE’s remarkably compact parameters were a consequence of the mathematical structure that also made the attack possible. When parameters look “too good to be true” compared to other PQC families, this should prompt additional scrutiny.

For more on isogeny-based cryptography and SIKE’s position in the broader PQC landscape, see Other PQC Families & Broken Schemes.

3.2 Rainbow: The Rectangular MinRank Attack

Rainbow was a multivariate polynomial signature scheme based on the Oil and Vinegar construction (see Other PQC Families & Broken Schemes for background). It was selected as one of NIST’s Round 3 finalists for digital signatures, alongside ML-DSA and SLH-DSA. Rainbow offered extremely fast signature verification and compact signatures.

The break (February 2022):

Ward Beullens published a preprint showing that Rainbow’s layered structure — the multi-layer Oil and Vinegar construction that gave it compact parameters — could be exploited via a rectangular MinRank attack.

How the attack works:

The MinRank problem asks: given a set of matrices M_1, …, M_k, find a non-trivial linear combination c_1 M_1 + … + c_k M_k that has rank at most r. For generic matrices, MinRank is NP-hard. But Rainbow’s layered structure produces matrices with highly constrained rank structure.

Beullens’ key observations:

Rainbow’s public key, viewed as a set of quadratic forms, corresponds to matrices where the layered Oil-Vinegar structure imposes strong rank constraints
By considering “rectangular” submatrices (not the full square matrix representation), the rank deficiency becomes more pronounced and easier to exploit
The rectangular MinRank instance derived from Rainbow’s public key can be solved in significantly less time than the security claims assumed — approximately 2^53 operations for Rainbow’s Level I parameters, which targeted 128-bit security

Impact and timeline:

Date	Event
2005	Rainbow proposed by Ding and Schmidt
2017	Rainbow submitted to NIST PQC Round 1
2020	Rainbow advances to Round 3 as signature finalist
2022 (Feb 14)	Beullens posts rectangular MinRank attack preprint
2022 (Feb 21)	Multiple teams confirm and reproduce the attack
2022 (Mar)	Beullens demonstrates key recovery for all parameter sets in hours
2022 (Oct)	NIST officially removes Rainbow from standardization

Beullens demonstrated a practical key-recovery attack against all three Rainbow parameter sets. The attack recovered the secret key in approximately 53 hours for Rainbow Level I (targeting 128-bit security) on a standard laptop. NIST subsequently removed Rainbow from the standardization process.

Lessons from Rainbow:

Layered structure introduced exploitable regularity. Plain UOV (Unbalanced Oil and Vinegar) has survived 25+ years of analysis. Rainbow’s multi-layer extension, which was introduced to improve parameters, also introduced the structure that enabled the attack. Optimization of parameters can reduce security margins in subtle ways.
The MinRank problem is not as hard as believed for structured instances. The generic MinRank problem is NP-hard, but the specific instances arising from Rainbow had exploitable structure. This is a recurring theme in PQC: security reductions to NP-hard problems provide limited guarantees when specific instances have additional structure.
Signature schemes face different attack surfaces than KEMs. The public key of a signature scheme is used directly and repeatedly; an attacker has unlimited access to it. This makes key-recovery attacks (like MinRank) particularly dangerous for signature schemes.

3.3 What Breaks Teach Us About Security Margins

Both SIKE and Rainbow were broken not by incremental improvements to known attack classes, but by qualitatively new attacks that exploited structural properties the community had not previously considered exploitable. This has important implications:

Conservative parameter choices matter. Schemes with large security margins (like ML-KEM, which has 50+ bits of margin above NIST thresholds) can absorb significant improvements in attack methodology. SIKE and Rainbow had tighter margins.
Diversity of hardness assumptions matters. This is why NIST standardized algorithms from multiple families: lattice-based (ML-KEM, ML-DSA, FN-DSA), hash-based (SLH-DSA), and code-based (HQC). If one family falls, others may survive.
Mathematical maturity of the underlying problem matters. Lattice problems have been studied since the 1980s (LLL algorithm, 1982). The decoding problem for linear codes dates to the 1960s. The specific isogeny problem exploited in SIKE was studied only since 2011. Time in the cryptanalytic spotlight is a meaningful, if imperfect, indicator of security.

4. Side-Channel Attacks

Side-channel attacks exploit physical characteristics of a cryptographic implementation — timing, power consumption, electromagnetic emanation, cache behavior — to extract secret information. PQC algorithms introduce new side-channel attack surfaces that do not exist in classical RSA or ECC implementations.

4.1 Side-Channel Attack Surfaces by Algorithm

graph LR
    subgraph "ML-KEM Side Channels"
        A1["NTT Butterfly<br/>Timing"] --> A2["Secret-Dependent<br/>Branching"]
        A3["Decapsulation<br/>Comparison"] --> A4["Power Trace<br/>Leakage"]
        A5["Noise Sampling<br/>CBD"] --> A6["Distribution<br/>Leakage"]
    end

    subgraph "ML-DSA Side Channels"
        B1["Rejection Sampling<br/>Loop Count"] --> B2["Nonce/Secret<br/>Correlation"]
        B3["NTT Operations"] --> B4["Timing<br/>Variation"]
        B5["Hint Vector<br/>Computation"] --> B6["Power<br/>Analysis"]
    end

    subgraph "FN-DSA Side Channels"
        C1["Floating-Point<br/>Arithmetic"] --> C2["FP Exception<br/>Timing"]
        C3["Gaussian Sampling<br/>CDT/Ziggurat"] --> C4["Branch<br/>Prediction"]
        C5["Tree-Based<br/>Sampling"] --> C6["Cache Access<br/>Pattern"]
    end

    subgraph "SLH-DSA Side Channels"
        D1["Hash Chain<br/>Length"] --> D2["Timing<br/>Variation"]
        D3["WOTS+ Chain<br/>Position"] --> D4["Power<br/>Correlation"]
        D5["FORS Tree<br/>Access"] --> D6["Cache<br/>Pattern"]
    end

    style A1 fill:#1a1a2e,stroke:#e94560,color:#eee
    style A3 fill:#1a1a2e,stroke:#e94560,color:#eee
    style A5 fill:#1a1a2e,stroke:#e94560,color:#eee
    style B1 fill:#1a1a2e,stroke:#e94560,color:#eee
    style B3 fill:#1a1a2e,stroke:#e94560,color:#eee
    style B5 fill:#1a1a2e,stroke:#e94560,color:#eee
    style C1 fill:#1a1a2e,stroke:#e94560,color:#eee
    style C3 fill:#1a1a2e,stroke:#e94560,color:#eee
    style C5 fill:#1a1a2e,stroke:#e94560,color:#eee
    style D1 fill:#1a1a2e,stroke:#e94560,color:#eee
    style D3 fill:#1a1a2e,stroke:#e94560,color:#eee
    style D5 fill:#1a1a2e,stroke:#e94560,color:#eee
    style A2 fill:#16213e,stroke:#0f3460,color:#aaa
    style A4 fill:#16213e,stroke:#0f3460,color:#aaa
    style A6 fill:#16213e,stroke:#0f3460,color:#aaa
    style B2 fill:#16213e,stroke:#0f3460,color:#aaa
    style B4 fill:#16213e,stroke:#0f3460,color:#aaa
    style B6 fill:#16213e,stroke:#0f3460,color:#aaa
    style C2 fill:#16213e,stroke:#0f3460,color:#aaa
    style C4 fill:#16213e,stroke:#0f3460,color:#aaa
    style C6 fill:#16213e,stroke:#0f3460,color:#aaa
    style D2 fill:#16213e,stroke:#0f3460,color:#aaa
    style D4 fill:#16213e,stroke:#0f3460,color:#aaa
    style D6 fill:#16213e,stroke:#0f3460,color:#aaa

4.2 Detailed Side-Channel Analysis

The following table summarizes the known side-channel attacks, their severity, and the required countermeasures for each NIST-standardized PQC algorithm.

Algorithm	Attack Type	Specific Vulnerability	Severity	Countermeasure
ML-KEM	Timing	NTT butterfly operations with secret-dependent modular reductions	High	Constant-time NTT implementation; avoid conditional reduction
ML-KEM	Power (SPA)	Decapsulation re-encryption comparison leaks validity of ciphertext	High	Constant-time comparison (Fujisaki-Okamoto implicit rejection)
ML-KEM	Power (DPA)	Centered Binomial Distribution (CBD) sampling correlates with secret coefficients	Medium	Masked sampling; shuffled coefficient order
ML-KEM	Cache	NTT twiddle factor table lookups	Medium	Preload tables into cache; bit-sliced implementation
ML-DSA	Timing	Rejection sampling loop iteration count depends on secret key and nonce	Critical	Constant-time rejection loop (pad to max iterations); sample in constant number of steps
ML-DSA	Nonce reuse	Reusing nonce with same key leaks secret key algebraically (not a side channel per se, but often caused by side-channel-induced nonce bias)	Critical	RFC 6979-style deterministic nonce derivation with hedging; hardware RNG contribution
ML-DSA	Power (DPA)	Polynomial multiplication with secret polynomials during signing	High	First-order masking of NTT; randomized execution order
SLH-DSA	Timing	WOTS+ chain computation length depends on message hash value	Medium	Constant-time chain computation (always compute full chain, discard extra)
SLH-DSA	Cache	FORS tree leaf access pattern reveals selected leaves	Medium	Oblivious memory access; all-leaf precomputation
SLH-DSA	Power	Hash function calls correlate with internal state	Low	Masked hash implementation (expensive for SHA-256/SHAKE)
FN-DSA	Floating-point	Discrete Gaussian sampling uses floating-point arithmetic; FP operations have data-dependent timing on most CPUs	Critical	Integer-only sampler (eliminates FP entirely); constant-time FP emulation
FN-DSA	Branch prediction	Tree-based sampling (CDT tables, lazy sampling) has secret-dependent branches	Critical	Constant-time table lookup; oblivious sampling
FN-DSA	Cache	Lookup tables for Gaussian sampling are accessed at secret-dependent indices	High	Bit-sliced implementation; full table scan with conditional moves
FN-DSA	Power (SPA)	FFT operations during signature generation with secret key	High	Masked FFT; randomized butterfly order

4.3 ML-KEM: Timing and Power Analysis

ML-KEM’s primary side-channel concern is in the decapsulation operation. The Fujisaki-Okamoto (FO) transform used to convert the underlying CPA-secure public-key encryption scheme into a CCA-secure KEM requires:

Decrypting the ciphertext to recover the plaintext message m’
Re-encrypting m’ to obtain a reference ciphertext c’
Comparing c with c’ in constant time
If they match, deriving the shared secret from m’; if not, deriving a “dummy” shared secret from a secret rejection key

Steps 3 and 4 must be constant-time. If an attacker can distinguish the “accept” path from the “reject” path — through timing, power, or electromagnetic emanation — they can mount an adaptive chosen-ciphertext attack that recovers the secret key one coefficient at a time.

The NTT (Number Theoretic Transform) is the other major attack surface. ML-KEM uses NTT for polynomial multiplication, and the butterfly operations involve modular reductions that can be data-dependent on some architectures. Barrett or Montgomery reduction implementations must be carefully validated to ensure constant-time behavior across all possible inputs.

Countermeasures: The reference implementations of ML-KEM (as standardized in FIPS 203) are designed to be constant-time. However, constant-time behavior depends on the target architecture — compiler optimizations, CPU microarchitecture, and speculative execution can all reintroduce timing variability. Verification tools like ctgrind (based on Valgrind) and timecop can detect timing leaks but are not foolproof. For high-assurance deployments, formal verification of constant-time properties (e.g., using Jasmin/EasyCrypt) is recommended.

4.4 ML-DSA: Rejection Sampling Leakage

ML-DSA’s signing procedure uses rejection sampling: after computing a candidate signature, the algorithm checks whether the signature would leak information about the secret key (specifically, whether the masking vector y is sufficiently large relative to the secret key contribution). If the check fails, the algorithm rejects the candidate and tries again with a fresh random nonce.

The number of rejection iterations is secret-dependent. On average, ML-DSA-65 requires approximately 5.1 signing attempts per signature. An attacker who can observe the number of iterations (through timing, power traces, or electromagnetic emanation) gains partial information about the secret key. Over many signatures, this information accumulates and can enable key recovery.

The nonce reuse catastrophe: If an implementation is induced to sign the same message with the same nonce (for example, through a fault injection that resets the RNG state), ML-DSA’s algebraic structure allows immediate secret key recovery from two signatures with the same nonce — identical to the ECDSA nonce reuse vulnerability that compromised PlayStation 3’s code signing. This is not hypothetical; it motivates the use of deterministic nonce derivation (where the nonce is derived from the secret key and message hash) hedged with randomness from a hardware RNG.

4.5 FN-DSA: The Floating-Point Danger

FN-DSA (Falcon) is the most side-channel-dangerous of the NIST PQC standards. Its signing procedure requires sampling from a discrete Gaussian distribution over a lattice — and the standard way to do this involves floating-point arithmetic.

The problem: floating-point operations on essentially all modern CPUs are not constant-time. Subnormal numbers (numbers very close to zero) trigger different microarchitectural paths than normal numbers. Different exponent ranges may have different latencies. Floating-point exceptions (overflow, underflow, inexact) can introduce timing variations. On x86 processors, the transition between SSE and x87 floating-point modes has measurable timing differences.

In FN-DSA, the Gaussian sampling process involves computing values like exp(-x^2 / (2 * sigma^2)) where x depends on the secret key. If the floating-point computation of this exponential leaks timing information about x, the attacker can recover the secret key.

This is not a theoretical concern. Multiple research papers have demonstrated practical side-channel key recovery against Falcon implementations:

Guerreau et al. (2022) demonstrated electromagnetic side-channel key recovery against a Falcon implementation on an ARM Cortex-M4
Karmakar et al. (2023) showed power analysis attacks against the floating-point sampler

Countermeasures:

Replace floating-point with integer arithmetic entirely. This is the recommended approach. Several constant-time integer-only Gaussian samplers have been developed for FN-DSA, including the sampler by Thomas Prest (2023) and the implementation in PQClean.
Mask the sampling process. Split the secret values into shares and sample independently for each share, combining the results. This increases computational cost but prevents single-trace attacks.
Avoid FN-DSA if possible. For applications where ML-DSA’s larger signatures are acceptable, ML-DSA is significantly easier to implement securely. FN-DSA’s advantages (smaller signatures) come with a substantial side-channel implementation burden.

5. Implementation Attacks

Implementation attacks go beyond passive observation of side channels. They actively manipulate the device or its environment to induce faulty behavior that leaks secrets.

5.1 Fault Injection Attacks

Fault injection attacks corrupt a computation at a precise moment to cause the device to output erroneous results that reveal information about the secret key.

Fault injection methods:

Method	Mechanism	Precision	Cost	Typical Target
Voltage glitching	Momentarily drop or spike the supply voltage	Cycle-level	$100–$1,000 (ChipWhisperer)	Microcontrollers, embedded SoCs
Clock glitching	Insert extra clock edges or shorten clock periods	Cycle-level	$100–$1,000	Synchronous digital circuits
Electromagnetic (EM) pulse	Focused EM pulse induces transient currents	~1mm spatial	$10,000–$50,000	Specific functional units on chip
Laser fault injection (LFI)	Focused laser beam flips bits in SRAM or registers	~1um spatial	$50,000–$500,000	Individual transistors, SRAM cells
Rowhammer	Repeated DRAM row access causes bit flips in adjacent rows	Row-level	$0 (software only)	DRAM-based systems (servers, desktops)

Fault attacks against ML-KEM:

The most dangerous fault attack against ML-KEM targets the decapsulation comparison. The FO transform’s security depends on the device correctly comparing the re-encrypted ciphertext with the received ciphertext. If a fault causes this comparison to always report “equal” (skipping the comparison), the attacker can submit malformed ciphertexts and use the resulting (incorrect) shared secrets to recover the secret key through an adaptive chosen-ciphertext attack.

Specifically:

The attacker sends a deliberately malformed ciphertext c* to the decapsulation oracle
A fault injection causes the FO comparison to be skipped — the device treats c* as valid
The device returns a shared secret derived from the “decrypted” message, rather than the rejection secret
By carefully constructing c* and observing the shared secret, the attacker learns information about the secret key
After O(n) adaptive queries, the full secret key is recovered

Countermeasures:

Double computation: Perform the decapsulation and comparison twice, using different code paths or instruction sequences, and check that both results agree
Instruction counter verification: Use hardware performance counters or watchdog timers to verify that the expected number of instructions were executed
Error-detecting codes (EDCs): Protect intermediate values with redundancy codes; any fault that corrupts a protected value is detected
Physical countermeasures: Voltage and clock monitoring circuits, light sensors (for laser FI), EM shielding

Rowhammer against PQC in software: Rowhammer is particularly relevant for server-side PQC deployments. If ML-KEM decapsulation runs on a server with DRAM-based key storage, an attacker co-located on the same physical machine can use Rowhammer to flip bits in the stored secret key. Even a single bit flip in the secret polynomial can enable a key-recovery attack. Mitigation: store secret keys in ECC-protected memory, or use integrity checks on the secret key before each use.

5.2 Timing Leaks in Comparison Operations

Beyond the FO comparison, PQC implementations contain many comparison operations that must be constant-time:

Polynomial coefficient comparison in ML-DSA’s rejection sampling (checking whether ||z||_inf < gamma_1 - beta)
Checksum verification in hash-based signatures
Decoding validity checks in code-based schemes (HQC)

A common implementation error is using early-exit comparison functions (like C’s memcmp) that return as soon as a mismatch is found. This leaks the position of the first different byte, which can be exploited over many queries.

Constant-time comparison pattern (C):

int constant_time_compare(const uint8_t *a, const uint8_t *b, size_t len) {
    volatile uint8_t result = 0;
    for (size_t i = 0; i < len; i++) {
        result |= a[i] ^ b[i];
    }
    return (1 & ((result - 1) >> 8)) - 1;
    // Returns 0 if equal, -1 if not equal
}

Even this pattern can fail if the compiler “optimizes” it into an early-exit loop. Using volatile qualifiers, compiler barriers, or assembly implementations is essential.

5.3 Cache-Timing Attacks

Cache-timing attacks exploit the fact that memory accesses that hit in the CPU cache are faster than those that miss. If a cryptographic implementation accesses memory at secret-dependent addresses (e.g., table lookups indexed by secret values), an attacker who shares the cache (same physical core, or adjacent core sharing L2/L3) can determine which addresses were accessed.

PQC-specific cache-timing concerns:

NTT twiddle factor tables: ML-KEM and ML-DSA use precomputed twiddle factors for the NTT. If these tables are large enough to span multiple cache lines, the access pattern reveals which butterfly operations were performed with which factors — potentially leaking secret coefficients.
Gaussian sampling tables in FN-DSA: The CDT (cumulative distribution table) sampler accesses a table at positions determined by a random value compared against the secret. The access pattern directly reveals the sampled value.
FORS leaf selection in SLH-DSA: SLH-DSA’s FORS (Forest of Random Subsets) component selects leaves from multiple small Merkle trees. The selected leaf indices depend on the message hash and are part of the signature, but during computation, the access pattern to the tree data structure can leak information about the internal state.

Countermeasures:

Bit-sliced implementations: Represent table lookups as Boolean circuits operating on individual bits, eliminating secret-dependent memory access entirely. This is the gold standard for cache-timing resistance.
Full table scans with conditional moves: Always read every entry in the table, using conditional move instructions (CMOV on x86) to select the correct entry. This ensures every table entry is loaded into cache regardless of the secret.
Cache partitioning: On platforms that support it (e.g., Intel CAT — Cache Allocation Technology), dedicate cache partitions to cryptographic operations to prevent cross-process cache interference.

5.4 Key Mismatch Attacks on KEMs

A key mismatch attack exploits the situation where two parties perform a KEM key exchange but end up with different shared secrets (a “mismatch”). By observing whether a mismatch occurred — often possible through timing differences in subsequent protocol steps — an attacker can recover the secret key bit by bit.

How it works against ML-KEM (without FO transform):

The attacker constructs a specially crafted ciphertext that, when decrypted, produces a result that depends on a single coefficient of the secret key
The attacker sends this ciphertext and observes whether the resulting shared secret matches (indicating the guessed coefficient value was correct) or mismatches
By repeating with different crafted ciphertexts, the attacker recovers the full secret key

The Fujisaki-Okamoto transform is specifically designed to prevent this attack: the re-encryption check ensures that any malformed ciphertext is rejected, and the “implicit rejection” mechanism ensures that the rejection path is indistinguishable from the acceptance path (from the attacker’s perspective). However, if the implementation has a side-channel leak in the FO comparison (Section 5.1), the key mismatch attack becomes viable again.

Key mismatch attacks have been demonstrated against:

Unprotected (CPA-secure) versions of Kyber/ML-KEM (Bauer et al., 2019)
NTRU implementations with imperfect FO transforms (Bindel et al., 2019)
HQC implementations where decoding failures are detectable (Guo et al., 2022)

6. Protocol-Level Attacks

Even a perfectly implemented, side-channel-hardened PQC algorithm can be defeated if the protocol that uses it has vulnerabilities. During the transition from classical to post-quantum cryptography, protocol-level attacks are among the most practical threats.

6.1 Downgrade Attacks

A downgrade attack forces a connection to use a weaker protocol version or cipher suite than both parties would otherwise negotiate. In the PQC transition context, this means forcing a connection to use classical (non-quantum-resistant) cryptography even when both parties support PQC.

How it works:

In TLS 1.3, the client sends a list of supported key exchange groups in the supported_groups extension, and the server selects one. If the client offers both PQC hybrid groups (e.g., X25519MLKEM768) and classical groups (e.g., X25519), a man-in-the-middle attacker can modify the ClientHello to remove the PQC options, forcing the server to select a classical group.

TLS 1.3’s design mitigates this through the Finished message, which includes a MAC over the entire handshake transcript. If the attacker modifies the ClientHello, the Finished messages will not match, and the handshake will fail. However:

TLS 1.2 and earlier versions do not have robust transcript binding and are vulnerable to downgrade attacks
Misconfigured implementations that fall back to TLS 1.2 when TLS 1.3 fails create a downgrade path
QUIC and other protocols may have different negotiation mechanisms with different downgrade resistance properties

Mitigation: Configure servers to reject non-PQC key exchange groups entirely once PQC deployment is confirmed. Use TLS 1.3 exclusively. Monitor for unexpected cipher suite selections in connection logs. See PQC in Protocols for detailed protocol configuration guidance.

6.2 Version Rollback

Version rollback is a specific type of downgrade attack that forces a connection to use an older protocol version. In the PQC context, this is dangerous because:

Older TLS versions (1.0, 1.1, 1.2) do not support PQC key exchange groups
Forcing a rollback to an older version automatically eliminates PQC protection
Many deployments maintain backward compatibility with older versions for legacy client support

TLS 1.3 includes a downgrade sentinel — the server inserts a specific value at the end of its Random field in the ServerHello when negotiating TLS 1.2 or below. A TLS 1.3-capable client that sees this sentinel knows that a downgrade has occurred. However, this only works if the client checks the sentinel — some implementations do not.

Mitigation: Disable TLS 1.0 and 1.1 entirely. Configure TLS 1.2 to only negotiate PQC-capable cipher suites where possible. Prefer TLS 1.3 exclusively for PQC-sensitive connections. Implement and verify downgrade sentinel checking.

6.3 Hybrid Mode Stripping

Hybrid cryptography combines classical and post-quantum algorithms so that the connection is secure as long as either algorithm is unbroken. Hybrid mode stripping attacks attempt to remove the post-quantum component, leaving only the classical algorithm.

Attack scenarios:

ClientHello modification: Strip the post-quantum component from the hybrid key share, leaving only the classical component. If the server accepts a non-hybrid classical group that the client also supports, the connection proceeds without PQC protection.
Key share truncation: In some hybrid implementations, the post-quantum and classical key shares are concatenated in a single extension. An attacker who understands the format can truncate the PQC portion while leaving the classical portion intact. If the implementation does not validate the key share length against the negotiated group, it may proceed with only the classical key exchange.
Certificate chain manipulation: In a hybrid PKI deployment where certificates contain both classical and PQC public keys, an attacker can strip the PQC key from the certificate. If the relying party accepts a certificate with only a classical key, the PQC signature verification is bypassed.

Mitigation: Use combined hybrid key exchange groups (where the PQC and classical components are inseparable in the negotiation) rather than composite approaches. Validate key share lengths strictly. Require PQC signatures in certificate chains. See Hybrid Cryptography for implementation guidance.

6.4 Certificate Substitution

During the PQC transition, PKI deployments will contain a mix of classical and PQC certificates. A certificate substitution attack exploits this heterogeneity:

A legitimate server has both a classical (RSA/ECDSA) certificate and a PQC (ML-DSA) certificate
An attacker who has compromised the classical key (e.g., via a future quantum computer) intercepts a connection
The attacker substitutes the PQC certificate with the classical certificate
If the client accepts the classical certificate (because it is still within its validity period and chains to a trusted root), the connection proceeds with compromised authentication

This is particularly dangerous in the “harvest now, decrypt later” threat model: an adversary who records today’s handshakes may later obtain a quantum computer capable of breaking the classical key, then use the recorded classical certificate to mount a man-in-the-middle attack against recorded sessions.

Mitigation: Implement certificate transparency (CT) logging for PQC certificates. Configure clients to prefer PQC certificates when available. Use certificate binding mechanisms that tie the certificate choice to the key exchange (e.g., the selected key exchange group determines which certificate type is acceptable). Revoke classical certificates proactively as PQC certificates are deployed.

6.5 Replay and Oracle Attacks During Migration

The transition period introduces a unique window where systems may accept both classical and PQC credentials, creating oracle opportunities:

Cross-protocol replay: If a system accepts both classical TLS 1.2 sessions and PQC-enabled TLS 1.3 sessions, session tickets or resumption tokens from one protocol version may be replayed against the other if session management does not properly bind tokens to the negotiated parameters.
Algorithm confusion: If a system supports multiple PQC algorithms (e.g., both ML-KEM and HQC for key exchange), an attacker could attempt to present a ciphertext formatted for one algorithm as a ciphertext for another, exploiting differences in validation or error handling to create a distinguishing oracle.
Fallback oracle: If a server falls back from PQC to classical cryptography when PQC negotiation fails, an attacker can force fallback by injecting errors during the PQC key exchange, then exploit the classical key exchange. The attacker effectively uses the PQC negotiation failure as a trigger for downgrade.

Mitigation: Bind session tokens to the full set of negotiated parameters (protocol version, key exchange group, signature algorithm). Implement strict algorithm negotiation that does not fall back silently. Log and alert on negotiation failures that result in algorithm downgrades.

7. Comprehensive Attack Reference Table

The following table provides a consolidated reference of attacks across all categories, organized by algorithm.

Algorithm	Attack Category	Specific Attack	Impact	Difficulty	Mitigation
ML-KEM	Mathematical	Primal lattice attack (BKZ)	Key recovery	Infeasible at current parameters (>2^192)	Conservative parameter selection
ML-KEM	Mathematical	Dual attack (MATZOV variant)	Key recovery	Debated; likely no better than primal	Monitor research; cryptographic agility
ML-KEM	Side-channel	Timing in NTT	Partial key leak	Moderate (requires local access)	Constant-time NTT
ML-KEM	Side-channel	Power analysis on FO comparison	Key recovery	High (requires physical access)	Constant-time comparison; masking
ML-KEM	Implementation	FO fault injection	Key recovery	High (requires physical access + equipment)	Double computation; integrity checks
ML-KEM	Implementation	Key mismatch oracle	Key recovery	Moderate (requires CCA oracle leak)	Correct FO implementation; implicit rejection
ML-KEM	Implementation	Rowhammer on secret key	Key recovery	Moderate (co-located attacker)	ECC memory; key integrity checks
ML-KEM	Protocol	Downgrade to classical KEM	Loss of PQ protection	Low (network MITM)	TLS 1.3 only; strict group policy
ML-DSA	Mathematical	Primal lattice attack (BKZ)	Key recovery	Infeasible at current parameters	Conservative parameter selection
ML-DSA	Side-channel	Rejection sampling timing	Key recovery over many signatures	Moderate	Constant-time rejection loop
ML-DSA	Side-channel	Nonce reuse / nonce bias	Immediate key recovery	Critical if exploited	Deterministic nonce with hedging
ML-DSA	Side-channel	DPA on NTT with secret key	Key recovery	High (physical access)	Masked NTT
ML-DSA	Implementation	Fault during signing	Signature forgery; key leak	High (physical access)	Signature verification before output
SLH-DSA	Mathematical	Preimage/collision on hash	Forgery	Infeasible (hash security)	Use SHA-256 or SHAKE-256 at appropriate security level
SLH-DSA	Side-channel	WOTS+ chain timing	Partial state leak	Low (minimal exploitable info)	Constant-time chain computation
SLH-DSA	Side-channel	FORS cache access pattern	Leaf index leak	Medium	Oblivious memory access
SLH-DSA	Implementation	Fault in hash computation	Signature forgery	High (requires precise fault)	Redundant hash computation
FN-DSA	Mathematical	Primal attack on NTRU lattice	Key recovery	Infeasible at current parameters	Conservative parameters; avoid overstretched regime
FN-DSA	Side-channel	Floating-point timing	Key recovery	Critical (demonstrated practical attacks)	Integer-only sampler; avoid FP entirely
FN-DSA	Side-channel	Gaussian sampling cache timing	Key recovery	High	Bit-sliced sampler; constant-time table access
FN-DSA	Side-channel	EM emanation during FFT	Key recovery	High (demonstrated on ARM Cortex-M4)	Masked FFT; EM shielding
FN-DSA	Implementation	Fault in sampling	Biased signatures; key leak	High	Verify signature before output
HQC	Mathematical	ISD (BJMM variant)	Key recovery	Infeasible at current parameters (>2^128)	Conservative code parameters
HQC	Mathematical	Quantum ISD	Key recovery	Infeasible (halves security bits)	Parameters account for quantum speedup
HQC	Side-channel	Decoding timing	Partial key leak	Medium	Constant-time decoder
HQC	Implementation	Decoding failure oracle	Key recovery	Moderate (requires many queries)	Failure rate below 2^(-128)
All PQC	Protocol	Hybrid mode stripping	Loss of PQ protection	Low (network MITM)	Combined hybrid groups; strict validation
All PQC	Protocol	Certificate substitution	Authentication bypass	Moderate (requires compromised classical key)	CT logging; PQC certificate preference

8. Mitigations Summary

8.1 Against Mathematical Attacks

Use conservative parameters. The NIST-standardized parameter sets were chosen with substantial security margins. Do not use non-standard or reduced parameters in production.
Maintain cryptographic agility. If lattice reduction algorithms improve significantly, you need the ability to update parameters or switch algorithms without redesigning your system. See Migration Strategies.
Deploy algorithmic diversity. Use algorithms from different mathematical families for different purposes (e.g., ML-KEM for key exchange, SLH-DSA for long-term signatures). A breakthrough against lattices would not affect hash-based signatures.
Monitor the research community. Follow NIST’s post-standardization cryptanalysis efforts, the IACR ePrint archive, and major cryptography conferences (CRYPTO, EUROCRYPT, ASIACRYPT) for advances in lattice reduction, ISD, and algebraic attacks.

8.2 Against Side-Channel Attacks

Use audited, constant-time implementations. Prefer implementations that have been formally verified for constant-time behavior (e.g., those produced using Jasmin or verified with tools like ct-verif).
Apply masking for high-value targets. First-order (and potentially higher-order) masking prevents single-trace power/EM attacks. The performance overhead is significant (2-5x for first-order masking) but necessary for smart cards and embedded devices.
Avoid FN-DSA floating-point in production. Use integer-only Gaussian samplers, or prefer ML-DSA if signature size constraints allow.
Test with side-channel evaluation tools. Use Test Vector Leakage Assessment (TVLA) methodology, power analysis platforms (ChipWhisperer, Riscure Inspector), and timing analysis tools to evaluate implementations before deployment.

8.3 Against Implementation Attacks

Implement redundancy. Double-check critical computations (FO comparison, signature generation). Verify outputs before releasing them.
Protect key storage. Use ECC-protected memory, hardware security modules (HSMs), or trusted execution environments (TEEs) for secret key storage.
Validate all inputs. Check ciphertext lengths, public key formats, signature sizes, and all protocol fields before processing. Reject malformed inputs immediately.
Deploy fault countermeasures on embedded platforms. Voltage monitors, clock monitors, light sensors, and instruction flow integrity checks are essential for devices exposed to physical attackers.

8.4 Against Protocol-Level Attacks

Use TLS 1.3 exclusively for PQC-sensitive connections. Disable fallback to older versions.
Configure strict cipher suite policies. Once PQC key exchange is deployed, remove non-PQC groups from the server’s offered list.
Use combined hybrid modes where the classical and PQC components cannot be separated in negotiation.
Implement certificate transparency for PQC certificates and monitor for unauthorized issuance.
Plan for certificate lifecycle management. Proactively rotate from classical to PQC certificates and revoke classical certificates on a defined timeline. See PQC in Protocols for protocol-specific guidance.

9. The Evolving Threat Landscape

The attack landscape against PQC is not static. Several active research directions may change the balance:

Lattice reduction improvements: The sieving algorithms at the core of BKZ have seen incremental improvements over the past decade — from the GaussSieve (2010) to the HashSieve (2015) to the G6K framework (2019). Each improvement reduces the constant in the exponential running time. A hypothetical reduction of the classical sieving constant from 0.292 to 0.265 (the current quantum sieving constant) would reduce ML-KEM-768’s security estimate by approximately 25 bits — still above the NIST threshold, but significantly eroding the margin.

Key areas of active lattice reduction research include:

Memory-efficient sieving: Current sieving algorithms require exponential memory (approximately 2^(0.2075 * beta) vectors must be stored). Research into memory-efficient variants could make larger block sizes practical, but so far, memory-time tradeoffs have not produced asymptotic improvements.
Quantum sieving refinements: Combining Grover search with classical sieving databases is the basis of the 2^(0.265 * beta) quantum sieving estimate. More sophisticated quantum-classical hybrid sieving strategies could potentially improve this constant, though no concrete improvements have been demonstrated.
The G6K kernel: The General Sieve Kernel (G6K), developed by Albrecht et al. (2019), provides a unified framework for lattice sieving that subsumes previous algorithms. G6K-based implementations have set records for lattice challenges and provide the best practical attack implementations. Monitoring G6K improvements is essential for tracking the practical state of lattice attacks.

Quantum algorithms beyond Shor and Grover: The assumption that quantum computers only help through Shor’s algorithm (for factoring/discrete log) and Grover’s algorithm (for generic search) may prove too optimistic. New quantum algorithms that exploit the algebraic structure of lattice or code-based problems could shift the landscape. No such algorithms are known, but the field of quantum algorithms is young.

Several speculative directions deserve monitoring:

Quantum walks on lattice graphs: Quantum random walk algorithms could potentially speed up lattice enumeration, though no concrete advantage has been demonstrated for cryptographic dimensions.
Variational quantum algorithms: Near-term quantum devices running variational algorithms (VQE, QAOA) have been proposed for combinatorial optimization problems related to lattice SVP, but current hardware is far too noisy and small to be relevant.
Quantum speedups for algebraic attacks: If quantum computers can speed up Gröbner basis computation or other algebraic techniques, this could affect the security of structured lattice schemes. The relationship between quantum computation and algebraic geometry is an active research area.

AI-assisted cryptanalysis: Machine learning techniques have been applied to cryptanalysis with mixed results. Neural networks have been trained to distinguish LWE samples from random (Wenger et al., 2022), though so far only for parameters far smaller than those used in practice. As AI capabilities advance, AI-assisted attack strategies could potentially discover new attack patterns that human researchers have missed.

Specific AI-cryptanalysis results to date:

LWE distinguishing: Neural networks can distinguish LWE from uniform random for small parameters (n < 64, small modulus) but fail completely for cryptographic parameters. The gap between “toy” and “real” parameters remains vast.
Side-channel trace classification: Deep learning (CNNs, transformers) has proven highly effective at extracting keys from power and EM traces, often outperforming classical template attacks. This is the most immediately practical AI-assisted attack vector.
Automated vulnerability discovery: Fuzzing and symbolic execution augmented with ML have found implementation bugs in cryptographic libraries, though not fundamental algorithmic breaks.

Side-channel attack automation: Profiled side-channel attacks increasingly use deep learning to automatically extract secrets from power or EM traces without requiring manual leakage modeling. As these tools become more sophisticated and accessible, the bar for mounting side-channel attacks drops. Commercial tools like Riscure Inspector and Langer EMV-TechnoPartner now incorporate ML-based trace analysis as standard features, lowering the expertise required to mount sophisticated attacks.

Multi-target attacks and batch cryptanalysis: As PQC deployments scale to millions of users, multi-target attacks become relevant. An attacker targeting any one of N users benefits from a factor-of-N speedup in brute-force attacks. For lattice-based schemes, multi-target attacks are less straightforward than for symmetric primitives, but hybrid approaches combining lattice reduction with multi-target enumeration could reduce effective security margins for large-scale deployments. The NIST security level definitions explicitly account for multi-target scenarios, but implementations should be aware of this additional attack surface.

10. Practical Recommendations

For organizations deploying PQC today, the attack landscape informs several practical priorities:

Do not delay deployment waiting for “perfect” security. The NIST standards have survived extensive analysis. The risk of harvest-now-decrypt-later attacks (see Classical Cryptography at Risk) outweighs the residual risk from potential future cryptanalytic improvements.
Prioritize ML-KEM for key exchange. It has the strongest security margin among lattice-based schemes, the most extensive analysis, and the most mature constant-time implementations.
Choose ML-DSA over FN-DSA unless signature size is critical. FN-DSA’s smaller signatures come at the cost of significantly harder side-channel protection. ML-DSA is easier to implement securely.
Deploy SLH-DSA for long-term signatures (code signing, root certificates, firmware updates) where signature size is less important than confidence in long-term security. SLH-DSA’s security depends only on the hash function, providing maximum diversity against lattice-specific attacks.
Use hybrid cryptography during the transition. Combining classical and post-quantum algorithms ensures that a break of either component alone does not compromise security. See Hybrid Cryptography.
Invest in implementation quality. Use well-audited libraries (see Implementations and Libraries), run side-channel tests, and validate constant-time behavior on your specific target platform.
Build cryptographic agility into your architecture. The lessons from SIKE and Rainbow are clear: any scheme can be broken. Systems that can swap algorithms without architectural changes are resilient to future surprises. See Migration Strategies.
Conduct regular threat modeling. Map your deployment against the attack categories in this page. For each category, ask: (a) is this attack relevant to my threat model? (b) are mitigations in place? (c) how would I detect an active attack? Document the results and revisit them as the threat landscape evolves.
Establish a cryptanalytic monitoring process. Assign a team member or subscribe to a threat intelligence feed that tracks PQC cryptanalysis developments. Key sources include:
- The IACR ePrint archive (eprint.iacr.org) — preprints appear here first
- NIST’s PQC mailing list and status updates
- Major conference proceedings: CRYPTO, EUROCRYPT, ASIACRYPT, Real World Crypto
- The PQC Forum community discussions
- Vendor advisories from your PQC library providers
Plan incident response for cryptographic breaks. If a NIST-standardized PQC algorithm is broken (as SIKE and Rainbow were), your organization needs a response plan. This plan should include: identifying all systems using the affected algorithm, activating cryptographic agility mechanisms to switch algorithms, rotating affected keys, and communicating with stakeholders. The response timeline should be measured in days, not months — SIKE went from “secure” to “totally broken” in under a week.

11. Key Takeaways

The attack landscape against PQC is broad, multi-layered, and actively evolving. The core points for practitioners:

No PQC algorithm is unconditionally secure. Security is always conditional on hardness assumptions and correct implementation. The NIST standards represent the best available confidence, not certainty.
Mathematical attacks are well-understood but not settled. The MATZOV dual attack controversy shows that even the methodology for estimating security is debated. Conservative parameters provide essential buffer.
Side-channel attacks are the most immediate practical threat. Mathematical attacks against the NIST standards are currently infeasible. Side-channel attacks against careless implementations are very much feasible — and have been demonstrated against FN-DSA and ML-KEM on real hardware.
Protocol-level attacks bypass cryptography entirely. A perfect PQC implementation behind a downgradeable protocol is not quantum-resistant. Protocol configuration is as important as algorithm selection.
The breaks of SIKE and Rainbow are cautionary tales, not anomalies. They demonstrate that even years of analysis by expert cryptanalysts can miss fundamental vulnerabilities. Cryptographic agility is not optional.
Defense in depth is the only viable strategy. Combine conservative parameter choices, audited constant-time implementations, side-channel countermeasures, strict protocol configuration, and cryptographic agility to build resilient systems.

Previous: Implementations and Libraries — practical guidance on PQC libraries, reference implementations, and deployment considerations.