Post-Quantum and Lattice-Based Cryptography Questions

Direct answer

The Learning With Errors (LWE) problem asks an adversary to distinguish, or recover a secret from, a set of linear equations over $\mathbb{Z}_q$ that have been deliberately corrupted with small random noise. Fix a secret $\mathbf{s} \in \mathbb{Z}_q^n$; each sample is a pair $(\mathbf{a}_i, b_i)$ with $\mathbf{a}_i \in \mathbb{Z}_q^n$ uniform and

where $e_i$ is drawn from a small error distribution $\chi$ (typically a discrete Gaussian or, in practice, a centered binomial distribution). Without the noise term this is ordinary linear algebra, solvable in polynomial time; the noise is precisely what turns it into a problem believed hard for both classical and quantum computers, backed by reductions from worst-case lattice problems.

Structured elaboration

Roles of the parameters.

• $n$, the dimension: the length of the secret vector and of each $\mathbf{a}_i$. It sets the dimension of the implicit lattice and is the primary driver of concrete hardness.
• $q$, the modulus: all arithmetic is mod $q$. It must be large enough relative to the error to leave decoding room for any scheme built on top, but not so large that the noise becomes negligible relative to $q$.
• The secret distribution for $\mathbf{s}$: originally uniform over $\mathbb{Z}_q^n$, but virtually all deployed schemes use a small, structured secret (the same small distribution as the error), because this is provably as hard as uniform-secret LWE and yields smaller, faster schemes.
• The error distribution $\chi$: concentrated near 0 (small variance relative to $q$) so the noise is "small" in the sense the hardness reductions need, while wide enough that the equations are not effectively noiseless.

Why the noise makes this hard. Given $n$ or more noiseless equations, an attacker recovers $\mathbf{s}$ exactly via Gaussian elimination mod $q$. Adding even small error breaks this: elimination on noisy, inconsistent equations does not converge to the true $\mathbf{s}$, it propagates and amplifies the noise through every pivot step (worked example below). Geometrically, the samples define points lying near, but not on, a lattice determined by $\mathbf{s}$; recovering $\mathbf{s}$ is equivalent to bounded-distance decoding (BDD) or the closest-vector problem (CVP) on that lattice, believed hard once the noise-to-modulus ratio is small enough.

Worst-case to average-case reductions. LWE's significance comes from Oded Regev's 2005 result showing a quantum polynomial-time reduction from worst-case lattice problems (approximate SVP, the Shortest Vector Problem: find the shortest nonzero vector in a lattice, and SIVP, the Shortest Independent Vectors Problem: find $n$ linearly independent lattice vectors that are collectively as short as possible, both on arbitrary $n$-dimensional lattices) to average-case LWE: an efficient solver for random LWE instances yields an efficient solver for the worst-case lattice problem. This is the opposite of most classical hardness assumptions, which rely on average-case hardness of one specific instance family (factoring a random RSA modulus); LWE's guarantee is that breaking random instances is at least as hard as solving the single hardest lattice of that dimension. Subsequent work (notably Peikert's) gave partially classical reductions under restricted parameter regimes, though the most general reductions remain quantum. Real parameter selection relies less on these asymptotic reductions and more on directly estimating the cost of known lattice attacks, since the reductions say "at least as hard as," not "exactly this many bits."

Worked example

A tiny, fully pinned instance makes the "noise breaks linear algebra" claim concrete: $n=4$, $q=97$, pinned seed.

import random
random.seed(20260730)
n, q = 4, 97
s = [random.randrange(q) for _ in range(n)]
samples = []
for i in range(6):
    a_i = [random.randrange(q) for _ in range(n)]
    e_i = random.choice([-2, -1, 0, 0, 1, 2])
    b_i = (sum(x*y for x, y in zip(a_i, s)) + e_i) % q
    samples.append((a_i, e_i, b_i))
print("s =", s)
for a_i, e_i, b_i in samples:
    print(a_i, e_i, b_i)

def solve_mod_q(A, b, q):
    n = len(A)
    M = [row[:] + [b[i]] for i, row in enumerate(A)]
    for col in range(n):
        piv = next(r for r in range(col, n) if M[r][col] % q != 0)
        M[col], M[piv] = M[piv], M[col]
        inv = pow(M[col][col], q - 2, q)
        M[col] = [(x * inv) % q for x in M[col]]
        for r in range(n):
            if r != col and M[r][col] != 0:
                factor = M[r][col]
                M[r] = [(M[r][k] - factor * M[col][k]) % q for k in range(n + 1)]
    return [M[i][n] for i in range(n)]

first4 = samples[:4]
A = [a for a, e, b in first4]
b_noiseless = [sum(x * y for x, y in zip(a, s)) % q for a, e, b in first4]
b_noisy = [b for a, e, b in first4]
print("noiseless solve:", solve_mod_q(A, b_noiseless, q))
print("noisy solve:", solve_mod_q(A, b_noisy, q))

Output (pinned seed):

s = [89, 76, 22, 32]
[68, 21, 4, 93] 1 43
[51, 71, 75, 7] -1 71
[69, 42, 72, 75] 1 29
[59, 45, 9, 66] -1 19
[96, 37, 46, 25] -1 72
[51, 90, 35, 31] -2 44
noiseless solve: [89, 76, 22, 32]
noisy solve: [77, 9, 19, 55]

Running Gaussian elimination mod 97 on the first four samples: with the noiseless target $b_i' = \langle \mathbf{a}_i,\mathbf{s}\rangle \bmod q$ the solver above exactly recovers [89, 76, 22, 32], matching $\mathbf{s}$. The identical solver run on the actual noisy $b_i$ values returns [77, 9, 19, 55], sharing no coordinate with the true secret. A single unit of injected noise per equation is enough to derail exact linear algebra completely, because arithmetic mod $q$ has no notion of "approximately correct": an off-by-one in one equation corrupts every pivot step that touches it. This is exactly why recovering $\mathbf{s}$ from real LWE samples requires lattice-reduction or decoding techniques, not linear algebra.

Trade-offs and pitfalls

• Error too small breaks hardness, not just correctness. If $\chi$ is degenerate enough that noise is negligible relative to $q$, LWE degenerates toward the easy noiseless case; the worst-case reductions require the noise rate to stay above certain thresholds relative to $n$ and $q$.
• Error too large breaks correctness of anything built on top. Schemes encoding a message into the noisy inner product need enough headroom between noise and the decoding threshold; over-widening $\chi$ for "extra margin" without re-deriving the failure probability is a common mistake.
• Uniform-secret vs. small-secret LWE. Using a small-entropy secret (as virtually every deployed scheme does) is a deliberate efficiency choice backed by a reduction showing it does not weaken hardness, not an ad hoc shortcut.
• Search-LWE vs. decision-LWE. The definition above is search-LWE (recover $\mathbf{s}$); decision-LWE (distinguish LWE samples from uniform pairs) is the version most encryption security proofs actually reduce to, and the two are polynomial-time equivalent for standard parameter regimes.

Direct answer

Recommend a binary Goppa code with $n = 3488$, $t = 64$, giving a code dimension $k = n - mt = 3488 - 12 \times 64 = 2720$ (using field-extension degree $m = \lceil \log_2 n \rceil = 12$, the smallest $m$ with $2^m \ge n$), matching Classic McEliece's actual NIST-submitted mceliece348864 parameter set exactly. Justification: this follows the same derive-and-cross-check methodology throughout, computing Prange's classical information-set-decoding (ISD) work factor directly from $(n,k,t)$ and confirming it clears the 128-bit target with the margin expected once the gap to the stronger Stern/BJMM attacks is accounted for.

Structured elaboration

Why $n=3488, t=64$ specifically, not some other pair achieving the same $(n,t)$ "shape." Classic McEliece's actual NIST submission fixed this exact pair for its Category 1 (roughly AES-128-equivalent) parameter set after extensive analysis against the full ISD attack family (not just Prange); recommending the SAME pair here is a deliberate choice to anchor this proposal to a value that has survived multiple rounds of public cryptanalysis, rather than proposing an untested novel pair that merely "looks" similar in scale.

Code family: binary Goppa, not a structured alternative. Binary Goppa codes are chosen specifically because they have NO known efficient distinguisher separating a disguised Goppa parity-check matrix from a matrix of a truly random linear code (the "Goppa-code-distinguishing" assumption, a SEPARATE hardness assumption from ISD hardness itself, both of which must hold). Structured code families proposed to shrink the key (quasi-cyclic or quasi-dyadic variants, for instance) have repeatedly been broken by attacks exploiting exactly the added structure; Classic McEliece deliberately keeps the unstructured, "looks like nothing" property despite its size cost, a considered trade-off documented across multiple rounds of the standardization process.

Key size and performance consequence. Public key size for a systematic-form parity-check matrix is $k(n-k)$ bits (the free, unstructured part of the matrix); this is the direct cost of choosing an unstructured code, hundreds of kilobytes for any Category-1-or-above parameter set, the largest public key of any mainstream NIST PQC KEM family. In exchange, encryption and decryption are extremely fast (matrix-vector multiplication plus one efficient algebraic decode, no expensive number-theoretic operations), and the ciphertext itself is comparatively small (a syndrome vector of length $n-k$ bits, not the full $n$-bit codeword), so the SIZE cost of this scheme is concentrated almost entirely in the public key, not in per-message bandwidth, an important distinction for any protocol where the key is exchanged once and reused across many messages.

Worked example

import math

def log2_comb(n, k):
    return (math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1)) / math.log(2)

def derive_k(n, t):
    m = math.ceil(math.log2(n))
    return n - m * t, m

def prange_log2_workfactor(n, k, t):
    return log2_comb(n, k) - log2_comb(n - t, k)

n, t = 3488, 64
k, m = derive_k(n, t)
wf = prange_log2_workfactor(n, k, t)
pk_bits = k * (n - k)
print(f"n={n}, t={t}, m={m}, k={k}")
print(f"Prange classical log2(workfactor) = {wf:.1f}")
print(f"public key size = {pk_bits} bits = {pk_bits/8/1024:.1f} KiB")

Output:

n=3488, t=64, m=12, k=2720
Prange classical log2(workfactor) = 142.8
public key size = 2088960 bits = 255.0 KiB

The derived $k=2720$ matches the officially published mceliece348864 dimension exactly (cross-verified live against NIST's own submission data). Prange's work factor of $2^{142.8}$ sits comfortably above the 128-bit target: this margin is expected, not evidence of over-conservatism, since Prange is the WEAKEST ISD variant and the officially targeted 128-bit level is calibrated against the stronger Stern/BJMM attacks, which reduce this Prange baseline by a polynomial-in-the-exponent factor this simplified calculation does not itself compute. The resulting $\approx 255$ KiB public key is the direct, unavoidable cost of the unstructured-code choice: over 150 times larger than a comparable lattice-based KEM's public key (roughly 1 to 1.5 kilobytes at a similar security level), the central performance trade-off this scheme accepts in exchange for its unusually long, largely unbroken track record on the core hardness assumption.

Trade-offs and pitfalls

• Common mistake: reporting the Prange work factor as the scheme's actual security level. As with any Prange-based estimate, Prange is a valid weakest-attack baseline, never the number to quote as "the" security level; the real evaluation requires the strongest known ISD variant (BJMM and successors), which this simplified calculation does not itself compute.
• 255 KiB is a real deployment cost, not a rounding error, for any protocol that cannot amortize the public key across many uses. A one-shot ephemeral key exchange pays this cost on every single handshake; a scheme designed for long-lived, reused keys (a static server key fetched once and cached) amortizes it far better. Parameter selection in isolation cannot answer "is this size acceptable," that depends entirely on the deployment's specific key-reuse pattern.
• Common mistake: assuming a smaller $t$ (fewer correctable errors) is a straightforward way to shrink the public key without a security cost. Since $k = n - mt$, DECREASING $t$ for fixed $n$ INCREASES $k$, which increases $k(n-k)$'s value up to the point where $k=n/2$ maximizes it, so the size-vs-security relationship is not monotonic in the simple direction intuition suggests; any proposed parameter change needs the full $(n,k,t)$ recomputed and re-evaluated together, not a single value tweaked in isolation.
• Two separate hardness assumptions underpin this recommendation, and parameter guidance addresses only one of them. The Prange/ISD work-factor calculation addresses SYNDROME-DECODING hardness; it says nothing about the SEPARATE Goppa-code-distinguishing assumption (that the disguised public matrix is indistinguishable from a generic random-code matrix), which is why deliberately choosing the conservative, unstructured Goppa family (rather than a smaller but structured alternative) is itself part of the security recommendation, not a detail orthogonal to it.

Direct answer

Beyond Shor's algorithm (breaks factoring and discrete log outright) and Grover's algorithm (quadratic speedup on unstructured search), the techniques that matter for evaluating today's post-quantum schemes fall into three groups: quantum-walk-based amplitude amplification applied to STRUCTURED search problems (giving speedups better than plain Grover but still short of Shor-style exponential breaks), collision-finding algorithms (BHT and successors) that affect hash-based and any construction relying on collision resistance, and a change to how security PROOFS themselves must model the adversary, the quantum random oracle model (QROM), which is a strictly stronger and harder-to-satisfy proof requirement than the classical random oracle model even for schemes with no quantum-speedup-relevant structure at all.

Structured elaboration

Quantum walks applied to lattice sieving and information-set decoding. Plain Grover search applied naively to a structured problem (finding a short lattice vector, or finding an error-free information set) gives a straightforward quadratic speedup, but quantum WALK algorithms exploit the problem's specific combinatorial structure to do meaningfully better than naive Grover on that same problem. For lattice sieving (the core subroutine of the best known SVP/CVP algorithms underlying lattice cryptanalysis), the best known classical sieve costs $2^{0.292 d}$ for lattice dimension $d$ (Becker-Ducas-Gama-Laarhoven, the widely used "core-SVP" classical exponent); the best known quantum sieve (using quantum walks, not plain Grover) reduces this to roughly $2^{0.265 d}$, a real but modest constant-factor-in-the-exponent improvement, not a structural break. For information-set decoding against code-based schemes, an analogous quantum-walk-based ISD (Bernstein-Jeffery-Lange-Meurer and follow-on work) similarly gives a modest, sub-quadratic-but-real speedup over the classical ISD family, again nowhere near Shor's exponential-to-polynomial collapse.

Collision-finding: BHT and its practical caveat. The Brassard-Hoyer-Tapp (BHT) algorithm finds collisions in a random function using roughly $O(2^{n/3})$ quantum queries, versus the classical birthday bound of $O(2^{n/2})$, a meaningful asymptotic improvement. The practical catch, and the reason this does not simply mean "halve your hash output length like you would for Grover-based preimage resistance," is that BHT's speedup requires a correspondingly large amount of QUANTUM-ACCESSIBLE MEMORY (qRAM) to realize the claimed query count, a resource widely considered unrealistic to build at the scale required for cryptographically meaningful $n$. This is exactly why NIST's PQC security categories are calibrated around the more conservative Grover-based PREIMAGE bound ($2^{n/2}$), not the more aggressive but memory-hungry BHT COLLISION bound, and it is exactly why hash-based signature designs (SPHINCS+/SLH-DSA) lean on tweakable, multi-target-resistant hash constructions specifically to reduce their reliance on full collision resistance wherever possible.

The quantum random oracle model (QROM) and what it changes about security proofs. A classical security proof in the random oracle model (ROM) assumes the adversary can only query the hash function on CLASSICAL inputs, one at a time, and observes classical outputs. A quantum adversary, by contrast, can query a hash function implemented as part of a larger quantum computation in QUANTUM SUPERPOSITION, potentially learning information about the function's behavior on exponentially many inputs simultaneously via a single query. A proof valid in the ROM is not automatically valid against this stronger adversary model; many classical ROM proof techniques (in particular, "rewinding" the adversary to extract information, a common ROM proof technique) do not straightforwardly carry over to the QROM, because quantum measurement is destructive and a quantum adversary's internal state cannot simply be "rewound and replayed" the way a classical adversary's query transcript can. This is why post-quantum scheme proposals need QROM-SPECIFIC security proofs, not merely "the same ROM proof, but now against a quantum adversary," and constructing QROM proofs has been an active, nontrivial research area in its own right (independent of whether the scheme's underlying hard problem is itself quantum-resistant).

Practical implications for parameter selection. For lattice and code-based schemes, the quantum-walk sieving/ISD speedups are folded into parameter selection as a modest ADDITIONAL exponent reduction on top of the classical attack cost (going from the classical $0.292d$-style exponent to the quantum $0.265d$-style exponent), not treated as a separate qualitative security category. For hash-based and any collision-resistance-dependent construction, Grover's PREIMAGE bound, not BHT's memory-hungry collision bound, is the conservative parameter-setting reference point. For schemes proved secure in the ROM, a genuinely QROM-VALID proof (not merely an unexamined assumption that the ROM proof "still basically works") is now a first-class requirement for the proposal to be taken seriously in the standardization process.

Trade-offs and pitfalls

• Common mistake: treating "quantum algorithm exists against this problem" as equivalent to "this problem is broken." Quantum-walk sieving and quantum ISD are real, incorporated-into-parameter-selection speedups, categorically different from Shor's algorithm's exponential-to-polynomial collapse; conflating the two overstates the near-term quantum threat to lattice and code-based schemes specifically.
• Common mistake: applying the Grover halving rule (double your key length) to collision resistance the same way it applies to preimage resistance. The correct conservative reference bound for collision resistance against a REALISTIC quantum adversary is still closer to Grover's preimage bound than to BHT's collision bound, precisely because BHT's qRAM requirement is not realistically available; treating BHT as the operative threat model would (over-conservatively, but for the wrong technical reason) inflate hash output-length requirements based on an unrealistic resource assumption.
• A scheme's underlying hard PROBLEM being quantum-resistant does not automatically make its security PROOF quantum-resistant. These are genuinely separate concerns: a lattice problem can remain hard against known quantum attacks while a specific scheme's ROM-based reduction proof still fails to establish security against a quantum adversary who can query the random oracle in superposition, which is exactly why QROM-specific proof work exists as its own research subfield.
• The NISQ-era practical threat (near-term noisy quantum hardware) is a DISTINCT concern from the algorithmic asymptotic-speedup question covered here; a technique with a proven asymptotic quantum advantage can still be completely impractical to run on any hardware that exists or is likely to exist soon, since realizing it needs fault-tolerant, error-corrected qubits and circuit depth far beyond what any noisy intermediate-scale device offers.

Direct answer

A security reduction is a proof technique showing that if an adversary can break a cryptographic scheme, that adversary can be used, as a subroutine inside another algorithm, to solve a problem believed to be hard, such as LWE or SIS. Reductions matter for post-quantum schemes specifically because the field is comparatively young: security is asserted relative to hardness assumptions rather than proven from first principles, and a reduction is what ties a scheme's concrete security back to those assumptions in a checkable way. The reduction's tightness, whether it preserves the adversary's advantage closely or loses a large factor, determines how literally a "128-bit secure" label should be trusted.

Structured elaboration

Tight vs. non-tight. A reduction $B$ that uses adversary $A$ (breaking the scheme with advantage $\epsilon_A$) to solve the hard problem gives a bound of the form

for some loss factor $L$. A tight reduction has $L=O(1)$, independent of the security parameter or query budget, so a break of the scheme translates almost directly into a break of the assumption. A non-tight (loose) reduction has $L$ growing with, for example, the number of oracle queries $Q$ an adversary is allowed (common in signature reductions using the forking lemma, where $L$ can scale like $Q$ or $Q^2$), meaning the scheme's proven security is meaningfully weaker than the assumed problem's security once the loss is accounted for.

Practical implications for parameter selection. If a reduction loses a factor $L$ and the design target is $\lambda$ bits of scheme security, the underlying hard-problem instance must actually be set to roughly $\lambda + \log_2 L$ bits to compensate (worked example below). Parameter selection that only looks up "LWE is $\lambda$-bit secure at these parameters" without checking the reduction's loss factor silently under-provisions security whenever the reduction is loose.

Practical implications for confidence in a scheme. A tight reduction to a well-studied problem is close to the strongest assurance a scheme can offer short of a first-principles proof: an attacker who breaks the scheme has, almost for free, also broken the assumption. A loose reduction still provides genuine assurance, but practical confidence then rests partly on cryptanalytic experience against the scheme's specific construction, not purely on the assumption's hardness. Several NIST PQC lattice signature schemes have reductions that are heuristic or non-tight in the deployed parameter regime, which is why their published parameter sets carry a deliberate margin beyond the bare reduction's requirement.

Random-oracle model (ROM) vs. standard model. Many efficient reductions, particularly Fiat-Shamir-style constructions common in lattice signatures, only go through if a hash function is modeled as a truly random oracle. This is a heuristic: no real hash function is a random oracle, and there exist contrived schemes provably secure in the ROM that are provably insecure for every real instantiation of the hash function (Canetti, Goldreich, and Halevi's 1998 uncomputability separation). Standard-model reductions avoid this idealization at the cost of being harder to construct and often less efficient, which is why high-assurance contexts (long-lived root keys, formally verified systems) sometimes explicitly favor standard-model constructions despite the efficiency cost, while most deployed PQC signatures accept the ROM heuristic given decades without it failing for well-designed schemes.

Worked example

The loss-factor arithmetic is simple exponent bookkeeping, worth doing explicitly rather than eyeballed. Suppose a reduction loses $L=2^{40}$ (from a forking-lemma bound on $Q=2^{40}$ hash queries), targeting $\lambda=128$ bits of scheme security:

target_adv_exp, loss_exp = 128, 40
print(target_adv_exp + loss_exp)   # 168

The underlying hard-problem instance needs roughly 168-bit hardness, not 128-bit, to deliver a genuinely 128-bit-secure scheme once this reduction's loss is accounted for. A "128-bit security" claim resting on this reduction without inflating parameters overstates its assurance by exactly the loss factor.

Trade-offs and pitfalls

• "A reduction exists" is not a binary pass/fail check. The most common mistake is treating "the scheme has a proof" as sufficient without checking tightness and against what problem; a reduction with an exponential loss factor provides far less than a tight reduction to a well-studied worst-case-hard problem.
• Asymptotic vs. concrete security. Reductions are usually stated asymptotically; real parameter selection needs the concrete loss factor as an explicit number, exactly the distinction the worked example makes.
• Heuristic security is common and should be labeled as such. Several practical lattice signature schemes rely on reductions that are non-tight or partly heuristic at deployed parameters; NIST's selected schemes compensate with conservative margins validated by extensive cryptanalysis rather than resting purely on the formal bound.

Direct answer

Lattice implementations leak through timing (data-dependent branches or variable-latency operations), cache access patterns (secret-dependent table lookups or memory addresses), and electromagnetic (EM) radiation correlated with the specific data being processed during the number-theoretic transform (NTT) and discrete Gaussian or centered-binomial sampling, the two operations that touch every secret coefficient directly. Mitigations exist at three layers, algorithmic (redesign the operation to have no secret-dependent control flow at all), code-level (constant-time implementation techniques applied to an already side-channel-aware algorithm), and hardware (physical shielding, masking, and noise injection), and effective defense in practice requires layering more than one, because each layer alone leaves gaps the others close.

Structured elaboration

Timing leakage sources. A secret-dependent branch (an if statement whose condition depends on a secret coefficient's sign or magnitude) is the classic timing leak: the two branches take measurably different time, and an attacker who can query the operation many times and average out noise recovers the branch outcome, hence the secret bit, statistically. In lattice schemes specifically, this shows up in rejection sampling (a variable number of loop iterations depending on the secret, the same branch-timing leak just described), in modular reduction routines that branch on whether a value needs correction, and in polynomial comparison/rounding steps used in encoding.

Cache leakage sources. A table-indexed lookup where the index depends on secret data (a precomputed sampling table indexed by a secret-derived value, or an NTT twiddle-factor table accessed in a secret-dependent order) leaves a footprint in the CPU cache: an attacker sharing the same physical cache (a co-resident process, a hyperthread sibling, or a malicious neighbor in a shared cloud environment) can observe WHICH cache lines were touched (Prime+Probe, Flush+Reload, and related techniques) and infer the secret-dependent index sequence.

EM leakage sources during NTT and sampling. The NTT processes every coefficient of the secret or error polynomial through a sequence of butterfly operations whose power draw and radiated EM signature correlate, coefficient by coefficient, with the DATA VALUE being multiplied and added, not just which instruction executes; similarly, a discrete Gaussian sampler's internal comparisons and table accesses correlate with the specific sampled value. Because these operations touch EVERY secret coefficient in a predictable, repeated pattern (the same butterfly structure runs once per coefficient), EM/power side-channel attacks against NTT and sampling are unusually EFFICIENT relative to attacking a single comparison once: an attacker gets many independent leakage traces (one per coefficient) from a SINGLE execution, enabling statistical techniques (differential power analysis, template attacks) that need far fewer physical measurements than attacking a single secret bit would.

Mitigations, by layer.

Trade-offs and pitfalls

• Algorithmic and code-level mitigations address DIFFERENT root causes and neither substitutes for the other. An algorithm redesigned to be branch-free (algorithmic layer) can still leak if the COMPILER reintroduces a data-dependent branch during optimization, or if the underlying CPU's instruction timing is itself secretly data-dependent (variable-latency multiply on some processors); code-level constant-time discipline and verification is what catches this class of gap, which algorithmic redesign alone cannot guarantee.
• Masking is not free security and does not compose trivially. A masking scheme correct for ONE operation (say, a masked addition) does not automatically remain secure when composed with a masked multiplication unless the composition is specifically analyzed; a common, real implementation defect is a "leaky" transition point between two otherwise-correctly-masked operations, where partial unmasking happens implicitly.
• Common mistake: treating constant-time code as sufficient defense against ALL the leakage sources named here. Constant-time discipline directly addresses timing and (with additional care around memory-access patterns) cache leakage, but does essentially nothing against power/EM leakage, which correlates with DATA VALUES processed at constant time, not with which instructions ran; EM/power defense specifically requires the hardware-layer mitigations (masking, shielding), a genuinely separate defense investment.
• NTT and sampling deserve disproportionate defensive attention precisely because they touch every secret coefficient in a repeated, structurally predictable pattern, giving an attacker many leakage samples per execution; a defense budget that treats every operation in the scheme as equally leakage-sensitive is misallocated relative to where the actual per-execution information leakage is concentrated.