# Lattice Part 4: From SIS/ISIS to LWE


Micciancio-Regev’s lecture-note framing[^mr], Regev’s 2005 reduction[^regev], and Peikert’s 2009 encryption perspective[^peikert09] are the three anchors for this bridge chapter.

Part 0-3 already gave the lattice side: basis reduction, CVP/Babai intuition, SIS, and ISIS. Here we change only one ingredient, but it changes the entire cryptographic surface. The goal is to stabilize plain LWE first, not to preview structured lattices yet.

<!--more-->

## Reader State After Part 0-3

This article assumes only the objects already used in Part 0-3.

- A lattice is still a discrete additive subgroup generated by a basis:

$$
\mathcal{L}(B)=\{B\mathbf{x}:\mathbf{x}\in\mathbb{Z}^k\}.
$$

- CVP asks for a lattice point close to a target:

$$
\operatorname{dist}(\mathcal{L},\mathbf{t})=\min_{\mathbf{x}\in\mathcal{L}}\|\mathbf{x}-\mathbf{t}\|.
$$

- SIS and ISIS ask for short integer witnesses satisfying exact modular equations:

$$
A\mathbf{x}\equiv \mathbf{0}\pmod q,\qquad A\mathbf{x}\equiv \mathbf{u}\pmod q.
$$

The new object in this chapter is not a new kind of lattice geometry. It is the same modular linear algebra with one added displacement term. Part 3 ended with exact short preimages; Part 4 starts by asking what happens when the public equation is almost exact but not exactly solvable.

## From Exact Relations To Noisy Relations

### What Part 0-3 Already Gave Us

SIS and ISIS are still exact-relation problems. The instance is linear, the witness is short, and the algebraic target is crisp:

$$
A \mathbf{x} \equiv \mathbf{0} \pmod q
$$

or in the inhomogeneous case,

$$
A \mathbf{x} \equiv \mathbf{u} \pmod q.
$$

The verification interface is clear: exact short solutions are hard to find, but once found they are easy to check.

### Why Exact Solvability Is Too Clean

Exact relations are too algebraically stable. If the relation is noiseless, linear algebra keeps its full power: combine equations, eliminate variables, and the system stays exact.

That is good for mathematics, but bad for hiding. Public-key encryption wants a hardness source that looks random enough to outsiders while still being structured enough for the key owner to decode.

### Injecting The Error Term

Micciancio and Regev’s notation[^mr] is the cleanest way to write the model. Stack $m$ samples into a matrix and a vector:

$$
A \in \mathbb{Z}_q^{m \times n},\qquad \mathbf{s}\in\mathbb{Z}_q^n,\qquad \mathbf{e}\leftarrow \chi^m,\qquad \mathbf{b}=A\mathbf{s}+\mathbf{e}\pmod q.
$$

This is the model change from SIS/ISIS to LWE. The preserved pieces are the linear algebra and the modular arithmetic; the changed piece is the right-hand side, which is no longer exact.

- In SIS, the target is homogeneous: $A\mathbf{x}\equiv \mathbf{0}\pmod q$.
- In ISIS, the target is affine but still exact: $A\mathbf{x}\equiv \mathbf{u}\pmod q$.
- In LWE, the affine target is blurred by an error vector:

$$
A\mathbf{s}+\mathbf{e}\equiv \mathbf{b}\pmod q.
$$

This is exactly the step where exact linear relations become noisy relations under an added error term.

The useful mental replacement is:

$$
\text{exact modular equality} \quad\leadsto\quad \text{modular equality plus a small unknown displacement}.
$$

In Part 3, the witness $\mathbf{x}$ was the object one wanted to find. In LWE, the hidden object is usually the secret $\mathbf{s}$, while the small vector $\mathbf{e}$ is the obstruction that prevents direct linear solving.

If we apply any row-combination matrix $M$ to the samples, exact relations stay exact, but noisy relations carry their error with them:

$$
M\mathbf{b}=MA\mathbf{s}+M\mathbf{e}\pmod q.
$$

That is the bridge from SIS/ISIS to LWE: exact relations become hidden linear relations, and elimination no longer kills the witness-cleanly because it also carries the noise term forward.

### One-Sample Sanity Check

Take the one-dimensional toy case only to see the obstruction. Let $q=17$, secret $s=5$, public coefficient $a=3$, and error $e=1$. The sample is

$$
b=as+e=3\cdot 5+1\equiv 16\pmod {17}.
$$

If the equation had no error, the observer would solve it by multiplying by $a^{-1}=6$:

$$
6\cdot 15\equiv 5\pmod {17}.
$$

With the noisy sample, the same operation gives

$$
6\cdot 16\equiv 11\pmod {17},
$$

which is not the secret. This example is deliberately small and not cryptographic. Its only purpose is to isolate the algebraic change: inverse operations that are valid for exact modular equations do not remove the error term. With many samples, the attacker gets more linear information, but also more coupled noise.

The full LWE problem is the high-dimensional version of this obstruction. The secret is not hidden because modular arithmetic is unfamiliar; it is hidden because every equation has been shifted by a small integer that is unknown to the attacker.

### Rows, Columns, And What The Matrix Means

Part 3 used matrices mainly as collections of modular equations. LWE uses the same convention. If the rows of $A$ are $\mathbf{a}_1,\ldots,\mathbf{a}_m$, then

$$
A\mathbf{s}=
\begin{pmatrix}
\langle\mathbf{a}_1,\mathbf{s}\rangle \\
\vdots \\
\langle\mathbf{a}_m,\mathbf{s}\rangle
\end{pmatrix}.
$$

The public vector $\mathbf{b}$ is obtained by adding one small error to each row equation:

$$
b_i=\langle\mathbf{a}_i,\mathbf{s}\rangle+e_i\pmod q.
$$

So an LWE instance can be read as $m$ approximate modular equations in the same hidden vector $\mathbf{s}$.

## Formal Definition Of Search-LWE And Decision-LWE

### Notation And Parameter Convention

For this note, $q$ is a modulus, usually prime or at least chosen so that the required modular arithmetic is well behaved. Vectors over $\mathbb{Z}_q$ are written in bold. When a residue is used inside a norm or an error bound, I implicitly take its centered representative in $(-q/2,q/2]$.

The main parameters are:

- $n$: the LWE dimension, i.e. the length of the hidden secret $\mathbf{s}$;
- $m$: the number of samples available to the adversary;
- $q$: the modulus;
- $\chi$: an error distribution over small integers, normally concentrated near zero;
- $\alpha q$: the heuristic noise scale when one writes $\chi$ as a discretized Gaussian-like distribution of width about $\alpha q$.

For a fixed secret $\mathbf{s}\in\mathbb{Z}_q^n$, write $A_{\mathbf{s},\chi}$ for the distribution of samples

$$
(\mathbf{a},b)=(\mathbf{a},\langle \mathbf{a},\mathbf{s}\rangle+e)\in \mathbb{Z}_q^n\times\mathbb{Z}_q,\qquad \mathbf{a}\leftarrow\mathbb{Z}_q^n,\ e\leftarrow\chi.
$$

This notation separates the public sampling process from the hidden parameter. The matrix form $(A,\mathbf{b})$ is just $m$ independent draws stacked into rows.

### The Search Form

Following Micciancio-Regev’s sample notation[^mr], the search problem is: given $(A,\mathbf{b})$ with $\mathbf{b}=A\mathbf{s}+\mathbf{e}\pmod q$, recover $\mathbf{s}$. Equivalently, given many samples from $A_{\mathbf{s},\chi}$, find the hidden parameter $\mathbf{s}$. Written one sample at a time,

$$
(\mathbf{a}_i, b_i) \in \mathbb{Z}_q^n \times \mathbb{Z}_q,\qquad
b_i = \langle \mathbf{a}_i, \mathbf{s}\rangle + e_i \pmod q,\quad e_i \leftarrow \chi.
$$

The search problem is to recover $\mathbf{s}$ from many such samples, i.e. to invert the hidden affine map behind the noise. In reductions, this is the algebraic hardness core; in the protocol, it is usually hidden behind the indistinguishability claim the attacker actually sees.

If $\mathbf{e}=\mathbf{0}$ and a square submatrix of $A$ is invertible modulo $q$, this would collapse to ordinary modular linear algebra:

$$
\mathbf{s}=A^{-1}\mathbf{b}\pmod q.
$$

With errors, the equation is really

$$
A\mathbf{s}=\mathbf{b}-\mathbf{e}\pmod q,
$$

but $\mathbf{e}$ is unknown. The attacker is therefore not solving one clean system; it is trying to infer both the hidden linear parameter and the small displacement attached to every row.

### The Decision Form

In decision-LWE, the task is to distinguish samples of the above form from uniform samples in $\mathbb{Z}_q^n \times \mathbb{Z}_q$.

Formally, for a distinguisher $\mathcal{D}$, the advantage is measured by

$$
\left|\Pr_{\mathbf{s},A,\mathbf{e}}[\mathcal{D}(A,A\mathbf{s}+\mathbf{e})=1]-\Pr_{A,\mathbf{u}}[\mathcal{D}(A,\mathbf{u})=1]\right|.
$$

Here $\mathbf{u}\leftarrow\mathbb{Z}_q^m$ is uniform and independent of $A$. This is the cryptographic face of LWE. Search-LWE says the secret is hard to recover; decision-LWE says the ciphertext-like samples are hard to tell from random. Peikert’s 2009 public-key construction uses exactly this distinction[^peikert09]: the attacker does not get an oracle that says “recover the secret”; it gets a sample and must decide whether the sample is structured or uniform.

### Parameters And Distributions

The distributional model depends on three distributions:

- $\mathbf{a}_i \leftarrow \mathbb{Z}_q^n$ uniformly
- $\mathbf{s} \leftarrow \mathbb{Z}_q^n$ or a structured secret distribution
- $e_i \leftarrow \chi$ concentrated near zero

The clean relation is now hidden under a small perturbation. Two constraints pull in opposite directions. If $\chi$ is too narrow, the samples approach a solvable noisy linear system. If $\chi$ is too wide, decryption in later constructions cannot reliably distinguish the encoded message from accumulated error. Micciancio and Regev’s survey framing[^mr] is important here because it keeps the algebraic object and the cryptographic claim separate: the sample matrix is elementary, but the assumption about its distribution is the security content.

## Why Noise Makes Linear Algebra Hard

### Elimination Fails Gracefully, Not Catastrophically

Suppose we have two samples

$$
b_1 = \langle \mathbf{a}_1,\mathbf{s}\rangle + e_1,\qquad
b_2 = \langle \mathbf{a}_2,\mathbf{s}\rangle + e_2 \pmod q.
$$

If the system were exact, we could eliminate coordinates by taking linear combinations. With noise, the same operation drags the error along:

$$
\begin{aligned}
\alpha b_1 + \beta b_2
&=
\langle \alpha \mathbf{a}_1 + \beta \mathbf{a}_2,\mathbf{s}\rangle \\
&\quad +(\alpha e_1+\beta e_2)\pmod q.
\end{aligned}
$$

So the signal combines linearly, but the error does too. Repeated elimination does not erase noise; it accumulates it.

### Signal Versus Error Accumulation

If one tries to recover $\mathbf{s}$ by solving a large linear system, the small errors become the obstruction. The exact algebraic dependency is still there, but it is buried under many correlated perturbations.

This is the key difference from SIS/ISIS:

$$
\text{exact relation} \Rightarrow \text{kernel / preimage search}
$$

while

$$
\text{noisy relation} \Rightarrow \text{hidden point estimation under perturbation}.
$$

### Why This Is Not Just Numerical Analysis

This is not floating-point instability. The arithmetic is exact modulo $q$. The hardness comes from a discrete decoding problem with structured noise, not from numerical approximation error.

## Geometry Behind The Reduction Story

### BDD Intuition Reappears

LWE can be viewed as a noisy closest-vector instance. Lift the modular relation to integer representatives and consider the standard q-ary lattice[^mr]

$$
\Lambda=\{ \tilde A \mathbf{x} + q\mathbf{z} : \mathbf{x}\in \mathbb{Z}^n,\ \mathbf{z}\in \mathbb{Z}^m \}.
$$

Then the noiseless part $\tilde A \mathbf{s}$ is a lattice point in that lattice, and the sample satisfies

$$
\tilde{\mathbf b}=\tilde A\mathbf{s}+\mathbf e-q\mathbf z
$$

for some integer vector $\mathbf z$. If $\mathbf e$ is short, then $\tilde{\mathbf b}$ lies within the decoding radius of the lattice point $\tilde A\mathbf s$. This is exactly how the noisy equation picture connects back to BDD-style geometry: the target is a nearby exact lattice point plus a short offset. The public matrix determines the signal geometry, and the attacker must recover that nearby exact point from the displaced target. The sample is not arbitrary noise in Euclidean space; it is a structured perturbation of the exact relation encoded by the secret.

The distance relation is the part worth keeping explicit:

$$
\operatorname{dist}(\tilde{\mathbf b},\Lambda)\le \|\mathbf e\|.
$$

The decoding problem is not to solve $A\mathbf{s}=\mathbf{b}$ exactly; it is to identify the lattice point $\tilde A\mathbf{s}-q\mathbf z$ hidden within an error ball. This is why the LWE picture naturally inherits the BDD language from the earlier lattice chapters.

### Worst-Case To Average-Case At A High Level

Regev’s theorem is the conceptual break[^regev]: average random-looking LWE samples are at least as hard as canonical worst-case approximate lattice problems such as SIVP and GapSVP, under a worst-case-to-average-case reduction. Micciancio-Regev’s lecture-note framing[^mr] is useful here because it makes clear what the theorem really transfers: hardness of a broad lattice family, not a proof that one concrete parameter set is immune to all attacks.

So the reduction chain is:

$$
\text{worst-case lattice hardness} \Longrightarrow \text{average-case LWE hardness}.
$$

### What Confidence The Reduction Actually Buys

The reduction does not prove every parameter set secure, and it does not rule out parameter-specific or implementation-specific attacks. What it does buy is structural confidence: if you had a good average-case solver for LWE, the reduction would turn it into a solver for hard worst-case lattice problems on arbitrary lattices, up to polynomial losses and the reduction’s own model assumptions[^regev].

That is much stronger than “this instance family seems hard in practice,” but it is still a theorem about hardness transfer, not a certificate of concrete security.

## Why This Assumption Is The Start Of Modern Lattice Encryption

### From Hardness Assumption To Encryption Template

Once noisy relations are hard to distinguish or solve, encryption becomes natural:

- encode a message in the relation
- add a secret-dependent mask
- hide the message behind small noise
- decrypt by using the secret to remove the structured part before the noise grows

The geometry is simple: the ciphertext is a perturbed object, and the secret is the trapdoor that identifies the right nearby point.

### Why Search And Decision Both Matter

Search-LWE explains the secret-recovery hardness: if you already know the sample matrix, the secret is still buried behind the noise. Decision-LWE is the public-key security interface: the adversary sees a matrix and a vector, and the claim is that this pair is computationally indistinguishable from uniform.

That split matters. A public-key encryption proof needs indistinguishability, not just hidden secret recovery, because ciphertext security is about what the attacker can tell from the outside. Search-LWE is the underlying algebraic problem; decision-LWE is the cryptographic claim that Peikert’s 2009 construction is actually built to use[^peikert09].

### Minimal Encryption Algebra

A stripped-down dual-Regev / Peikert-style encryption skeleton shows why the decision form is the right interface. Put the public samples as columns:

$$
A\in\mathbb{Z}_q^{n\times m},\qquad \mathbf{t}=A^T\mathbf{s}+\mathbf{e}\in\mathbb{Z}_q^m.
$$

The public key is $(A,\mathbf{t})$. To encrypt one bit $\mu\in\{0,1\}$, choose a sparse or short selector $\mathbf{r}\in\{0,1\}^m$ and publish

$$
\mathbf{c}_1=A\mathbf{r},\qquad c_2=\langle \mathbf{t},\mathbf{r}\rangle+\left\lfloor q/2\right\rfloor\mu \pmod q.
$$

The secret key $\mathbf{s}$ removes the structured part:

$$
\begin{aligned}
c_2-\langle \mathbf{s},\mathbf{c}_1\rangle
&=
\langle A^T\mathbf{s}+\mathbf{e},\mathbf{r}\rangle-\langle \mathbf{s},A\mathbf{r}\rangle+\left\lfloor q/2\right\rfloor\mu \\
&=
\langle \mathbf{e},\mathbf{r}\rangle+\left\lfloor q/2\right\rfloor\mu \pmod q.
\end{aligned}
$$

Correctness is the small-noise condition: if $|\langle \mathbf{e},\mathbf{r}\rangle|$ stays well below $q/4$ in centered representatives, the receiver decodes whether the result is near $0$ or near $q/2$. Security is the decision-LWE condition: the public vector $\mathbf{t}$ should look uniform to an adversary without $\mathbf{s}$, so the mask induced by $\mathbf{r}$ hides the message.

### What The Next Article Will Add

Plain LWE is enough to stabilize the modern assumption. It is not yet enough to explain why practical schemes move to quotient rings, module structure, and fast polynomial arithmetic.

That is the boundary with Part 5. Nothing in Ring-LWE, Module-LWE, NTRU, or Kyber replaces the noisy-relation model established here. Those constructions inherit it, then add algebraic structure to compress representation and accelerate arithmetic.

## Conclusion

SIS and ISIS live on exact relations. LWE keeps the linear structure but injects a noise term that prevents clean elimination, turns decoding into BDD-flavored geometry, and admits worst-case-to-average-case reductions. That combination is why LWE becomes the foundation for modern lattice encryption.

This note stops here: the plain LWE baseline is now stable enough for the structured variants in Part 5.

## References

Suggested reading order:

1. Micciancio-Regev for the notation, q-ary lattice viewpoint, and BDD connection.
2. Regev 2005 for the original worst-case-to-average-case theorem and the quantum reduction context.
3. Peikert 2009 for the encryption-facing view of decision-LWE and public-key construction syntax.

[^mr]: Daniele Micciancio and Oded Regev, *Lattice-based Cryptography*.
[^regev]: Oded Regev (2005), *On lattices, learning with errors, random linear codes, and cryptography*.
[^peikert09]: Chris Peikert (2009), *Public-key cryptosystems from the worst-case shortest vector problem: extended abstract*.