Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Claim 7.4.1 — compatibility 1/m1/m1/m and overlap 2/m2/m2/m of the majority keys; the conditional sampler is uniform on Ri\mathcal R_iRi​

Open
ITPIRPreproc.MatchVec.Supplement.claim_7_4_1

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

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

Let m=2hm=2^hm=2h with h≥3h\ge3h≥3. Fix an integer H≥h+64H\ge h+64H≥h+64, with d=2H14+1d=2H^{14}+1d=2H14+1 and μ=H−6\mu=H^{-6}μ=H−6. Consider the key space R={−1,+1}h×d\mathcal R=\{-1,+1\}^{h\times d}R={−1,+1}h×d with S(R)={(a,sgn⁡(Rva)):a∈[m]}S(R)=\{(a,\operatorname{sgn}(Rv_a)):a\in[m]\}S(R)={(a,sgn(Rva​)):a∈[m]}, where the vav_ava​ are the row vectors of a seed, and let Ri={R:i∈S(R)}\mathcal R_i=\{R:i\in S(R)\}Ri​={R:i∈S(R)}. Then:

  1. for every seed and every position i=(a,b)∈[m]×{−1,+1}hi=(a,b)\in[m]\times\{-1,+1\}^hi=(a,b)∈[m]×{−1,+1}h,
Pr⁡R←R[i∈S(R)]=1m;\Pr_{R\leftarrow\mathcal R}[i\in S(R)]=\frac1m;R←RPr​[i∈S(R)]=m1​;
  1. for every good seed and every pair of distinct positions i,ji,ji,j,
Pr⁡R←Ri[j∈S(R)]≤2m;\Pr_{R\leftarrow\mathcal R_i}[j\in S(R)]\le\frac2m;R←Ri​Pr​[j∈S(R)]≤m2​;
  1. for every seed and position i=(a⋆,b⋆)i=(a^\star,b^\star)i=(a⋆,b⋆), the conditional sampler returns a uniform key from Ri\mathcal R_iRi​. The sampler negates each uniform block rtr_trt​ whose majority sign sgn⁡⟨rt,va⋆⟩\operatorname{sgn}\langle r_t,v_{a^\star}\ranglesgn⟨rt​,va⋆​⟩ differs from bt⋆b^\star_tbt⋆​.

This is property (i) of Definition 4.1 for the majority primitive, together with the exact conditional sampler used by the compiler.

Formalization Note Pr⁡R←R\Pr_{R\leftarrow\mathcal R}PrR←R​ is ∣Ri∣/∣R∣|\mathcal R_i|/|\mathcal R|∣Ri​∣/∣R∣. Pr⁡R←Ri\Pr_{R\leftarrow\mathcal R_i}PrR←Ri​​ is the average over Ri\mathcal R_iRi​ (avgOver). The sampler statement says that the image of the uniform law on R\mathcal RR under the sampler is the uniform law on Ri\mathcal R_iRi​.

Differences from the source:

  • encoding: probabilities over R ← R and R ← R_i; the sampler returns a uniform key from R_i → normalized counts (#R)⁻¹·#R_i and averages over R_i; the image of the uniform law on R under the sampler equals the uniform law on R_i; reason: uniform laws on finite sets; same probabilities
Preamble
import Mathlib
import Definitions.Def_ITPIRPreproc_MatchVec_Supplement_Majority

open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec.Supplement

/-- Claim 7.4.1, printed p.28 (PDF p.30). Under the §7.2 parameters (`m = 2^h`, `h ≥ 3`, integer
`H ≥ h + 64`, `d = 2H^14 + 1`, `µ = H^{−6}`), with key space `R = {−1,+1}^{h×d}` and
`S(R) = {(a, sgn(R v_a))}`:
(1) for every seed and every position `i`, `Pr_{R←R}[i ∈ S(R)] = 1/m`;
(2) for every good seed and distinct positions `i, j`, `Pr_{R←R_i}[j ∈ S(R)] ≤ 2/m`;
(3) for every seed and position `i`, the conditional sampler maps the uniform law on `R` to the
uniform law on `R_i`. -/
theorem claim_7_4_1 (h H : ℕ) (hh : 3 ≤ h) (hH : h + 64 ≤ H) :
    (∀ (σ : Seed h H) (i : MPos h),
      (Fintype.card (Key h H) : ℝ≥0∞)⁻¹ * (majCompat σ i).card = ((2 : ℝ≥0∞) ^ h)⁻¹) ∧
    (∀ σ : Seed h H, IsGood σ → ∀ i j : MPos h, i ≠ j →
      avgOver (majCompat σ i) (fun R => if majSel σ R j then 1 else 0) ≤ 2 / (2 : ℝ≥0∞) ^ h) ∧
    (∀ (σ : Seed h H) (i : MPos h) (R : Key h H),
      (Fintype.card (Key h H) : ℝ≥0∞)⁻¹ *
          (Finset.univ.filter fun R₀ => majSampler σ i R₀ = R).card =
        if majSel σ R i then ((majCompat σ i).card : ℝ≥0∞)⁻¹ else 0) := 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), Claim 7.4.1, printed p.28 (PDF p.30); objects Eq. (22) and Key sampling, printed p.26 (PDF p.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