Constant-Time Arithmetic for Lattice Schemes

A lattice scheme whose mathematics resists a quantum adversary can still be defeated by a branch predictor. Side-channel attacks on post-quantum implementations exploit the same classes of leakage as on classical ones, but the arithmetic has properties that make some leaks easier to eliminate and others harder. Integer modular arithmetic is naturally branch-free in a way that elliptic curve point addition is not; on the other hand, the sampling steps and the rejection loops in signatures are data-dependent by design, and the transition between the arithmetic core and the control flow around it is where implementations go wrong.

Where the secret-dependent decisions actually are

Trace a decapsulation of ML-KEM and classify each operation by whether its timing can depend on the secret. The secret key is the vector $s$ and the additional rejection seed $z$. Decapsulation computes $m’ = \mathrm{Decompress}(v) - \mathrm{Decompress}(u)^T s$, then re-encapsulates from $m’$ and compares. The matrix-vector product with $s$ is the only operation that directly combines the secret with attacker-controlled data, and it is carried out with the NTT: transform $s$ once at key generation, transform the incoming vector at decapsulation, multiply pointwise in the NTT domain, and inverse-transform.

The NTT itself has no data-dependent branches when implemented over a fixed schedule. Every butterfly operates on every coefficient, and the twiddle factors are constants chosen by the loop index. The only leak-relevant detail is the representation: if coefficients are allowed to grow beyond the word size and are reduced conditionally, the reduction becomes a branch on a secret. Implementations avoid this by carrying coefficients in a redundant representation throughout the transform, adding a multiple of $q$ that keeps the value in a range where overflow cannot occur, and performing a single full reduction at the end. The number of additions is fixed, so the timing is fixed.

The multiplication by the twiddle factor is where the word size matters. For $q = 3329$ with 16-bit words, a product of two 16-bit values occupies 32 bits, and the Montgomery reduction step can be arranged so that intermediate values stay under $2^{16}$ with a fixed constant added. The standard’s reference implementation and the Longa–Naehrig variant differ in whether they defer the reduction, but both are branch-free. The reason to care is that a compiler may introduce a branch when optimising a conditional subtract written as if (a >= q) a -= q;, and the mitigation is to write the reduction as a -= (a >= q) ? q : 0; which compiles to a conditional move or a mask, or to use the classic constant-time trick of subtracting $q$, masking the sign bit, and adding the mask back.

A less obvious leak is in the ordering of the NTT butterflies. The standard’s arithmetic is defined with a specific butterfly ordering because the results must match bit for bit for the re-encryption check to succeed. An implementation that reorders the butterflies for speed produces the same mathematical result but a different bit pattern in intermediate values, and while that does not affect correctness of the final reduction, it can affect the constant-time property if the alternative schedule incorporates data. The conformance requirement pins the order for a different reason: the compression step discards low bits, and the discarded bits depend on the exact intermediate values in a way that the re-encryption check detects.

Sampling without rejection, and the sampling that must reject

Key generation samples noise from a centred binomial distribution, and this is the place where the lattice design buys a constant-time property on purpose. The distribution over ${-2, \dots, 2}$ is generated by taking eight bits, splitting into four two-bit values, summing the bits of each pair and subtracting two from the result. The arithmetic is additions and a fixed constant, and every input byte produces four output coefficients regardless of its value. There is no rejection, no table lookup, and no variable number of random bytes consumed.

Contrast with the discrete Gaussian. Sampling from a discrete Gaussian over a finite support requires either a table of cumulative probabilities and a binary search, which has data-dependent memory access and hence cache leakage, or a rejection-sampling loop with a variable number of iterations. Both are hard to make constant-time, and both were the subject of attacks on earlier lattice implementations. The centred binomial is not a Gaussian, and its statistical distance from the ideal Gaussian is the price of the constant-time property; the parameter analysis of the scheme accounts for the actual distribution rather than the ideal one, which is why substituting a Gaussian “for better security” breaks the analysis in both directions.

Signing is the opposite case. ML-DSA’s Fiat-Shamir with Aborts loop as described in ML-DSA’s rejection sampling rejects candidates, and the number of rejections depends on the secret and on the secret-dependent masking vector $y$. This is a genuine timing leak that cannot be eliminated by rewriting the arithmetic. The mitigations are all at the protocol level: derive the masking randomness deterministically from the message and a counter, so that an attacker who observes the rejection count learns nothing beyond what the deterministic derivation already allows; ensure the counter is included in the derivation so that retries use fresh values; and cap the number of retries with a fallback that reveals nothing about the cause of the excess. The specification’s requirement that the signer derive fresh randomness per attempt and the absence of any requirement to conceal the retry count are consistent: the leak is accepted because the security argument accounts for it.

Memory access patterns over untrusted input

Public keys and ciphertexts are attacker-controlled. Parsing them is where a large share of real vulnerabilities live, and the constant-time concerns overlap with bounds checking. Three patterns recur.

Boundary-checked decoding of coefficients. The 12-bit decoder for a public key reads two coefficients from three bytes. A canonical decoder must reject values at or above $q$. An implementation that reduces mod $q$ silently accepts non-canonical encodings, which produces the same key under a different byte string; if the protocol hashes the public key encoding, two different encodings produce two different hashes of what the identity considers one key, and a signature scheme that binds a key to an identity through its hash becomes forgeable across encodings. A bytewise comparison against the canonical re-encoding of the decoded value is the check, and it is constant-time if performed over the whole key rather than with early exit.

Hint decoding in signatures. The hint in ML-DSA is a sparse structure: each row begins with a count, followed by that many byte indices. A decoder that trusts the count will read past the row’s bounds if the count is larger than the row size, so the count must be validated before the loop. The validation itself is a branch on attacker data, which is fine: the attacker already knows the count they sent. The problem is only when the count influences the memory access of a subsequent secret operation, which it does if the decoded hint is used to index into a secret-dependent structure. The reference decoder validates first, then processes, so the branch is on public data.

Comparison of the re-encrypted ciphertext. The final check in decapsulation compares the received ciphertext against the recomputed one. A standard library comparison that returns on the first mismatch reveals the length of the common prefix, and a decapsulation oracle that reveals that length is enough to mount a key-recovery attack because the attacker can iteratively refine the ciphertext. The comparison must run over every byte, accumulating the difference with a bitwise OR or a subtraction that does not short-circuit, and the result must be converted to a branchless selection between the two keys.

What the compiler does to all of this

The hardest part of constant-time lattice code is not writing the arithmetic but keeping it. Compilers recognise if (x < y) patterns and may convert a conditional move into a branch when it estimates that the branch is more profitable. A masking idiom written as mask = -(uint16_t)(a >= q) compiles to a comparison and a negation on most architectures, but nothing in the C standard requires it to, and link-time optimisation or a different optimisation level can change the code generation. The countermeasures are to inspect the generated code, to use volatile or inline assembly for the critical reductions, and to keep the arithmetic in a small set of functions whose code generation is verified once.

Vectorisation is the modern variant of the same problem. A compiler that auto-vectorises the NTT loop may generate masked loads that read past the end of an array for the tail of the loop, which is benign for the arithmetic but not for a memory checker or a hardened allocator that traps on the access. The portable fix is to pad arrays to the vector width, and the performance fix is to choose the transform size to be a multiple of that width: 256 coefficients for $q = 3329$ divides evenly by the common vector widths, which is one reason the parameter is fixed rather than chosen per security level.

Finally, the whole question is architecture-specific. The 16-bit operations in ML-KEM’s reference implementation are natural for 32-bit and 64-bit processors, where a 16-bit multiply produces a full-width result cheaply, but the same code on a processor with slow 16-bit multiplication or on a vector unit with no 16-bit multiply has a different cost profile. Implementations that vectorise the NTT use the 32-bit lanes for two 16-bit coefficients per lane and rely on the fact that the reduction bounds keep the products from overflowing the lane. The choice of parameter for the modulus, the size of the coefficient encoding, and the structure of the transform are all tied to that arithmetic, which is why the parameter sets are fixed in the standard rather than left to the implementer.