Trapdoored matrices with exact fast forward action
DefinitionZamirInversion581_Mult_Supplement_TrapdoorFix a finite field . A trapdoor object consists of a sampler program and a forward-action program in the same field RAM. It satisfies the trapdoor assumption when there are and such that, on dimension , every sampler run outputs a dense matrix and a finite trapdoor block within operations. On every supported pair and every vector , every action run outputs exactly within operations. The action input is , the trapdoor, and the vector; it is not given the dense matrix.
For every nonuniform probabilistic polynomial-time bit distinguisher family , there is a negligible function such that
where is uniform on all matrices and the distinguisher sees only . Negligibility uses the published condition for every natural .
This records precisely the assumed capabilities from §3.1. Determinant computation, transpose action, inversion, and multi-sample security are consequences to be proved, not fields of the assumption. Dense matrices and vectors use row-major and coordinate-order block encodings. The shifts by two in the runtime bounds handle small dimensions without changing the asymptotic requirement.
import Mathlib
import Definitions.Def_ZamirInversion581_Mult_Supplement_FieldRAM
import Definitions.Def_ZamirInversion581_Mult_Supplement_Statistics
import Definitions.Def_MLManagesComplexity_Negligible
set_option autoImplicit false
namespace ZamirInversion581.Mult.Supplement
/-! §3.1, p.11: only fast sampling, exact forward action, and single-sample
nonuniform computational indistinguishability are assumed. No determinant,
transpose, inverse, or multi-sample guarantee is a field of this interface. -/
variable {F : Type*} [Field F] [Fintype F] [DecidableEq F]
/-- Row-major dense encoding. -/
def matrixBlock {n : ℕ} (X : Mat F n) : List F :=
(List.finRange n).flatMap (fun i => (List.finRange n).map (fun j => X i j))
def vectorBlock {n : ℕ} (v : Fin n → F) : List F := (List.finRange n).map v
/-- Decode the already exposed dense block. -/
def blockMatrix (n : ℕ) (xs : List F) : Mat F n :=
fun i j => xs.getD (n * i.val + j.val) 0
/-- Total decoding; the sampler's validity clause excludes the default case. -/
def sampleData (n : ℕ) (σ : Config F) : Mat F n × List F :=
match σ.status with
| .done (some (.blocks xs τ)) => (blockMatrix n xs, τ)
| _ => (0, [])
/-- Source objects are programs, not arbitrary fast maps. -/
structure TrapdoorPrograms (F : Type*) where
sampler : Program F
action : Program F
noncomputable def samplerLaw (𝒯 : TrapdoorPrograms F) (n : ℕ) : PMF (Config F) :=
finalLaw 𝒯.sampler (blockInput [n] [])
/-- Input n, trapdoor length; memory is the trapdoor followed by the vector. -/
def actionInput (n : ℕ) (τ : List F) (v : Fin n → F) : Config F :=
blockInput [n, τ.length] (τ ++ vectorBlock v)
/-- Trapdoored-matrix assumption, with constants belonging to the fixed family.
Every random branch of the sampler returns n² field cells and a finite trapdoor.
Every supported pair has an exact forward action for every vector. -/
def IsTrapdoored (𝒯 : TrapdoorPrograms F) : Prop :=
(∃ (C : ℝ) (b : ℕ), 0 < C ∧ ∀ n,
HaltWithin 𝒯.sampler (blockInput [n] [])
(C * (n + 2 : ℝ) ^ 2 * Real.log (n + 2 : ℝ) ^ b) ∧
∀ σ ∈ (samplerLaw 𝒯 n).support,
(∃ xs τ, σ.status = .done (some (.blocks xs τ)) ∧ xs.length = n * n) ∧
∀ v : Fin n → F,
let Rτ := sampleData n σ
HaltWithin 𝒯.action (actionInput n Rτ.2 v)
(C * (n + 2 : ℝ) * Real.log (n + 2 : ℝ) ^ b) ∧
∀ δ ∈ (finalLaw 𝒯.action (actionInput n Rτ.2 v)).support,
δ.status = .done (some (.block (vectorBlock (Rτ.1.mulVec v))))) ∧
∀ D : ℕ → Program F, NonuniformPPT D →
∃ ν : ℕ → ℝ, MLManagesComplexity.Negligible ν ∧ ∀ n,
|(eventProb ((samplerLaw 𝒯 n).bind (fun σ =>
finalLaw (D n) (matrixInput n [n] (sampleData n σ).1)))
(fun δ => δ.status = .done (some (.index 1)))) -
(unifMean (fun X : Mat F n => accepts (D n) (matrixInput n [n] X)
(fun o => o = .index 1)))| ≤ ν n
end ZamirInversion581.Mult.Supplement