Proof of Lemma 4.3, p. 11 — for any outcome x, the probability over the test that x ∉ B_test is negligible in m
ProvedCommitOpen.Benign.sampling_negligibleconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-cryptographysampling
Fix and . There is a negligible function such that for every and all strings ,
where , is a uniform subset of size , is a uniform subset of , and .
The relative error rate on a random sample of positions predicts the error rate on the unsampled positions. This is the classical sampling problem the paper invokes with a reference to Hoeffding's inequality; it is the probabilistic core of Lemma 4.3.
Formalization Note. depends only on and ; it is uniform in , and . The paper's is , identical when is an integer. on is .
Preamble
import Mathlib import Definitions.Def_CommitOpen_Benign_Model
Formal statement
namespace CommitOpen.Benign
theorem sampling_negligible (α ε : ℝ) (hα0 : 0 < α) (hα1 : α < 1) (hε : 0 < ε) :
∃ ν : ℕ → ℝ, Negligible ν ∧
∀ (m : ℕ) (x xhat : Fin m → Bool),
∑ t ∈ Finset.univ.filter (fun t : Test m ⌊α * m⌋₊ => x ∉ goodSet ε xhat t),
testProb m ⌊α * m⌋₊ t ≤ ν m := by sorry
end CommitOpen.Benign
Source
Damgård, Fehr, Lunemann, Salvail & Schaffner, Improving the Security of Quantum Protocols via Commit-and-Open, arXiv:0902.3918v4, p. 11, proof of Lemma 4.3 (last sentence), citing [Hoe63]
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.