Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.3 — a uniformly random seed is good except with probability 2m2e−μ2d/2≤2e2hln⁡2−H22m^2e^{-\mu^2d/2}\le 2e^{2h\ln2-H^2}2m2e−μ2d/2≤2e2hln2−H2

Open
ITPIRPreproc.MatchVec.Supplement.lemma_7_3

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographymajority-constructionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrievalprobability

Let m=2hm=2^hm=2h with h≥3h\ge3h≥3. Fix an integer H≥h+64H\ge h+64H≥h+64, and set d=2H14+1d=2H^{14}+1d=2H14+1 and μ=H−6\mu=H^{-6}μ=H−6. A seed σ=((gk,τk))k∈[d]∈(F2h×F2)d\sigma=((g_k,\tau_k))_{k\in[d]}\in(\mathbb F_2^h\times\mathbb F_2)^dσ=((gk​,τk​))k∈[d]​∈(F2h​×F2​)d defines the row vectors va,k=(−1)⟨a,gk⟩2+τkv_{a,k}=(-1)^{\langle a,g_k\rangle_2+\tau_k}va,k​=(−1)⟨a,gk​⟩2​+τk​, a∈[m]a\in[m]a∈[m]. It is good if ∣⟨va,va′⟩∣≤μd|\langle v_a,v_{a'}\rangle|\le\mu d∣⟨va​,va′​⟩∣≤μd for all a≠a′a\ne a'a=a′. For a uniformly random seed (uniform over all 2(h+1)d2^{(h+1)d}2(h+1)d seeds),

Pr⁡[σ is not good]≤2m2exp⁡ ⁣(−μ2d2)≤2exp⁡(2hln⁡2−H2).\Pr[\sigma\text{ is not good}]\le 2m^2\exp\!\Bigl(-\frac{\mu^2d}{2}\Bigr)\le 2\exp\bigl(2h\ln2-H^2\bigr).Pr[σ is not good]≤2m2exp(−2μ2d​)≤2exp(2hln2−H2).

In the proof of Theorem 7.1, this gives the probability 2−λ−12^{-\lambda-1}2−λ−1 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. h≥3h\ge3h≥3 and H≥h+64H\ge h+64H≥h+64 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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me