Monotonicity of the syntactic bound in the leaf bounds.
ProvedFHENoise.NoiseCkt.noiseBound_monoaether-catalogcryptography
Monotonicity of the syntactic bound in the leaf bounds.
theorem FHENoise.NoiseCkt.noiseBound_mono{gamma D : ℝ} {beta beta' : ℕ → ℝ} (hg : 0 ≤ gamma) (hD : 0 ≤ D)
(hbeta : ∀ i, 0 ≤ beta i) (hle : ∀ i, beta i ≤ beta' i) :
∀ f : NoiseCkt, f.noiseBound gamma D beta ≤ f.noiseBound gamma D beta'
:= 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 NoiseCktFormal statement
theorem FHENoise.NoiseCkt.noiseBound_mono{gamma D : ℝ} {beta beta' : ℕ → ℝ} (hg : 0 ≤ gamma) (hD : 0 ≤ D)
(hbeta : ∀ i, 0 ≤ beta i) (hle : ∀ i, beta i ≤ beta' i) :
∀ f : NoiseCkt, f.noiseBound gamma D beta ≤ f.noiseBound gamma D beta'
:= by sorrySource