Lemma 7.3 — a uniformly random seed is good except with probability
OpenITPIRPreproc.MatchVec.Supplement.lemma_7_3cryptographymajority-constructionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrievalprobability
Let with . Fix an integer , and set and . A seed defines the row vectors , . It is good if for all . For a uniformly random seed (uniform over all seeds),
In the proof of Theorem 7.1, this gives the probability that the seed sampled during preprocessing is bad (Eq. (30)).
Formalization Note The probability is the number of non-good seeds divided by the number of seeds. Both inequalities are stated. and are the standing assumptions of §7.2.
Differences from the source:
- encoding: Pr over a uniformly random seed → the number of non-good seeds divided by the number 2^{(h+1)d} of seeds; rows a identified with their binary labels (bit t of a is coordinate t); reason: uniform law on a finite set; the §5.2 identification of [m] with F_2^h
Preamble
import Mathlib import Definitions.Def_ITPIRPreproc_MatchVec_Supplement_Majority
Formal statement
namespace ITPIRPreproc.MatchVec.Supplement
/-- Lemma 7.3, printed p.26 (PDF p.28). With `m = 2^h`, `h ≥ 3`, an integer `H ≥ h + 64`,
`d = 2H^14 + 1` and `µ = H^{−6}`: a uniformly random seed (uniform over all `2^{(h+1)d}` seeds) is
good except with probability at most `2m² exp(−µ²d/2)`, and `2m² exp(−µ²d/2) ≤ 2 exp(2h ln 2 − H²)`. -/
theorem lemma_7_3 (h H : ℕ) (hh : 3 ≤ h) (hH : h + 64 ≤ H) :
((Finset.univ.filter fun σ : Seed h H => ¬ IsGood σ).card : ℝ) /
(Fintype.card (Seed h H) : ℝ) ≤
2 * ((2 : ℝ) ^ h) ^ 2 * Real.exp (-(mu H ^ 2 * (dim H : ℝ) / 2)) ∧
2 * ((2 : ℝ) ^ h) ^ 2 * Real.exp (-(mu H ^ 2 * (dim H : ℝ) / 2)) ≤
2 * Real.exp (2 * h * Real.log 2 - (H : ℝ) ^ 2) := by sorry
end ITPIRPreproc.MatchVec.Supplement
Source
Jesko Dujmovic, Zhengnan Lai, Daniel Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572 (October 2026), Lemma 7.3, printed p.26 (PDF p.28); parameters Eq. (19), (20), (21), printed pp.24, 26 (PDF pp.26, 28)