Gaussian mechanism , its privacy profile , and per-instance sensitivity bounds
DefinitionPFRelease_Supplement_gaussMechLet be the standard Gaussian CDF. The privacy profile of the Gaussian mechanism with standard deviation is
For a real-valued function on datasets, the Gaussian mechanism outputs on input : its law is the Gaussian with mean and variance .
A function bounds the per-instance sensitivity of (a real-valued function on nonempty datasets) if
for every , every and every slot with .
These objects describe the scalar releases of PFR: when the score is large on every admitted neighbouring pair, Gaussian noise calibrated to is private on those pairs.
Formalization Note is Mathlib's cdf (gaussianReal 0 1). gaussMech g σ s is gaussianReal (g s) (σ²) (Mathlib takes the variance); a dataset of slots enters as the list of its records. The left side of the sensitivity bound is embedded in ; the bound quantifies over every dataset size , as in Definition D.1.
import Mathlib
import Definitions.Def_PFRelease_Dataset
open MeasureTheory ProbabilityTheory
namespace PFRelease.Supplement
/-- The standard Gaussian CDF `Φ(x) = Pr[N(0, 1) ≤ x]` (Shenfeld, Tsfadia, Ligett, *Propose-Filter-Release:
Scaling Noise to Typical Sensitivity via Private Filtering*, arXiv:2610.40654, held version sha256 e1d516b3…,
§2, p.7 = PDF p.9, and Fact A.2, p.27).
**Formalization Note** `Φ` is Mathlib's `cdf` of the standard real Gaussian `gaussianReal 0 1`. -/
noncomputable def stdNormalCDF (x : ℝ) : ℝ := cdf (gaussianReal 0 1) x
/-- The privacy profile of the Gaussian mechanism (§2, p.7 = PDF p.9; Fact A.2, p.27):
`δ_{N_σ}(ε) := Φ(1/(2σ) − εσ) − e^ε Φ(−1/(2σ) − εσ)`. -/
noncomputable def gaussProfile (σ ε : ℝ) : ℝ :=
stdNormalCDF (1 / (2 * σ) - ε * σ) - Real.exp ε * stdNormalCDF (-1 / (2 * σ) - ε * σ)
/-- The Gaussian noise-addition mechanism `N_σ(g)` (§2, p.7 = PDF p.9; Fact A.2, p.27): on a dataset `s`
of `n` records it outputs `g(s) + N(0, σ²)`, i.e. its law is the Gaussian with mean `g(s)` and
variance `σ²`.
**Formalization Note** `g` is a real-valued function on datasets in `X* = List (Option X)`; a dataset
of `n` slots enters through `toList`. Mathlib's `gaussianReal μ v` takes the variance `v ∈ ℝ≥0`,
here `σ²`, so `σ` is the standard deviation (for `σ = 0` the law is the point mass at `g(s)`). -/
noncomputable def gaussMech {X : Type*} {n : ℕ} (g : List (Option X) → ℝ) (σ : ℝ)
(s : Fin n → Option X) : Measure ℝ :=
gaussianReal (g (toList s)) (Real.toNNReal (σ ^ 2))
/-- A function `Δ : X* × X → [0, ∞]` bounds the per-instance sensitivity of a real-valued function
`g` on nonempty datasets (Definition D.1, p.39 = PDF p.41) if `|g(s) − g(s^{i→⊥})| ≤ Δ(s^{i→⊥}, sᵢ)`
for every `n ≥ 1`, every `s ∈ Xⁿ` and every slot `i` with `sᵢ ≠ ⊥`.
**Formalization Note** The quantifier over `n ≥ 1` is explicit (it ranges over every dataset size,
not only the size of a later theorem). The left side is embedded in `[0, ∞]` by `ENNReal.ofReal`.
`g` is total on `List (Option X)`; its value on the empty list is never used. -/
def IsPerInstanceBound {X : Type*} (g : List (Option X) → ℝ)
(Δ : List (Option X) → Option X → ENNReal) : Prop :=
∀ (m : ℕ), 1 ≤ m → ∀ (s : Fin m → Option X) (i : Fin m), s i ≠ none →
ENNReal.ofReal |g (toList s) - g (toList (nullOut s {i}))| ≤
Δ (toList (nullOut s {i})) (s i)
end PFRelease.Supplement