lattice security: why noise matters

lattice-based cryptography derives its security from the hardness of finding short vectors in high-dimensional lattices. the noise in Ring-LWE is not a bug — it is the security mechanism. without noise, the system is trivially breakable. with noise, it resists all known attacks, including quantum.

the Ring-LWE problem

the Ring Learning with Errors problem, defined over R_q = F_p[x]/(x^n+1):

given: a ← uniform(R_q),  s ← small(R_q),  e ← small(R_q)
       b = a * s + e

find: s

a is a known random ring element. s is a secret with small coefficients. e is an error term with small coefficients. the product a * s is a ring multiplication. the adversary sees (a, b) and must recover s.

without the error e: b = a * s, so s = a^{-1} * b. trivially solvable by ring element inversion. the error is what makes the problem hard.

why noise creates hardness

the error e masks the exact value of a * s. the adversary knows b = a * s + e but cannot separate the signal (a * s) from the noise (e). this is an information-theoretic barrier: many different pairs (s, e) are consistent with the observed (a, b).

the geometric interpretation: the lattice generated by a has points at a * s for each s. the observed b = a * s + e is close to a lattice point but not on it. finding the nearest lattice point is the Closest Vector Problem (CVP) — known to be NP-hard in the worst case and believed hard on average for random lattices.

the noise budget

in FHE, a ciphertext is a Ring-LWE sample: (c_0, c_1) where c_0 + c_1 * s is close to the message. "close" means: the decryption noise is bounded.

decrypt(c_0, c_1, s) = c_0 + c_1 * s = m + e

if |e| is small enough (below a threshold), m can be recovered exactly. if |e| grows too large, decryption fails.

every homomorphic operation increases the noise:

operation              noise growth
──────────────────     ────────────────────────
addition               +1 bit (noise roughly doubles)
plaintext multiply     noise scales by plaintext norm
ciphertext multiply    noise squares + log₂(n) bits
key switching          adds fixed noise from switching key
rotation (automorphism) adds fixed noise from evaluation key

the noise budget is the gap between the current noise level and the maximum tolerable noise. once the budget is exhausted, decryption fails.

tracking noise in jali

jali models noise as a log₂ bound — an integer representing the bit-length of the noise:

NoiseBudget {
  log_bound: u32     // log₂ of the L∞ noise bound
}

conservative (worst-case) tracking:

after_add:  log_bound = max(a.log_bound, b.log_bound) + 1
after_mul:  log_bound = a.log_bound + b.log_bound + log₂(n)
after_key_switch:  log_bound = max(current, ks_noise)
after_bootstrap:   log_bound = bootstrap_noise (fixed reset)

the multiplication rule is the critical one: each multiplication roughly doubles the noise exponent. a chain of L multiplications grows noise exponentially in L. this is why FHE without bootstrapping supports only a bounded number of multiplications (leveled FHE).

bootstrapping: noise reset

Gentry's breakthrough (2009): evaluate the decryption circuit homomorphically. the output is a fresh ciphertext with reset noise. the cost is enormous — one bootstrap is roughly 10^6 ring multiplications — but it allows unlimited computation.

before bootstrap: noise = high (nearly exhausted)
bootstrap: homomorphically decrypt and re-encrypt
after bootstrap: noise = low (fresh)

bootstrapping is the reason FHE works at all. and it is the reason jali's performance matters: the bootstrap circuit is dominated by ring multiplications and automorphisms.

noise in proofs (zheng)

when zheng proves correctness of FHE computation, it must verify that the noise remained within bounds at every step. the naive approach:

generic: 64 constraints per coefficient per operation (range check)
         n coefficients × m operations = 64nm constraints

the ring-aware approach (using jali's noise model):

ring-aware: running accumulator, fold noise bound per step
            check once at bootstrapping boundary
            ~30 field ops per fold step

the savings come from tracking the noise bound algebraically rather than range-checking every coefficient independently. this is the noise-tracking analog of the 3072x savings from NTT-based ring multiplication.

security parameters

the security of Ring-LWE depends on three parameters: the ring dimension n, the modulus q (here q = p, the Goldilocks prime), and the noise distribution.

n = 1024, q ~ 2^64:  ~128-bit security
n = 2048, q ~ 2^64:  ~192-bit security
n = 4096, q ~ 2^64:  ~256-bit security

these estimates assume the best known lattice attacks (BKZ with progressive sieving). the quantum speedup for lattice problems is modest — Grover gives a sqrt improvement on sieving, reducing security by roughly n/7 bits. post-quantum security remains well above the classical threshold.

the hardness landscape

problem	classical	quantum	status
Ring-LWE (n=1024)	2^128	2^110	conjectured hard
Module-LWE (k*n=1024)	2^128	2^110	NIST standard (ML-KEM)
NTRU (n=1024)	2^128	2^110	alternative, similar security
ideal-SVP (n=1024)	2^128	2^110	no known quantum advantage beyond generic

no quantum polynomial-time algorithm is known for any of these problems. lattice cryptography is the leading candidate for post-quantum security, and Ring-LWE over cyclotomic rings (jali's domain) is the most studied and deployed instantiation.

Dimensions

lattice-security

jali/docs/explanation/lattice-security.md