Aether Catalog definitions — Cryptography_FHE_NoiseGrowth
DefinitionCryptography_FHE_NoiseGrowthaether-catalogcryptography
Definition bundle for the Aether Catalog module Cryptography.FHE.NoiseGrowth, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Cryptography/FHE/NoiseGrowth.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Cryptography_FHE_NoiseGauge
import Definitions.Def_Cryptography_FHE_RingLWE
/-!
# Exact noise accumulation in BGV/BFV homomorphic evaluation
This file develops the *quantitative* layer that the catalog file
`Cryptography.FHE.RingLWE` leaves abstract: it tracks the actual size of the
decryption noise through homomorphic addition, multiplication, relinearization
(key switching) and bootstrapping, and proves that a circuit decrypts correctly
whenever an explicitly computed noise bound stays below the decoding radius.
## The model
A ciphertext is a **polynomial in the secret key**: `c = c₀ + c₁ X + c₂ X² + …`
with *phase* `phase s c = c.eval s`. This is the standard "extended
ciphertext" view: fresh BGV/BFV ciphertexts have degree `1`, and multiplication
of ciphertexts is exactly multiplication of these polynomials, so that
* `phase s (c + d) = phase s c + phase s d`,
* `phase s (c * d) = phase s c * phase s d`,
i.e. **the phase map is a ring homomorphism** (`phaseHom`). Relinearization is
modelled as *any* map `relin` that changes the phase by a small element of the
ideal `(t)` generated by the plaintext modulus — exactly what BGV key switching
guarantees. Correctness then splits into two independent obligations:
* an *algebraic* one: the phase, read modulo `t`, is the plaintext circuit value
(`NoiseCkt.phase_eval_mod`), true at every noise level;
* an *analytic* one: the phase norm stays under the decoding radius
(`NoiseCkt.noise_evalEnc_le`).
The main theorem `NoiseCkt.decrypt_evalEnc` combines them.
## Main results
* `phaseHom` — the phase is a ring homomorphism in the extended-ciphertext model,
compatible with the two-component ciphertexts of `RingLWEFHE`.
* `bgv_mul_noise_exact` / `bgv_mul_noise_bound` — the exact BGV multiplication
noise term `e·m' + m·e' + t·e·e'` and its gauge bound.
* `NoiseCkt.noise_evalEnc_le` — the master accumulation theorem: the noise of an
evaluated circuit is bounded by the syntactically computed `noiseBound`.
* `NoiseCkt.phase_eval_mod` — relinearization never disturbs the plaintext.
* `NoiseCkt.decrypt_evalEnc` — full correctness of noisy homomorphic evaluation.
* `noiseBound_le_iter` — the doubly exponential depth bound
`γ·N_d ≤ (γ·B)^(2^d)` in the relinearization-free regime, and
`mulChain_noise_eq` showing that this bound is *attained* over `ℤ`.
-/
namespace FHENoise
open Polynomial
noncomputable section
variable {R : Type*} [CommRing R]
/-! ## 1. Ciphertexts as polynomials in the secret key -/
/-- An *extended ciphertext*: the tuple `(c₀, c₁, …)` viewed as a polynomial in
the secret key. Fresh ciphertexts have degree ≤ 1. -/
abbrev Cipher (R : Type*) [CommRing R] := Polynomial R
/-- The phase (decryption function before decoding) of an extended ciphertext. -/
def phase (s : R) (c : Cipher R) : R := c.eval s
/-- The phase map is a ring homomorphism: this single fact is what makes
homomorphic addition and multiplication work at all. -/
def phaseHom (s : R) : Cipher R →+* R := Polynomial.evalRingHom s
/-- Embedding of the catalog's two-component ciphertexts `(a, b)` into the
extended model: `(a,b) ↦ b - a·X`. -/
def ofPair (c : RingLWEFHE.Ciphertext R) : Cipher R := C c.b - C c.a * X
/-! ## 2. Noise of a ciphertext relative to a gauge -/
variable (G : NoiseGauge R)
/-- The noise level of a ciphertext: the gauge size of its phase. -/
def noise (G : NoiseGauge R) (s : R) (c : Cipher R) : ℝ := G.nu (phase s c)
/-! ## 3. The exact BGV multiplication noise term -/
/-! ## 4. Circuits, evaluation with relinearization, and the master bound -/
/-- Arithmetic circuits over ciphertext wires. -/
inductive NoiseCkt where
| leaf : ℕ → NoiseCkt
| add : NoiseCkt → NoiseCkt → NoiseCkt
| mul : NoiseCkt → NoiseCkt → NoiseCkt
deriving Inhabited
namespace NoiseCkt
/-- Multiplicative depth. -/
def mulDepth : NoiseCkt → ℕ
| .leaf _ => 0
| .add f g => max f.mulDepth g.mulDepth
| .mul f g => max f.mulDepth g.mulDepth + 1
/-- Number of input wires (with multiplicity). -/
def leafCount : NoiseCkt → ℕ
| .leaf _ => 1
| .add f g => f.leafCount + g.leafCount
| .mul f g => f.leafCount + g.leafCount
/-- Homomorphic evaluation: additions are free, multiplications are followed by
relinearization. -/
def evalEnc (relin : Cipher R → Cipher R) (rho : ℕ → Cipher R) : NoiseCkt → Cipher R
| .leaf i => rho i
| .add f g => f.evalEnc relin rho + g.evalEnc relin rho
| .mul f g => relin (f.evalEnc relin rho * g.evalEnc relin rho)
/-- Plaintext semantics in an arbitrary commutative ring (used for the message
ring `R ⧸ (t)`). -/
def evalPlain {M : Type*} [CommRing M] (v : ℕ → M) : NoiseCkt → M
| .leaf i => v i
| .add f g => f.evalPlain v + g.evalPlain v
| .mul f g => f.evalPlain v * g.evalPlain v
/-- The syntactic noise bound of a circuit: leaves contribute their own bound,
additions add, multiplications multiply (with the expansion factor) and pay the
relinearization surcharge `D`. -/
def noiseBound (gamma D : ℝ) (beta : ℕ → ℝ) : NoiseCkt → ℝ
| .leaf i => beta i
| .add f g => f.noiseBound gamma D beta + g.noiseBound gamma D beta
| .mul f g => gamma * (f.noiseBound gamma D beta) * (g.noiseBound gamma D beta) + D
/-! ## 5. The algebraic layer: relinearization never disturbs the plaintext -/
/-! ## 5b. Modular composition of noise budgets -/
/-- Substitution of subcircuits into the input wires of a circuit. -/
def subst (f : NoiseCkt) (g : ℕ → NoiseCkt) : NoiseCkt :=
match f with
| .leaf i => g i
| .add f₁ f₂ => .add (subst f₁ g) (subst f₂ g)
| .mul f₁ f₂ => .mul (subst f₁ g) (subst f₂ g)
end NoiseCkt
/-! ## 6. Depth: the doubly exponential bound and its sharpness -/
/-- The relinearization-free noise iteration: `x ↦ γ x²`, `d` times. -/
def iterNoise (gamma : ℝ) : ℕ → ℝ → ℝ
| 0, x => x
| (d + 1), x => gamma * (iterNoise gamma d x) ^ 2
namespace NoiseCkt
/-- The balanced squaring circuit of multiplicative depth `d`. -/
def sqChain : ℕ → NoiseCkt
| 0 => .leaf 0
| (d + 1) => .mul (sqChain d) (sqChain d)
end NoiseCkt
end
end FHENoise