PPT forger implementation witness for Theorem 7.2
OpenCritWinSpin.p7b_7_2_forger_implcritwinspintheorem_7_2
Constructs PPT forgers B_ext and B_amp that run Lhat_{T,k} using slotM, call adversary A on the lifted instance, and output the first fresh decoded configuration.
Preamble
import Mathlib import Definitions.Def_IsingLTL_BeliefProp_TVDist import Definitions.Def_CritWinSpin_Lhat import Definitions.Def_CritWinSpin_nuPm open QAlgorithms.Complexity QAlgorithms.LocalHamiltonian QuantumPRC OWFLocalDesc IsingLTL.BeliefProp set_option autoImplicit false
Formal statement
namespace CritWinSpin
/-- Uniform PPT forger simulation for Theorem 7.2: given `liftF`, `slotM`, `k`, `T`, and `A`,
there exist PPT machines `B_ext` and `B_amp` simulating `L̂_{T,k}` with `slotM`, invoking `A` on
the lifted instance, and scanning `X'` for the first configuration whose `Ψ`-message is fresh. -/
theorem p7b_7_2_forger_impl (S : SpinLaw) (p : ℕ)
(F : BilinearFamily) (src : BinarySource F) (C : ℝ) (hsrc : SourceProps F src C)
(Ac Cc : ℕ) (Ccap : ℝ) (hCcap : 0 < Ccap)
(liftF : Str → Str) (hliftF : CookPvsNP.PolyTimeComputable liftF) (slotM : PPT)
(û : (d : ℕ) → (desc : Str) → WatersKey F desc d → ℚ) (d₁ : ℕ)
(hlift : ∀ d ≥ d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
IsUhat S ((thetaQ p Ac Cc (src.n d) : ℚ) : ℝ) (cloudSize p Cc (src.n d)) (û d desc key) ∧
liftF (encInst (src.ham d desc key)) =
tupleCode [encInst (liftInst S p Ac Cc (src.ham d desc key) (û d desc key)),
encRat (û d desc key)])
(k T : ℕ → ℕ) (hk : EffPoly k) (hk₁ : ∀ d, 1 ≤ k d) (hT : EffPoly T)
(hTk : ∀ d, ⌈Ccap * ((k d : ℝ) + 1 + (src.n d : ℝ) ^ 2)⌉₊ ≤ T d)
(A : PPT) :
∃ (B_ext B_amp : PPT),
(∀ d ≥ max 1 d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
∀ Fs : Fin (T d) → BinCfg (src.n d),
(∑ ω : Fin (T d) → Option (Config S (Fin (src.n d) × Fin (cloudSize p Cc (src.n d)))),
(∏ t, slotKernel S p Cc slotM (src.ham d desc key) (û d desc key) (Fs t) (ω t)) *
match lhatRun (k d) ω with
| none => 0
| some R =>
∑ y : Config S (Fin (src.n d) × Fin (cloudSize p Cc (src.n d))),
A.prob (tupleCode [encInst (liftInst S p Ac Cc (src.ham d desc key) (û d desc key)),
encSamples (fun j a => (R j).2 (finProdFinEquiv.symm a))])
(fun s => decConfig S (src.n d * cloudSize p Cc (src.n d)) s =
some (fun a => y (finProdFinEquiv.symm a))) *
(match List.findSome? (fun j =>
match decodeY ((Fin.cons y (fun j' => (R j').2) : Fin (k d + 1) → Config S (Fin (src.n d) × Fin (cloudSize p Cc (src.n d)))) j) with
| some y₀ => if ∃ j' : Fin (k d), decMsg (src.psi d desc key) (R j').2 = some (src.psi d desc key y₀) then none else some y₀
| none => none) (List.finRange (k d + 1)) with
| none => 0
| some y₀ => if y₀ ∈ src.omega d desc key ∧ ∀ t : Fin (T d), src.psi d desc key y₀ ≠ src.psi d desc key (Fs t) then 1 else 0)) ≤
B_ext.prob (tupleCode (pkCode F d desc key :: List.ofFn fun t => List.ofFn (Fs t)))
(fun s => ∃ y : BinCfg (src.n d), s = List.ofFn y ∧ y ∈ src.omega d desc key ∧
∀ t, src.psi d desc key y ≠ src.psi d desc key (Fs t))) ∧
(∀ d ≥ max 1 d₁, ∀ desc, GenSupport F.gen d desc → ∀ key : WatersKey F desc d,
∀ Fs : Fin (T d) → BinCfg (src.n d),
(∑ ω : Fin (T d) → Option (Config S (Fin (src.n d) × Fin (cloudSize p Cc (src.n d)))),
(∏ t, slotKernel S p Cc slotM (src.ham d desc key) (û d desc key) (Fs t) (ω t)) *
match lhatRun (k d) ω with
| none => 0
| some R =>
∑ X' : Fin (k d + 1) → Config S (Fin (src.n d) × Fin (cloudSize p Cc (src.n d))),
A.prob (tupleCode [encInst (liftInst S p Ac Cc (src.ham d desc key) (û d desc key)),
encSamples (fun j a => (R j).2 (finProdFinEquiv.symm a))])
(fun s => decTuple S (src.n d * cloudSize p Cc (src.n d)) (k d + 1) s =
some (fun j a => X' j (finProdFinEquiv.symm a))) *
(match List.findSome? (fun j =>
match decodeY (X' j) with
| some y₀ => if ∃ j' : Fin (k d), decMsg (src.psi d desc key) (R j').2 = some (src.psi d desc key y₀) then none else some y₀
| none => none) (List.finRange (k d + 1)) with
| none => 0
| some y₀ => if y₀ ∈ src.omega d desc key ∧ ∀ t : Fin (T d), src.psi d desc key y₀ ≠ src.psi d desc key (Fs t) then 1 else 0)) ≤
B_amp.prob (tupleCode (pkCode F d desc key :: List.ofFn fun t => List.ofFn (Fs t)))
(fun s => ∃ y : BinCfg (src.n d), s = List.ofFn y ∧ y ∈ src.omega d desc key ∧
∀ t, src.psi d desc key y ≠ src.psi d desc key (Fs t))) := by sorry
end CritWinSpinSource
CritWinSpin Theorem 7.2 decomposition