Learning With Rounding (LWR)
Learning With Rounding is a deterministic variant of Learning With Errors (LWE). Both problems start from the same place, a batch of modular linear equations in a hidden secret, and both hide the secret by making each answer imprecise. Where LWE blurs each answer by adding a small random error drawn fresh every time, LWR blurs it by rounding: it computes the exact answer over a large modulus and then rounds it down to a coarser, smaller modulus, throwing away the low-order bits. The lost bits play the role the noise played, so the secret stays hidden without anyone ever sampling a random error. That single change, deterministic rounding standing in for randomized noise, buys smaller keys, faster arithmetic, and a simpler implementation at the cost of a hardness argument that holds under narrower conditions than LWE’s.
Source: Abhishek Banerjee, Chris Peikert, Alon Rosen, “Pseudorandom Functions and Lattices,” EUROCRYPT 2012, pp. 719-737, DOI 10.1007/978-3-642-29011-4_42 (ePrint 2011/401, which introduces the LWR problem as a derandomization of LWE).
The short version:
- LWR replaces LWE’s random error with deterministic rounding. Compute the exact modular inner product, then round it from a large modulus
qdown to a small modulusp. The bits lost in rounding hide the secret the way added noise does in LWE. - No error sampling means a simpler, faster scheme. There is no random distribution to draw from, no rejection sampling, and less randomness to protect, which is why LWR schemes tend to be compact and quick.
- Banerjee, Peikert, and Rosen introduced it in 2012 as a derandomization of LWE, and proved a reduction: LWR is at least as hard as LWE when the ratio
q/pis large enough. - It is the basis of SABER, a lattice key-encapsulation mechanism that reached the final round of the NIST post-quantum competition, using module-LWR with power-of-two moduli.
- The tradeoff is reduction breadth. LWR’s worst-case guarantee is more conditional than LWE’s, so a designer accepts a narrower proof in exchange for the efficiency, and that judgment is exactly why NIST’s chosen standards use noise-based Module-LWE rather than rounding.
Picture the same noisy spreadsheet from Learning With Errors, every row an equation in the hidden secret, every answer made imprecise so the clean algebra will not land on the truth. LWE makes each answer imprecise by nudging it up or down by a small random amount picked freshly for that row. LWR makes it imprecise a different way: it computes the answer exactly, then reports it rounded to the nearest coarse gradation, like reading a precise measurement off a ruler that only has centimeter marks. The fine detail is gone either way, and the secret is just as buried, yet with rounding there was never any dice to roll. The imprecision came from the reporting itself, so the person building the system needs no source of random error.
What is Learning With Rounding?
Learning With Rounding asks you to recover a secret from modular linear equations whose answers have been rounded from a large modulus to a smaller one. Each sample pairs a known row of coefficients with a value equal to that row combined with the secret over a modulus q, then rounded into a smaller modulus p. The rounding function scales the exact result by p/q and takes the floor, so it keeps the high-order information and discards the low-order bits. That discarded slice is the source of hardness. As with LWE, recovering the secret from the exact, un-rounded answers would be ordinary linear algebra, so the imprecision is the entire security.
Source: Banerjee, Peikert, Rosen, EUROCRYPT 2012, ePrint 2011/401; rounding-function form ⌊(p/q)·(a·s mod q)⌉ per the same work.
The problem is deterministic in a way LWE is not, and that difference is the crux. In LWE, asking for the same equation twice yields two answers that differ, because a fresh random error is added each time. In LWR, the same equation always rounds to the same value, because the imprecision is a fixed function of the exact result rather than a random draw. Determinism is what makes LWR attractive for building pseudorandom functions and compact key exchange, and it is also what makes the hardness argument more delicate, because a deterministic transformation gives an attacker a more stable target to study than a randomized one.
How is LWR different from LWE?
The mechanical difference is where the imprecision comes from, and everything else follows from it. LWE adds random error sampled from a narrow distribution; LWR subtracts information by rounding to a coarser modulus. Both leave the secret hidden below a threshold the legitimate key holder can clear and an attacker cannot, but they get there by opposite routes, one adding randomness and one removing precision.
| Property | Learning With Errors (LWE) | Learning With Rounding |
|---|---|---|
| Source of imprecision | Random error added to each answer | Deterministic rounding to a smaller modulus |
| Randomness needed | Fresh error sampled per sample | None once the equations are fixed |
| Same query twice | Different answers | Identical answer |
| Efficiency | Heavier: sampling, more bits | Lighter: no sampling, fewer bits transmitted |
| Hardness reduction | Broad worst-case-to-average-case (Regev) | Narrower, conditional on a large q/p ratio |
Source: Banerjee, Peikert, Rosen, EUROCRYPT 2012, ePrint 2011/401; LWE reduction per Oded Regev, “On Lattices, Learning with Errors…,” 2005/2009, paper PDF.
The practical payoff of dropping the error term is real. A scheme with no error to sample carries no error-distribution code, needs no rejection sampling, transmits fewer bits because the rounded values live in the smaller modulus, and exposes less randomness for a side-channel to attack. Those savings are why the SABER designers reached for rounding. The cost is that LWR’s security proof depends on parameters, chiefly a large gap between q and p, so a designer trades the breadth of LWE’s guarantee for the leanness of the construction, and has to defend that trade in the parameter choices.
What did Banerjee, Peikert, and Rosen prove?
They introduced LWR as a way to derandomize LWE and proved that LWR inherits LWE’s hardness under the right conditions. The reduction shows that solving LWR is at least as hard as solving LWE when the ratio q/p is sufficiently large, meaning the rounding modulus p is small enough relative to q that the discarded bits carry enough of the effect a random error would have carried. Under that condition, an efficient LWR solver would yield an efficient LWE solver, so LWR sits on the same lattice foundation as LWE and, transitively, on the worst-case lattice problems LWE reduces to.
Source: Banerjee, Peikert, Rosen, “Pseudorandom Functions and Lattices,” EUROCRYPT 2012, ePrint 2011/401.
The honest caveat is the phrase “sufficiently large.” The original reduction required a q/p gap and a modulus size that were larger than what an efficient real-world scheme wants to use, so early LWR reductions did not directly cover the aggressive parameters deployment needs. Later research tightened and broadened the conditions under which LWR remains provably hard, and practical LWR schemes lean on a combination of those improved reductions and direct cryptanalysis of the concrete parameters. The takeaway for a decision-maker is that LWR’s theoretical footing is genuine and derived from LWE, and it is more parameter-dependent than LWE’s, which is a reason for conservatism rather than a reason for alarm.
Why does SABER use LWR instead of LWE?
SABER uses rounding because it makes the scheme simpler and faster without sacrificing the lattice security model, and it takes the idea one step further by choosing power-of-two moduli. SABER is built on the module version of the problem, Module-LWR, the rounding analogue of the Module-LWE that underlies ML-KEM. Its moduli are q = 2^13 and p = 2^10, both powers of two, which turns the rounding operation into a plain bit shift and eliminates modular reduction, rejection sampling, and explicit error sampling from the hot path. The result is a compact, constant-time-friendly key-encapsulation mechanism.
Source: SABER round 3 specification, D’Anvers, Karmakar, Sinha Roy, Vercauteren et al., SABER team, KU Leuven (Module-LWR basis; q = 2^13, p = 2^10; power-of-two moduli remove modular reduction and error sampling).
SABER offers three parameter sets that scale the module dimension to reach different security levels, in the same way ML-KEM offers three sizes of one scheme.
| SABER parameter set | NIST security level |
|---|---|
| LightSaber | Level 1 |
| SABER | Level 3 |
| FireSaber | Level 5 |
Source: SABER round 3 specification, SABER team, KU Leuven (LightSaber / SABER / FireSaber at NIST levels 1, 3, 5).
SABER reached the final round of the NIST post-quantum competition and was a serious contender, so the reason ML-KEM won the standard rather than SABER is worth stating plainly. NIST chose the noise-based Module-LWE design, judging that its broader hardness reduction and larger body of cryptanalysis outweighed the efficiency edge that rounding provides. That is the efficiency-versus-analysis tradeoff in one decision: LWR is leaner, LWE is better understood, and the standard went to the better-understood option while LWR remains an important, well-studied part of the lattice toolkit.
Where does LWR show up in real systems?
LWR does not appear by name in a shipped protocol, and unlike Module-LWE it does not sit under a finalized NIST standard, so its footprint today is narrower than LWE’s. Its primary appearance is SABER, which any organization surveying the post-quantum landscape will encounter as a NIST finalist and a benchmark against ML-KEM. Rounding as a technique also appears inside some other lattice constructions as an efficiency device, so the idea travels beyond the single scheme even where the “LWR” label does not.
For a leadership decision, the practical meaning is that LWR is context worth having and not a deployment target. The standardized default for key establishment is ML-KEM on Module-LWE, so a migration plan is built around that, not around SABER. Understanding LWR tells you why the standard uses noise rather than rounding, what the discarded alternative offered, and why a scheme can be faster and smaller yet still lose on the strength and breadth of its security argument. That is exactly the kind of judgment that separates reading a benchmark table from understanding what the numbers cost.
Common misconceptions
- “LWR is just LWE with a different name.” They share a structure and LWR reduces to LWE, and they hide the secret by opposite mechanisms. LWE adds random noise; LWR removes precision by rounding. The determinism of rounding is a real difference that changes the efficiency, the implementation, and the breadth of the security proof.
- “Rounding is less secure than adding noise.” LWR carries a genuine reduction to LWE, so it rests on the same lattice hardness. Its reduction is more parameter-dependent, which is a reason to choose parameters carefully, and it does not make a well-parameterized LWR scheme weak. NIST preferred LWE for its broader analysis, which is a conservatism call rather than a verdict that LWR is broken.
- “SABER lost the NIST competition because it was insecure.” SABER reached the final round and no break decided the outcome. NIST selected the noise-based Module-LWE design of ML-KEM for its broader hardness reduction and larger cryptanalytic record, and SABER’s rounding-based approach remains a respected, well-studied construction.
- “LWR needs no random numbers at all.” The rounding removes the per-sample error draw, and a real scheme still needs randomness for key generation and encapsulation. What LWR removes is the error-sampling machinery, which is a meaningful simplification of one specific and side-channel-sensitive part.
- “I should deploy SABER for post-quantum key exchange.” The finalized standard is ML-KEM, and that is what a migration targets. SABER is a finalist and a benchmark, not a NIST standard, so building production key establishment on it means stepping off the standardized path.
Questions people ask
What is Learning With Rounding in simple terms? It is Learning With Errors with the random noise swapped for deterministic rounding. Instead of adding a small random amount to each equation’s answer, you compute the answer exactly over a large modulus and then round it down to a smaller one, and the bits you throw away in rounding hide the secret the way the noise did.
How is LWR different from LWE? The imprecision that hides the secret comes from rounding rather than from added random error. That makes LWR deterministic, so the same equation always gives the same rounded answer, and it removes the need to sample and protect a random error distribution. The cost is a hardness reduction that holds under narrower parameter conditions than LWE’s.
Who introduced LWR and when? Abhishek Banerjee, Chris Peikert, and Alon Rosen introduced it in 2012, at EUROCRYPT, in “Pseudorandom Functions and Lattices,” where they presented LWR as a way to derandomize LWE and proved that LWR is at least as hard as LWE when the ratio between the two moduli is large enough.
Why does SABER use rounding instead of noise? Because it makes the scheme smaller and faster. Dropping the error term removes error sampling, rejection sampling, and some transmitted bits, and SABER’s power-of-two moduli turn the rounding into a bit shift with no modular reduction. That leanness is LWR’s whole appeal, and it is why SABER reached the NIST final round.
If SABER is so efficient, why did ML-KEM become the standard? NIST judged that the noise-based Module-LWE design behind ML-KEM had a broader hardness reduction and a larger body of cryptanalysis than SABER’s rounding-based design, and chose the better-understood option. The efficiency edge of rounding did not outweigh the analytical breadth of noise.
Do I need to understand LWR to migrate to the standards? No. The standardized key-establishment algorithm is ML-KEM on Module-LWE, so the migration work is inventory, sizing, and testing against that. Understanding LWR explains why the standard uses noise rather than rounding and what the efficient alternative traded away, which is leadership context rather than an implementation requirement.
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.