Theorem 5.1 — Sampling a common shell with an exact conditional law
OpenZLIPPadding.Padding.Supplement.common_shell_samplingLet the independent increments have a common nonzero, automorphism-invariant lattice law with norm at most . Supply positive integers with and a valid . Write for the hidden-coordinate endpoint law and . Assume the explicit finite estimate: for every there is such that with for every standard-shell vector . For and , put
The specified bucket algorithm uses exactly increment calls. It returns failure or a label and vectors on , and returns a heavy label with probability at least . Conditional on every returned label of positive probability, its vectors have exactly the product law , where is automorphism invariant. For every heavy and every ,
Time is polynomial in , input length, oracle time and output length. No local central limit theorem or unconditional guarantee for arbitrary approximate-SVP oracles is assumed. This companion theorem is separate from the padding proof.
Differences from the source:
- encoding: the real failure budget beta and total running time including the oracle → the derived integer T is supplied as a finite budget; kernel execution counts KT requests and charges any per-call time bound; reason: no real number or proof witness is an executable input; T is exactly (5.4) and oracle costs are included
import Definitions.Def_ZLIPPadding_Padding_Supplement_Walk
namespace ZLIPPadding.Padding.Supplement
open scoped BigOperators ENNReal
theorem common_shell_sampling :
∃ (P : Program) (c d : ℕ), 0 < c ∧
∀ (n K M N : ℕ) (B : QMat n) O U (π ν : PMF (ZVec n))
(gamma Delta beta : ℝ) (R : ℕ),
0 < n → 0 < K → 0 < M → 1 ≤ N → CoordLaw B O U π ν →
SignedInvariant π →
(∀ z, π z ≠ 0 → z ≠ 0 ∧ normSq z ≤ gamma^2) →
0 ≤ gamma → (K : ℝ)*gamma^2 ≤ M/4 → LocalEstimate π K M Delta →
0 < beta → beta < 1/4 →
(∀ z, ν z ≠ 0 → (encVec z).length ≤ R) →
let T := walkTrials M N beta
let law := bucketLaw (basisGram B) ν K M N T
let runs := walkRun P c d B ν K M N T (errorBits beta) R
(∀ s, runs s ≠ 0 →
Budget (powerBound c d (K+M+N+errorBits beta+(encBasis B).length+R)) s ∧
s.queries.length = K*T ∧ (∀ w ∈ s.queries, w = encBasis B)) ∧
runs.map (fun s => decodeWalk n s.core.output) = law ∧
(∀ m zs, law (some (m,zs)) ≠ 0 →
1 ≤ m ∧ m ≤ M ∧ zs.length = N ∧
∀ z ∈ zs, qnorm (basisGram B) z = m) ∧
prob law {o | ∃ m zs, o = some (m,zs) ∧ m ∈ heavy π K M} ≥ 1-beta ∧
(∀ m, mass law {o | ∃ zs, o = some (m,zs)} ≠ 0 →
let cond := conditionalShell ν (basisGram B) K m
ShellLaw m (cond.map U.mulVec) ∧ SignedInvariant (cond.map U.mulVec) ∧
∀ zs, law (some (m,zs)) =
mass law {o | ∃ xs, o = some (m,xs)} * iid cond N zs) ∧
(∀ m ∈ heavy π K M, ∀ z ∈ shell n m,
let cond := conditionalShell π (1 : ZMat n) K m
Real.exp (-2*Delta)/(shell n m).card ≤ (cond z).toReal ∧
(cond z).toReal ≤ Real.exp (2*Delta)/(shell n m).card) ∧
(∀ tau : ℕ, ∀ s, runs s ≠ 0 →
s.core.bitCost + s.core.randomBits + s.core.peakCells + s.queries.length*tau ≤
powerBound c d (K+M+N+errorBits beta+(encBasis B).length+R+tau)) := by sorry
end ZLIPPadding.Padding.Supplement