Full correctness of noisy homomorphic evaluation.
ProvedFHENoise.NoiseCkt.decrypt_evalEncaether-catalogcryptography
Full correctness of noisy homomorphic evaluation. A decoder dec that
recovers the plaintext class from any phase of gauge size < T returns the
plaintext circuit value, provided the syntactic noise bound stays below T.
theorem FHENoise.NoiseCkt.decrypt_evalEnc{M : Type*} [CommRing M] {D T : ℝ} (G : NoiseGauge R) (s : R)
(pi : R →+* M) (dec : R → M)
(hdec : ∀ x, G.nu x < T → dec x = pi x)
(relin : Cipher R → Cipher R)
(hrelinN : ∀ c, G.nu (phase s (relin c) - phase s c) ≤ D)
(hrelinP : ∀ c, pi (phase s (relin c)) = pi (phase s c))
(rho : ℕ → Cipher R) (beta : ℕ → ℝ) (hleaf : ∀ i, noise G s (rho i) ≤ beta i)
(f : NoiseCkt) (hbudget : f.noiseBound G.gamma D beta < T) :
dec (phase s (f.evalEnc relin rho)) = f.evalPlain (fun i => pi (phase s (rho i))) := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Cryptography/FHE/NoiseGrowth.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Cryptography/FHE/NoiseGrowth.lean
import Mathlib
import Definitions.Def_Cryptography_FHE_NoiseGauge
import Definitions.Def_Cryptography_FHE_NoiseGrowth
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 `ℤ`.
-/
open FHENoise
-- open removed: section is not a namespace
noncomputable section
variable {R : Type*} [CommRing R]
/-! ## 1. Ciphertexts as polynomials in the secret key -/
/-! ## 2. Noise of a ciphertext relative to a gauge -/
variable (G : NoiseGauge R)
/-! ## 3. The exact BGV multiplication noise term -/
/-! ## 4. Circuits, evaluation with relinearization, and the master bound -/
open NoiseCkt
/-! ## 5. The algebraic layer: relinearization never disturbs the plaintext -/Formal statement
theorem FHENoise.NoiseCkt.decrypt_evalEnc{M : Type*} [CommRing M] {D T : ℝ} (G : NoiseGauge R) (s : R)
(pi : R →+* M) (dec : R → M)
(hdec : ∀ x, G.nu x < T → dec x = pi x)
(relin : Cipher R → Cipher R)
(hrelinN : ∀ c, G.nu (phase s (relin c) - phase s c) ≤ D)
(hrelinP : ∀ c, pi (phase s (relin c)) = pi (phase s c))
(rho : ℕ → Cipher R) (beta : ℕ → ℝ) (hleaf : ∀ i, noise G s (rho i) ≤ beta i)
(f : NoiseCkt) (hbudget : f.noiseBound G.gamma D beta < T) :
dec (phase s (f.evalEnc relin rho)) = f.evalPlain (fun i => pi (phase s (rho i))) := by sorrySource