PQC Research Series — Part 2

Complexity Assumptions in Post-Quantum Cryptography: LWE, SIS, and the Limits of Reductionist Security

Author: Mayckon Giovani
Date: April 26, 2026
Series: PQC Research Series
Tags: PQC, Formal Methods, Cryptography, Systems

0. Context

Post-quantum cryptography is usually discussed as a migration exercise: replace ECDH with ML-KEM, replace RSA/ECDSA with ML-DSA / SLH-DSA, keep the rest. That framing is operationally convenient and mathematically incomplete.

Underneath the primitives, PQC is a statement about complexity assumptions: not only that certain lattice problems are hard, but that the particular distributions and structures we deploy are hard under the resource model we actually face. That “under” clause is the whole problem.

Reductionist security tends to overfit to the cleanest layer: “scheme $\Rightarrow$ LWE/SIS $\Rightarrow$ worst-case lattice hardness.” Systems security fails one layer earlier: the implementation and the operational environment frequently step outside the model (biased noise, correlated randomness, side-channel traces, non-atomic erasure, misconfigured parameters). If the reduction is a refinement map, those violations are breaking refinement.

1. Problem Statement

Fix a security parameter $\secpar \in \N$. Let $\proto_P$ be a PQC primitive instantiated at a concrete parameter set $P$ (dimensions, modulus, noise distribution, ring/module structure, compression rules, etc).

We would like a statement of the form:

under a hardness assumption $\mathsf{Hard}(P)$ such as LWE or SIS.

In theory, $\mathsf{Hard}(P)$ is defined in an idealized sampling and oracle model. In production, $\proto_P$ is realized by a stateful implementation $I_P$ running under system constraints (entropy sources, memory limits, microarchitectural leakage, concurrency schedules, firmware quirks). The real question is therefore not “is LWE hard?” but:

1. Which exact assumption is the proof actually using? (search-LWE vs decision-LWE, secret distribution, error distribution, structure, number of samples, oracle model). (1) (2)
2. What is the reduction loss and how does it translate to concrete parameters? Non-tightness is not a theoretical footnote; it is a sizing input. (3) (4)
3. Does the implementation preserve the model boundary? If $I_P$ does not sample from $\chi$, leaks timing, reuses randomness, or fails to erase secrets, then “security under LWE” is not even a well-posed claim.

So the formal problem is:

Define a model boundary $\mathcal{B}(P)$ for the deployed primitive, and prove (or at least bound) that the deployed system $(I_P)$ refines the ideal model required by the reduction.

This is the same engineering move you make when you prove a protocol implementation refines a TLA+ spec: you do not get correctness from a spec; you get correctness from a refinement argument that survives the real machine.

2. Formal Model

2.1 Lattices and worst-case problems

A (full-rank) lattice $\Lambda \subset \R^n$ can be represented by a basis matrix $B \in \R^{n \times n}$:

Let $\lambda_1(\Lambda)$ be the length of the shortest non-zero vector in $\Lambda$, and let $\lambda_i(\Lambda)$ denote the $i$-th successive minimum.

Two canonical worst-case approximation problems are:

• $\mathsf{GapSVP}_\gamma$: decide whether $\lambda_1(\Lambda) \le 1$ or $\lambda_1(\Lambda) > \gamma$ for approximation factor $\gamma$.
• $\mathsf{SIVP}_\gamma$: find $n$ linearly independent vectors in $\Lambda$ each of length at most $\gamma \cdot \lambda_n(\Lambda)$.

These are not just academic artifacts; they are the anchor points of worst-case/average-case reductions.

One additional object appears constantly in the LWE/SIS reduction chain: $q$-ary lattices induced by modular linear constraints. Given $A \in \Z_q^{m \times n}$, define:

This is the lattice-theoretic view of “solutions to $Ax=0 \bmod q$,” and it is the bridge between average-case modular samples and worst-case geometric statements.

2.2 Learning With Errors (LWE)

Let $n, m \in \N$, modulus $q \ge 2$, and an error distribution $\chi$ over $\Z$ (typically a discrete Gaussian or a centered bounded distribution). Sample:

and define:

The search-LWE problem is: given $(A,b)$ sampled as above, recover $s$.

The decision-LWE problem is: distinguish $(A, A s + e)$ from uniform $(A, u)$ where $u \gets \Z_q^m$.

Regev’s foundational result (and its refinements) relate average-case LWE to worst-case lattice problems in an explicit parameter regime. A usable engineering summary is:

For $q=\mathrm{poly}(n)$ and noise rate $\alpha$ with $\alpha q \gtrsim \sqrt{n}$, an efficient LWE solver would imply an efficient worst-case lattice solver for $\mathsf{GapSVP}$ / $\mathsf{SIVP}$ at approximation factor roughly $\tilde{O}(n/\alpha)$. (1) (2)

Regev’s original reduction is quantum; later work establishes comparable hardness under classical reductions in relevant regimes. (5)

Two details matter more than people admit:

1. Which distribution is assumed. Proofs typically state $\chi$ as a discrete Gaussian or a distribution with explicit tail bounds. Implementations often use centered binomial or other efficient samplers, which must be justified as “close enough” in the right sense for the specific proof obligations you are relying on. (3)
2. Which LWE flavor is assumed. Search/decision equivalences exist in many regimes, but they are not a magical black box; they can depend on $q$, on the secret distribution, and on how you treat noise. If your implementation deviates (small secret, compressed samples, non-i.i.d. noise), you need to know what you are implicitly assuming.

efficient LWE solvers imply efficient worst-case lattice solvers (for certain approximation factors), under explicit distributional assumptions. (1) (2) (5)

2.3 Short Integer Solution (SIS)

Let $A \gets \Z_q^{m \times n}$. The SIS problem with bound $\beta$ is to find a non-zero vector $x \in \Z^n \setminus \{0\}$ such that:

Equivalently, SIS asks for a short non-zero vector in the $q$-ary lattice $\Lambda_q^\perp(A)$.

SIS is the canonical collision / relation-finding hardness backbone for lattice-based hash functions and commitment-style components. Ajtai’s work is the root of the worst-case/average-case connection here: average-case short relations in random modular constraints imply worst-case hardness in lattice geometry. (6)

2.4 Structured variants: Ring-LWE and Module-LWE

Efficiency demands structure; security pays for it.

Let $R = \Z[x]/(f(x))$ with cyclotomic choices common in practice (e.g., $f(x)=x^N+1$ for power-of-two $N$), and $R_q = R / qR$.

• Ring-LWE samples $A,s,e$ in $R_q$ and defines $b = A s + e$ in the ring. The hardness reductions are to worst-case problems on ideal lattices, which is a narrower and more structured family than arbitrary lattices. (7)
• Module-LWE lives in $R_q^k$ (a module of rank $k$), interpolating between unstructured LWE (large $k$, less structure) and Ring-LWE ($k=1$, maximal structure). This is exactly the reason the NIST standards emphasize “module-lattice-based” constructions: it is the efficiency/security Pareto surface the community has converged on. (8)

The engineering takeaway is not “Ring bad, Module good.” The takeaway is: structure is an attack surface and the reduction story becomes more delicate as structure increases.

Concrete example: the ML-KEM parameter sets standardized in FIPS 203 instantiate a Module-LWE lineage over $R_q$ with $N=256$, $q=3329$, and module ranks $k \in \{2,3,4\}$ (corresponding to ML-KEM-512/768/1024). They do not use an “ideal discrete Gaussian”; they use efficient bounded samplers and explicit compression/rounding rules. Those are engineering choices, and they are part of the assumption surface area. (8)

2.5 Reduction loss and concrete security (why parameters get fat)

Reductions are rarely tight. In schematic form, a typical security proof looks like:

where $c(n)$ is polynomial and $\varepsilon(P)$ collects statistical distance terms, failure probabilities (e.g., decryption failures), and other “small” terms.

In asymptopia, “polynomial” is harmless. In production, $c(n)$ forces you to inflate parameters to recover a desired concrete margin. If you want to reason about bit-security, you need:

1. a reduction (often non-tight),
2. an attack cost model (heuristic),
3. and a mapping from that model to operational budgets (time, memory, parallelism, side-channel surface).

This is where the lattice estimator ecosystem exists: it is not part of the theorem, but it is part of deployment reality. (4) (9)

To make this concrete, the backbone of many classical lattice attacks is BKZ reduction. The quality of a reduced basis is often summarized by the root Hermite factor $\delta_0$ such that (heuristically):

where $\beta$ is the BKZ block size and $\det(\Lambda)$ is the lattice determinant. Under standard heuristics (GSA), a common approximation is:

The deployment-level problem is that $\beta$ is not just a parameter in a paper; it is an attacker knob trading time vs memory vs parallelism, and your “bit-security” estimate is a projection of that multidimensional optimization into a single scalar. That projection is where most engineering overconfidence lives. (4) (9)

flowchart TD
  A["Worst-case lattice hardness (GapSVP/SIVP)"] -->|reduction| B["Average-case assumption (LWE/SIS distribution)"]
  B -->|construction| C["Primitive (KEM / Signature)"]
  C -->|implementation| D["System artifact (CPU + RNG + memory + concurrency)"]
  D -->|observable traces| E["Adversary view"]
  E -->|attack selection| F["Concrete cost model (BKZ / sieving / BKW / hybrids)"]
  F -->|security margin| G["Operational claim ('128-bit', etc.)"]
  D -. breaks .-> B
  D -. breaks .-> C

3. System Constraints

This is the part formal papers cannot carry for you. If you operate in IIoT, distributed control planes, VPN endpoints, or globally deployed backend services, you do not get the “ideal sampler + ideal CPU + ideal leakage” model for free.

3.1 Distribution preservation is a correctness property

Suppose the proof requires error distribution $\chi$ but the implementation samples $\chi'$. Let $\Delta = \mathrm{SD}(\chi,\chi')$ be the statistical distance between the two single-sample distributions.

By a standard hybrid argument, for $m$ independent samples:

This is a hard bound on how much your implementation can drift before you have materially changed the assumed problem distribution.

In other words: sampler bias is not “implementation detail.” It is a parameter in the adversary’s distinguishing advantage.

3.2 Memory and cache behavior are part of the attacker interface

The LWE/SIS hardness games assume the adversary sees algebraic samples, not microarchitectural traces. Real code runs on CPUs that leak via timing, cache, branch predictors, and transient execution. This induces a leakage channel:

and the attacker’s observation is no longer $(A,b)$; it is $(A,b,\mathsf{Leak}(\cdot))$.

You do not get to hand-wave this away by calling it “side-channel hardening.” If leakage depends on secret-dependent control flow or memory access, the problem you are solving is not LWE; it is “LWE with a leakage oracle,” which is a different assumption.

Operationally, this forces concrete constraints:

• constant-time arithmetic for NTT/multiplication paths,
• constant-time sampling and rejection logic,
• no secret-dependent table indices,
• explicit zeroization of ephemeral secrets and intermediate buffers,
• avoiding shared mutable RNG state across concurrent sessions.

3.3 Determinism, concurrency, and entropy budgets

Distributed systems want determinism (reproducible builds, deterministic state machines) and often run in constrained environments (IIoT gateways, embedded devices, enclaves, containers with weak entropy at boot). That collides with lattice schemes in predictable ways:

• Entropy: ML-KEM-style primitives need fresh randomness per encapsulation; “reuse because it’s faster” is a catastrophe. (8)
• Concurrency: shared RNG state across goroutines/threads becomes a correlation gadget.
• Crash consistency: erasure is not atomic; you must treat “crash after keygen but before zeroization” as part of the adversary model.

If you want to be honest, the system boundary must state which of these are assumed and which are enforced.

4. Core Argument / Insight

The deep failure mode in PQC deployments is not that LWE/SIS become easy. The failure mode is that teams confuse:

• a reduction (a conditional implication in an ideal model),
• a parameter choice (a concrete instantiation sized using heuristic cost models),
• an implementation (a program that must preserve distribution and hide secrets),
• and a system (a stateful, concurrent, observable artifact operating under failure).

When those layers are collapsed into “we use lattice crypto, therefore quantum-safe,” the security claim becomes meaningless.

So the right way to think about LWE/SIS in systems engineering is to treat them as assumption interfaces with explicit obligations. A minimal obligation set looks like this:

1. Sampling obligations: error/secret sampling matches the assumed distribution within negligible distance; compression does not introduce exploitable bias; decryption failures are bounded and monitored.
2. Leakage obligations: constant-time boundaries for secrets; avoidance of secret-dependent memory access; hardened error paths.
3. Lifecycle obligations: keys and intermediate secrets are erased promptly; crash behavior does not leave long-lived secrets resident; “ephemeral” is enforced, not asserted.
4. Agility obligations: parameters and algorithms are versioned protocol objects; rollout and rollback are engineered, not improvised.

The reason this matters is that concrete security is not a theorem; it is an adversarial optimization problem.

You can write it as:

where $\text{model}$ encodes time, memory, parallelism, and (increasingly) quantum speedups. The uncomfortable point: $\mathsf{Work}_{\mathsf{alg}}$ is heuristic for the best attacks we know, and it changes over time. (3) (4)

The resulting posture should be adversarial and operational:

• assume estimator drift (new BKZ/sieving improvements),
• assume implementation faults (timing, RNG, error oracles),
• and design rollback paths as if you will need them.

5. Implications

For production systems, treating LWE/SIS correctly implies specific engineering decisions:

1. Treat parameter sets as part of the protocol version. If you cannot unambiguously name $P$ (including compression rules, domain separation, and failure semantics), you cannot reason about interoperability or downgrade surfaces.
2. Make distributional correctness testable. Sampler tests, statistical checks, and CI gates are not “nice-to-have.” They are how you maintain the refinement boundary.
3. Budget for memory-hardness and DoS. Lattice operations are attacker-triggerable (handshakes, key exchanges). Your availability model must treat expensive crypto as an attack surface, especially under packet loss and retries.
4. Formalize lifecycle invariants. “Ephemeral” means erased before the next adversarial event. Specify it like an invariant and enforce it like one.
5. Be explicit about structure. Ring/Module structure buys you performance. It must be treated as an explicit risk trade-off, with monitoring and agility, not as free security.

6. Continuity Hook

Part 1 defined adversary models (classical vs quantum vs QROM) by specifying interfaces and resource vectors. Part 2 defined LWE/SIS as assumption interfaces with concrete system obligations.

The next step is inevitable:

how do lattice hardness and reduction arguments change once the attacker is quantum, and how should we account for quantum time–memory trade-offs (and QROM interfaces) when sizing parameters for real systems?

That is Part 3: quantum cost models, coherence budgets, and what “post-quantum hardness” actually means in operational terms.

7. References

• Regev, “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography” (JACM). (1)
• Ajtai, “Generating Hard Instances of Lattice Problems” (STOC '96). (6)
• Micciancio & Regev, “Worst-Case to Average-Case Reductions Based on Gaussian Measures” (SIAM J. Comput.). (2)
• Brakerski et al., “Classical Hardness of Learning with Errors” (STOC '13). (5)
• Lyubashevsky, Peikert & Regev, “On Ideal Lattices and Learning with Errors over Rings” (EUROCRYPT 2010). (7)
• Chen & Nguyen, “BKZ 2.0: Better Lattice Security Estimates” (ASIACRYPT 2011). (4)
• Peikert, “A Decade of Lattice Cryptography” (FnT TCS). (3)
• NIST, “FIPS 203: ML-KEM” (CSRC). (8)
• Albrecht et al., “LWE estimator” (GitHub). (9)