All proofs
Project-declaredLean 4.31.0 · mathlib@fabf563a7c95

Build Witness mem rel In

ArkLib.Lattices.Ajtai.InnerOuter.buildWitness_mem_relIn

Plain-language statement

The witness assembler is correct , the hmk input to the generic assembly coordinateWiseSpecialSound_of_mkWitness (SingleRound.lean), and the mathematical content of Hachi Lemma 8's three-case split: at every star-shaped family of relOut-accepting branches, buildWitness lands in relIn.

Exact Lean statement

theorem buildWitness_mem_relIn (hq5 : q % 8 = 5) {b ω γ : ℕ} (hκ : (2 * ω) ^ 2 < q)
    (hτ : 0 < zDigits)
    (stmt : QuadEvalStatement 𝓜(q, α) innerRows (2 ^ m) messageDigits outerRows (2 ^ r) innerDigits
      dRows)
    (v : CarrierCom 𝓜(q, α) dRows)
    (fam : Fin (2 ^ r + 1) → (Fin (2 ^ r) → ShortChallenge 𝓜(q, α) ω))
    (resp : Fin (2 ^ r + 1) →
      QuadEvalResponse 𝓜(q, α) innerRows (2 ^ m) messageDigits (2 ^ r) innerDigits zDigits)
    (hrel : ∀ j, ((stmt, v, fam j), resp j) ∈ relOut 𝓜(q, α) (b : ZMod q) ω γ)
    (hstar : ∃ e, StarAt fam e) :
    (stmt, buildWitness 𝓜(q, α) (b : ZMod q) stmt v fam resp) ∈
      relIn 𝓜(q, α) (b : ZMod q)
        (quadEvalBetaSq γ b zDigits ((𝓜(q, α)).φ.natDegree) m messageDigits) γ (2 * ω)

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem buildWitness_mem_relIn (hq5 : q % 8 = 5) {b ω γ : } (hκ : (2 * ω) ^ 2 < q)    (hτ : 0 < zDigits)    (stmt : QuadEvalStatement 𝓜(q, α) innerRows (2 ^ m) messageDigits outerRows (2 ^ r) innerDigits      dRows)    (v : CarrierCom 𝓜(q, α) dRows)    (fam : Fin (2 ^ r + 1)  (Fin (2 ^ r)  ShortChallenge 𝓜(q, α) ω))    (resp : Fin (2 ^ r + 1)       QuadEvalResponse 𝓜(q, α) innerRows (2 ^ m) messageDigits (2 ^ r) innerDigits zDigits)    (hrel :  j, ((stmt, v, fam j), resp j)  relOut 𝓜(q, α) (b : ZMod q) ω γ)    (hstar :  e, StarAt fam e) :    (stmt, buildWitness 𝓜(q, α) (b : ZMod q) stmt v fam resp)       relIn 𝓜(q, α) (b : ZMod q)        (quadEvalBetaSq γ b zDigits ((𝓜(q, α)).φ.natDegree) m messageDigits) γ (2 * ω) := by  unfold buildWitness  by_cases hB :  j, PolyVec.flattenBlocks (resp j).innerDec       PolyVec.flattenBlocks (resp (central fam)).innerDec  · -- Case (A): some branch's inner decomposition differs → `B`-kernel MSIS solution    -- (both branches' c2 commit to the shared `stmt.u`).    rw [dif_pos hB]    obtain ⟨-, hu₁, -, -, -, -, hγ₁, -⟩ := hrel hB.choose    obtain ⟨-, hu₂, -, -, -, -, hγ₂, -⟩ := hrel (central fam)    exact msis_of_commit_eq 𝓜(q, α) stmt.pp.outerMatrix hu₁ hu₂ hγ₁ hγ₂ hB.choose_spec  · by_cases hD :  j, (resp j).carrierDec  (resp (central fam)).carrierDec    · -- Case (B): shared `t̂` but some carrier decomposition differs → `D`-kernel MSIS solution      -- (the shared round-0 message `v` is what makes both branches commit to the same `v`).      rw [dif_neg hB, dif_pos hD]      obtain hv₁, -, -, -, -, hγ₁, -, -⟩ := hrel hD.choose      obtain hv₂, -, -, -, -, hγ₂, -, -⟩ := hrel (central fam)      exact msis_of_commit_eq 𝓜(q, α) stmt.pp.dMatrix hv₁ hv₂ hγ₁ hγ₂ hD.choose_spec    · -- Case (C): shared `t̂` and `ŵ` → the subtract-and-divide weak opening.      rw [dif_neg hB, dif_neg hD]      push Not at hB hD      have ht :  j, (resp j).innerDec = (resp (central fam)).innerDec :=        fun j => funext fun i => PolyVec.block_eq_of_flattenBlocks_eq (hB j) i      exact verifiedOpening_of_star hq5 hκ hτ stmt v fam resp hrel hstar ht hD,        evalConsistency_of_relOut_star hq5 hκ stmt v fam resp hrel hstar hD
Project
ArkLib
License
Apache-2.0
Commit
fad5cbf80877
Source
ArkLib/Commitments/Functional/Hachi/QuadEval/Soundness.lean:386-421

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.31.0

Affine gaps lifted to interleaved codes

affine_gaps_lifted_to_interleaved_codes

Project documentation

This lemma proves the final algebraic step in the DG25 Theorem 3.1 proof. It shows that if R > e + 1, then e * (R / (R - 1)) < e + 1. The intuition is that the fraction R / (R - 1) is always greater than 1, but as R gets larger, it gets closer to 1. The hypothesis R > e + 1 provides a strong enough bound to ensure the product e * (fraction) do...

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose coeff

ArkLib.Lattices.Ajtai.gadgetDecompose_coeff

Plain-language statement

The k-th coefficient (k < deg φ) of a gadget-decomposition block is exactly the corresponding digit of the corresponding input coefficient.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose lawful

ArkLib.Lattices.Ajtai.gadgetDecompose_lawful

Plain-language statement

The base-b gadget decomposition is a lawful gadget decomposition.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record