The Primal and Dual Attacks
The primal and dual attacks are the two concrete ways cryptographers actually try to solve Learning With Errors in practice. Both convert the noisy-equations problem into a lattice problem and then unleash a lattice-reduction algorithm on it, and the security of every deployed lattice scheme is estimated by working out how expensive each of these two attacks would be at the chosen parameters. The primal attack builds a lattice in which the LWE secret sits as an unusually short vector and hunts for it directly. The dual attack builds a different lattice, finds a short vector there, and uses it to tell real LWE samples apart from random noise. Neither breaks the standardized parameter sets, and the whole point of naming them is that the security estimate is the cost of the cheaper of the two.
Source: Martin R. Albrecht, Rachel Player & Sam Scott, “On the concrete hardness of Learning with Errors,” Journal of Mathematical Cryptology 9(3), 2015, ePrint 2015/046.
The short version:
- There are two attacks, and they are the whole menu. Every serious attempt to solve LWE via lattices is either a primal attack or a dual attack, so a scheme’s security estimate is the cost of whichever one is cheaper.
- The primal attack embeds LWE into a unique-shortest-vector problem. It builds a lattice where the secret and its noise form one abnormally short vector, then runs BKZ until that vector pops out.
- The dual attack works on the dual lattice. It finds short vectors in the dual, uses them to test whether a batch of samples was made with a real secret or drawn at random, and thereby solves the decision version of LWE.
- Both bottom out in lattice reduction. The expensive step in each is running BKZ with a large block size, so the attacks differ in setup and share the same engine.
- They set the parameters. Designers pick key sizes so that the cheaper of the two attacks costs more than the target security level, which is exactly what Core-SVP estimation measures.
Picture the noisy spreadsheet of LWE, where the secret is buried under small random errors. A lattice attack does not attack the spreadsheet directly. It rewrites the whole system as a grid of points in high-dimensional space, a lattice, arranged so that the answer you want corresponds to a point that is closer to the origin than any point has a right to be. The primal attack makes the secret itself that anomalously close point and reaches straight for it. The dual attack builds the mirror-image grid and finds a short point there instead, then uses that point as a ruler that reads “real secret” or “just noise.” Both then hand the grid to the same reduction machine and ask it to find the short vector. How long that machine has to run is the security of the scheme.
What is the primal attack on LWE?
The primal attack turns Learning With Errors into a single instance of the unique shortest vector problem, then solves that with lattice reduction. Starting from the public LWE data, you construct a lattice using a standard trick called Kannan’s embedding, which folds the noisy equations and their answers into one larger lattice built so that the LWE secret together with its error vector appears as a single short vector inside it. Because the noise is small by design, that embedded vector is much shorter than everything else in the lattice, which makes it the unique shortest vector and makes the problem a uSVP instance rather than a general search.
Source: Martin R. Albrecht, Rachel Player & Sam Scott, “On the concrete hardness of Learning with Errors,” 2015, ePrint 2015/046.
Once the LWE instance is dressed as a uSVP instance, the attack runs BKZ with a block size large enough to surface that short vector. The block size is the dial: a larger block size finds shorter vectors but costs vastly more, so the attacker picks the smallest block size that can still recover the embedded secret. Estimating the primal attack therefore reduces to one question, namely the smallest BKZ block size that succeeds, because that block size determines the running cost through the reduction algorithm. When a security analysis quotes a required block size for a parameter set, it is almost always the primal attack’s block size, since the primal attack is usually the cheaper of the two for the parameters the standards use.
What is the dual attack on LWE?
The dual attack solves the decision version of LWE by finding short vectors in the dual lattice. Every lattice has a companion lattice called its dual, and a short vector in the dual of the LWE lattice acts as a distinguisher. You take such a short dual vector and pair it against a batch of samples. If the samples came from a genuine LWE secret, the pairing lands on a value that is not quite uniform, and it leaves a faint, measurable bias. If the samples were drawn uniformly at random, the pairing looks flat and random. Detecting that bias tells you which world you are in, which is exactly what the decision version of LWE asks.
Source: Martin R. Albrecht, Rachel Player & Sam Scott, “On the concrete hardness of Learning with Errors,” 2015, ePrint 2015/046.
The cost of the dual attack comes from two places at once. Finding a short enough vector in the dual lattice again means running BKZ at some block size, so reduction is once more the expensive engine. On top of that, the shorter your dual vector the stronger the bias, so the fewer samples you need to detect it with confidence, while a longer dual vector produces a weaker bias that requires far more samples to confirm. The attacker balances a bigger block size against the number of samples and the security analysis works out the cheapest point on that curve. Because the decision problem and the search problem are essentially as hard as each other for LWE, breaking the decision version this way is a real break of the scheme.
The two attacks line up cleanly side by side, sharing an engine while differing in setup and in what they recover.
| Property | Primal attack | Dual attack |
|---|---|---|
| Lattice built | Embeds the secret + noise as one short vector (uSVP) | The dual of the LWE lattice |
| What it finds | The unique shortest vector (the secret) | A short vector used as a distinguisher |
| LWE version solved | Search (recovers the secret) | Decision (real samples vs random) |
| Expensive engine | BKZ at a large block size | BKZ at a large block size |
| Usually cheaper for the standards? | Yes, tends to drive the headline number | No, but re-estimated continuously |
Source: Martin R. Albrecht, Rachel Player & Sam Scott, “On the concrete hardness of Learning with Errors,” 2015, ePrint 2015/046.
Why do both attacks feed the same security estimate?
Both attacks feed the estimate because a defender has to survive the cheaper one, so the scheme’s real security is the minimum of the two costs. When cryptographers set parameters for a lattice scheme, they compute the cost of the best primal attack and the cost of the best dual attack against a candidate parameter set, take whichever is smaller, and treat that as the attacker’s actual price. If that price sits comfortably above the target security level, the parameters pass. If either attack comes in cheap, the parameters fail and the designers enlarge the dimension or adjust the noise until both attacks are expensive again.
Source: Martin R. Albrecht, Rachel Player & Sam Scott, “On the concrete hardness of Learning with Errors,” 2015, ePrint 2015/046.
This is why the two attacks are studied as a pair rather than in isolation. For the module-lattice parameters the NIST standards use, the primal attack is usually the cheaper strike, so it tends to drive the headline number, but the dual attack is re-estimated continuously because improvements to it could move the minimum. Both attacks share the same expensive subroutine, BKZ, and BKZ’s cost is dominated in turn by the sieving or enumeration it calls to solve the shortest-vector problem inside each block. So the full security estimate is a stack: the scheme’s strength rests on the cheaper of primal and dual, each of those rests on BKZ, and BKZ rests on the cost of the SVP-solver at the required block size. That stack is what Core-SVP formalizes into a single defensible number.
How do the attacks set the parameters for the standards?
They set the parameters by converting a target security level into a minimum lattice dimension. A designer starts with a goal, for example matching the brute-force cost of AES-128 at NIST’s Category 1, and asks what dimension and noise make both the primal and dual attacks cost at least that much. Larger dimensions force the attacker to run BKZ at a larger block size, which raises the cost of both attacks together, so the designer raises the dimension until the cheaper attack clears the bar with margin to spare. The margin matters because it absorbs the steady trickle of small algorithmic improvements to lattice reduction without forcing a redesign.
Source: NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 13, 2024, “The security of ML-KEM is related to the computational difficulty of the Module Learning with Errors problem.”
This is the mechanism behind the three sizes of the flagship schemes. ML-KEM-512, ML-KEM-768, and ML-KEM-1024 are the same Module-LWE design at three module dimensions, chosen so the cheaper of the primal and dual attacks lands above Category 1, Category 3, and Category 5 respectively. A team deploying the defaults never runs these attacks or touches a block size. The value of understanding them at a leadership level is knowing that the security claims rest on two concrete, publicly analyzed strategies rather than on faith, that the estimates carry deliberate margin, and that the number to watch over time is any advance that lowers the cost of primal or dual reduction at the required block sizes.
Common misconceptions
- “Solving LWE means attacking the noisy equations directly.” The practical attacks first rewrite LWE as a lattice problem and then run lattice reduction. The primal and dual attacks are the two ways to do that rewrite, and reduction does the actual work.
- “The primal and dual attacks are completely different algorithms.” They set up different lattices, the primal embedding the secret as a short vector and the dual building a distinguisher, but both bottom out in the same expensive step of running BKZ at a large block size.
- “You only need to worry about one of them.” A defender has to survive whichever is cheaper, so both are estimated and the security is the minimum of the two. For the standardized module parameters the primal attack is usually cheaper, but the dual is watched because improvements could flip that.
- “The dual attack recovers the secret.” The dual attack solves the decision version, telling real LWE samples from random ones, which is enough to break the scheme because the decision and search versions of LWE are essentially as hard as each other.
- “A bigger key can be attacked with the same effort.” Larger dimensions force a larger BKZ block size, which raises the cost of both attacks steeply, so enlarging the parameters is exactly how designers push both attacks out of reach.
Questions people ask
What are the primal and dual attacks on LWE? They are the two lattice strategies for solving Learning With Errors. The primal attack embeds LWE into a unique-shortest-vector instance and reduces the lattice until the secret surfaces as a short vector. The dual attack finds a short vector in the dual lattice and uses it to distinguish real LWE samples from random ones. A scheme’s security is the cost of whichever attack is cheaper.
How does the primal attack work? It uses an embedding to build a lattice in which the LWE secret and its noise form one unusually short vector, which makes the problem a unique shortest vector problem. Then it runs BKZ at the smallest block size that recovers that vector, and the required block size is what determines the attack’s cost.
How does the dual attack work? It finds a short vector in the dual lattice and pairs it against a batch of samples. A real LWE secret leaves a faint statistical bias in the result, while random samples do not, so detecting the bias solves the decision version of LWE. Shorter dual vectors give a stronger bias and need fewer samples, so the attacker trades block size against sample count.
Which attack is stronger against the NIST standards? For the module-lattice parameters in ML-KEM and ML-DSA, the primal attack is usually the cheaper of the two and tends to drive the headline security number, but the dual attack is re-estimated continuously because an improvement to it could lower the minimum that defines the security.
Do these attacks break ML-KEM or ML-DSA? No. The standardized parameters are chosen so the cheaper of the primal and dual attacks costs more than the target security level, with deliberate margin. They are the yardsticks that measure security, and at the deployed sizes there is no practical break.
Do I need to understand these attacks to migrate? No. The migration work is inventory, sizing, and testing, and the lattice arithmetic lives inside the libraries you integrate. Understanding the primal and dual attacks explains why the lattice security estimates are trusted and which cryptanalytic advances would matter enough to watch.
Everything here is the map, given freely. When your team needs the lattice standards sized, sequenced, and hedged across your own estate, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.