SABER

Introduction

SABER was one of the finalists in NIST’s post-quantum key encapsulation competition, ultimately losing out to CRYSTALS-Kyber but standing on genuinely different mathematical ground worth understanding in its own right. Both are module-lattice schemes built from small polynomial rings — but where Kyber gets its noise by explicitly sampling a random error and adding it, SABER gets its noise for free, as a side effect of rounding numbers down to a smaller scale. This variant of the hard lattice problem is called Learning With Rounding (LWR), and SABER’s name literally comes from its core operation: Modular Lattice with a Rounding trick, rearranged (SABER = Mod-LWR).

Table of Contents

• Learning With Rounding vs. Learning With Errors
• Key Generation
• Encapsulation and Decapsulation
• A Worked Example
• Why Rounding Works as Noise
• SABER vs. Kyber
• FAQ
• References

Learning With Rounding vs. Learning With Errors

LWE-based schemes like Kyber compute A·s + e, where e is freshly sampled random noise from a specific probability distribution every time. That sampling step has to be done very carefully — a biased or poorly-implemented noise sampler has been the source of real side-channel and security bugs in lattice cryptography. LWR sidesteps the problem entirely: instead of adding noise, it computes A·s at high precision (modulus q) and then rounds the result down to a smaller modulus p. The information lost in that rounding step — literally the low-order bits that get discarded — behaves exactly like small random noise from an attacker’s perspective, but requires no noise sampler at all, which simplifies implementation and closes off a whole class of side-channel attacks tied to noise sampling.

Key Generation

1. Generate a public k×k matrix A of polynomials in ℤ_q[x]/(xⁿ+1), coefficients uniform mod the large modulus Q.
2. Sample a small secret vector s of k polynomials (small coefficients, no error vector needed).
3. Compute A·s mod Q at full precision.
4. Round the result down from modulus Q to a smaller modulus P: b = round(A·s, Q→P). This rounded vector — not a noisy sum — is the public key.

Encapsulation and Decapsulation

To encapsulate message bits:

1. Sample a small secret vector s′ (the encapsulator’s own randomness — again, no error vector).
2. Compute u = round(Aᵀ·s′, Q→P) — the first ciphertext component, rounded the same way as the public key.
3. Compute the dot product b·s′ mod P, then round it again, down to an even smaller modulus T: this gives round(b·s′, P→T).
4. Add the encoded message bits (0 or T/2) to get the second ciphertext component: c = round(b·s′, P→T) + encode(bits) mod T.

To decapsulate, the recipient (holding secret s) computes:

round(u·s, P→T), then subtracts it from c, then rounds each coefficient of the difference to the nearer of {0, T/2}.

This works because b·s′ and u·s are both approximations of the same underlying quantity — s′ᵀ(A·s) — computed from two different roundings of A·s (once as b, once folded into u via Aᵀ). The rounding “noise” introduced at each stage is small enough that it cancels out below the T/2 decision threshold, the same way LWE’s explicit noise does in Kyber.

Interactive Visualizer

Real SABER uses ring degree n=256 and a modulus chain Q=2¹³ → P=2¹⁰ → T=2¹ (or 2³, depending on variant), tuned so the rounding “noise” stays statistically indistinguishable from true LWE noise at secure parameter sizes. The visualizer above runs the identical two-stage rounding structure — module rank k=2, ring degree n=4, moduli Q=256 → P=32 → T=8 — small enough to watch every rounding step directly, with genuinely zero explicit error sampling anywhere in the code.

A Worked Example

Using the visualizer’s toy parameters:

1. A random 2×2 matrix A (mod 256) and small secret vector s produce A·s mod 256, rounded down to mod 32 to get public key b.
2. To send 4 bits, the sender samples its own small s′, computes u = round(Aᵀ·s′, 256→32), then b·s′ mod 32, rounds that down to mod 8, and adds the encoded bits (0 or 4) mod 8 to get c.
3. The recipient computes round(u·s, 32→8), subtracts it from c mod 8, and rounds each of the 4 resulting values to the nearer of 0 or 4.
4. Both roundings introduce small discrepancies, but they stay well under the halfway threshold, so the bits come back exactly.

Why Rounding Works as Noise

Rounding a value from modulus Q down to modulus P discards roughly log₂(Q/P) bits of information per coefficient — information an attacker without the secret key cannot recover, functioning exactly like the entropy that explicit LWE noise provides. The key security argument for LWR (proven to reduce to LWE hardness under the right parameter choices) is that as long as Q is large enough relative to the number of samples an attacker can collect, the rounded outputs remain computationally indistinguishable from uniformly random values — which is precisely the property a KEM’s public key and ciphertext need.

SABER vs. Kyber

Kyber’s prime modulus enables the Number Theoretic Transform for fast polynomial multiplication, which tipped NIST’s final decision toward Kyber for the primary standard — but SABER’s power-of-two moduli make its arithmetic (masking, rounding, modular reduction) notably simpler to implement correctly and constant-time, which is why it remains an actively studied and used alternative, especially in academic and embedded contexts.

FAQ

Is rounding actually as secure as adding random noise?

Under the parameter regimes used by SABER, yes — the Learning With Rounding problem has been proven to reduce to Learning With Errors hardness (deterministic rounding noise is computationally indistinguishable from the “real” LWE noise distribution at those scales), so SABER inherits the same lattice-hardness guarantees as LWE-based schemes like Kyber.

Why does SABER use a power-of-two modulus instead of a prime like Kyber?

Power-of-two moduli make rounding, masking (for side-channel protection), and modular reduction all simpler and faster to implement in constant time — no modular inverse or Barrett/Montgomery reduction tricks needed, since taking a value mod 2ᵏ is just a bitmask.

Why didn’t NIST pick SABER as the primary standard?

It came down mostly to raw performance: Kyber’s prime modulus enables the NTT, which makes polynomial multiplication substantially faster than SABER’s non-NTT-friendly power-of-two arithmetic at the ring sizes both use, and NIST prioritized that speed for the primary general-purpose KEM standard.

Does the visualizer’s double rounding (Q→P then P→T) match real SABER?

Yes structurally — real SABER also rounds twice: once to compress the public key/ciphertext-u, and again to compress the final ciphertext component that carries the encoded message, exactly mirroring the visualizer’s Q→P→T chain, just at production-scale moduli.

References

1. D’Anvers, J-P., Karmakar, A., Sinha Roy, S., Vercauteren, F. “SABER: Mod-LWR based KEM.” Cryptology ePrint Archive, 2018.

2. NIST. “Post-Quantum Cryptography Standardization — Round 3 Finalists.” Available at: https://csrc.nist.gov/projects/post-quantum-cryptography

3. Banerjee, A., Peikert, C., Rosen, A. “Pseudorandom Functions and Lattices” (introduces Learning With Rounding). EUROCRYPT, 2012.

4. SABER Team. “SABER: Mod-LWR Based KEM.” Available at: https://www.esat.kuleuven.be/cosic/pqcrypto/saber/