Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
Every lattice-based HE scheme — and every FHE scheme worth using in 2024 is lattice-based — encrypts a message by adding it to a small noise term sampled from a discrete Gaussian. This is what makes the scheme secure: distinguishing 'message plus small noise' from 'uniform random' is exactly the Learning-With-Errors problem. But it's also the mechanism that makes HE expensive: every homomorphic operation grows the noise, additions linearly and multiplications quadratically, and once the noise crosses a threshold the ciphertext stops decrypting correctly. So the parameter that ultimately controls cost — ring dimension, modulus size, key size, runtime — is your noise budget. Understanding noise is understanding why FHE is slow and why the headlines about 'a 100x speedup' are usually about noise management. If you skip this, the rest of HE feels like magic; if you internalize it, the rest is engineering.
A typical LWE-style ciphertext is , where is the secret, is small Gaussian noise, is a scaling factor that places the message in the high bits, and is the ciphertext modulus. Decryption recovers by computing and then rounding away the noise. Adding two ciphertexts adds their noise terms (linear growth). Multiplying two ciphertexts roughly multiplies their noise terms (quadratic growth). Once , the rounding fails and the message is lost.
Use these three in order. Each builds on the one before.
In one paragraph, explain *why* lattice HE schemes need to add noise to ciphertexts at all, and what would go wrong if we tried to remove it. (Hint: think about what 'security' means here.)
Walk me through how noise grows under homomorphic addition vs. multiplication. Why is multiplication's growth quadratic in the noise rather than linear, and how does relinearization (a step we'll meet later) help control it?
Suppose I want to evaluate a circuit of multiplicative depth 10 in BFV. Walk me through how I'd pick $q$, the ring dimension $n$, and the noise parameter $\sigma$ to make decryption succeed *and* hit the 128-bit security level. Where does the lattice-estimator come in?
b_prod = b1 * b2// main.go
// Toy LWE-style scalar 'encryption' in 1 dimension to feel the noise growth.
// Real schemes are over polynomial rings; here we just track the noise envelope.
package main
import (
"fmt"
"math"
"math/rand"
)
const (
q = int64(1) << 40 // ciphertext modulus
Delta = int64(1) << 30 // plaintext scaling
sigma = 3.2 // Gaussian std-dev for noise
)
func noise(rng *rand.Rand) int64 {
// Discrete Gaussian-like sample.
return int64(math.Round(rng.NormFloat64() * sigma))
}
type CT struct{ a, b int64 }
func enc(m int64, s int64, rng *rand.Rand) (CT, int64) {
a := rng.Int63n(q)
e := noise(rng)
b := ((a*s + Delta*m + e) % q + q) % q
return CT{a, b}, e // return noise alongside for instrumentation
}
func dec(ct CT, s int64) int64 {
raw := ((ct.b - ct.a*s) % q + q) % q
if raw > q/2 {
raw -= q
}
return int64(math.Round(float64(raw) / float64(Delta)))
}
func main() {
rng := rand.New(rand.NewSource(0))
s := int64(17)
ct, e := enc(7, s, rng)
fmt.Printf("decrypts: %d noise magnitude: %d\n", dec(ct, s), abs(e))
// Add 1000 ciphertexts homomorphically — addition grows noise linearly.
total := ct
totalNoise := e
for i := 0; i < 999; i++ {
nct, ne := enc(7, s, rng)
total = CT{
a: (total.a + nct.a) % q,
b: (total.b + nct.b) % q,
}
totalNoise += ne
}
fmt.Printf("after 1000 adds — sum: %d noise magnitude: %d\n", dec(total, s), abs(totalNoise))
fmt.Printf("threshold (q / 2*Delta): %d\n", q/(2*Delta))
}
func abs(x int64) int64 {
if x < 0 {
return -x
}
return x
}
go run main.go