Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Claim 7.4.2 — the majority query is uniform on R\mathcal RR, also conditional on ok; the fail branch has probability at most 1/161/161/16

Open
ITPIRPreproc.MatchVec.Supplement.claim_7_4_2

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. Fix a seed, and for a target i=(a⋆,b⋆)∈[m]×{−1,+1}hi=(a^\star,b^\star)\in[m]\times\{-1,+1\}^hi=(a⋆,b⋆)∈[m]×{−1,+1}h sample

R←Ri,(Q,u)←Query(i,R).R\leftarrow\mathcal R_i,\qquad (Q,u)\leftarrow\mathrm{Query}(i,R).R←Ri​,(Q,u)←Query(i,R).

Then:

  1. QQQ is uniform on R\mathcal RR, the branch u=failu=\mathrm{fail}u=fail included: Pr⁡[Q=Q0]=1/∣R∣\Pr[Q=Q_0]=1/|\mathcal R|Pr[Q=Q0​]=1/∣R∣ for every key Q0Q_0Q0​;
  2. conditional on u=oku=\mathrm{ok}u=ok, QQQ is also uniform on R\mathcal RR: Pr⁡[Q=Q0, u=ok]=Pr⁡[u=ok]/∣R∣\Pr[Q=Q_0,\ u=\mathrm{ok}]=\Pr[u=\mathrm{ok}]/|\mathcal R|Pr[Q=Q0​, u=ok]=Pr[u=ok]/∣R∣ for every Q0Q_0Q0​;
  3. there is a single number p≤1/16p\le 1/16p≤1/16 such that for every target iii and every key R∈RiR\in\mathcal R_iR∈Ri​, Query(i,R)\mathrm{Query}(i,R)Query(i,R) returns u=failu=\mathrm{fail}u=fail with probability exactly ppp.

This is property (ii) of Definition 4.1 for the majority primitive, and the privacy of Theorem 7.1 rests on it.

Formalization Note Uniformity of RRR over Ri\mathcal R_iRi​ is the average over Ri\mathcal R_iRi​ (avgOver). Conditional uniformity is stated in product form. By clause 3, Pr⁡[u=ok]≥15/16>0\Pr[u=\mathrm{ok}]\ge15/16>0Pr[u=ok]≥15/16>0, so the product form is equivalent to the conditional statement. Clause 3 is stated for each fixed key, not on average over keys.

Differences from the source:

  • encoding: Q ≡ Unif(R) when R ← R_i and (Q, u) ← Query(i, R) → the average over R_i of Pr[Q = Q₀] equals 1/#R for every key Q₀; reason: uniform law on a finite set; same law
  • encoding: conditional on u = ok, the query is uniform on R → Pr[Q = Q₀ ∧ u = ok] = Pr[u = ok]·(1/#R) for every Q₀; reason: equivalent to the conditional law being uniform, since Pr[u = ok] ≥ 15/16 > 0 by clause 3
  • encoding: the fail branch has probability at most 1/16, independently of the key and the target → there is one p ≤ 1/16 equal to Pr[u = fail] under Query(i, R) for every target i and every key R ∈ R_i; reason: the literal statement for the fixed seed
Preamble
import Mathlib
import Definitions.Def_ITPIRPreproc_MatchVec_Supplement_Majority

open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec.Supplement

/-- Claim 7.4.2, printed p.28 (PDF p.30). Under the §7.2 parameters, for every seed `σ`:
for every target `i = (a⋆, b⋆)`, with `R ← R_i` and `(Q, u) ← Query(i, R)`,
(1) `Q` is uniform on `R` (the branch `u = fail` included): `Pr[Q = Q₀] = 1/|R|` for every key `Q₀`;
(2) conditional on `u = ok`, `Q` is uniform: `Pr[Q = Q₀ ∧ u = ok] = Pr[u = ok] / |R|`;
(3) there is one number `p ≤ 1/16` such that, for every target `i` and every key `R ∈ R_i`,
`Query(i, R)` returns `u = fail` with probability exactly `p`. (`u = true` is `ok`.) -/
theorem claim_7_4_2 (h H : ℕ) (hh : 3 ≤ h) (hH : h + 64 ≤ H) (σ : Seed h H) :
    (∀ (i : MPos h) (Q₀ : Key h H),
      avgOver (majCompat σ i) (fun R => (majQuery σ i R).toOuterMeasure {p | p.1 = Q₀}) =
        (Fintype.card (Key h H) : ℝ≥0∞)⁻¹) ∧
    (∀ (i : MPos h) (Q₀ : Key h H),
      avgOver (majCompat σ i)
          (fun R => (majQuery σ i R).toOuterMeasure {p | p.1 = Q₀ ∧ p.2 = true}) =
        avgOver (majCompat σ i) (fun R => (majQuery σ i R).toOuterMeasure {p | p.2 = true}) *
          (Fintype.card (Key h H) : ℝ≥0∞)⁻¹) ∧
    (∃ pfail : ℝ≥0∞, pfail ≤ 1 / 16 ∧
      ∀ (i : MPos h) (R : Key h H), R ∈ majCompat σ i →
        (majQuery σ i R).toOuterMeasure {p | p.2 = false} = pfail) := 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.2, printed p.28 (PDF p.30); Query algorithm, printed p.27 (PDF p.29)

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