Claim 7.4.3 — the majority decoder never errs, and for a good seed recovers with probability at least
OpenITPIRPreproc.MatchVec.Supplement.claim_7_4_3cryptographymajority-constructionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrieval
Let with . Fix an integer , with , and . Fix a seed, a database and a target . Sample
and set and . Then:
- soundness: ;
- availability: if the seed is good,
This is property (iii) of Definition 4.1 for the majority primitive, with recovery probability in place of . The correctness of Theorem 7.1 rests on it.
Formalization Note The probabilities average over the law of under Query. is none. The answer is none (abort) or the list in the enumeration order of . Soundness is stated for every seed, and availability for every good seed.
Differences from the source:
- encoding: probabilities over R ← R_i and (Q, u) ← Query(i, R); ⊥; ans = abort or (ok, β) → the average over R_i of the Query law; none; Option (List Bool) with β in the enumeration order of S⁺(Q) (rows in order; within a row, column labels lexicographically with coordinate 0 first and −1 before +1); reason: uniform law on a finite set; Answer and Decode use the same enumeration, so the claim's events are the same for any fixed order
Preamble
import Mathlib import Definitions.Def_ITPIRPreproc_MatchVec_Supplement_Majority open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec.Supplement
/-- Claim 7.4.3, printed p.29 (PDF p.31). Under the §7.2 parameters, for every seed `σ`, database
`D ∈ {0,1}^{m×m}` and target `i = (a⋆, b⋆)`, with `R ← R_i`, `(Q, u) ← Query(i, R)`,
`z = Hint(D, R)` and `ans = Answer(D, Q)`:
`Pr[Decode(i, R, z, Q, u, ans) ∈ {D[a⋆, b⋆], ⊥}] = 1`; and if the seed is good,
`Pr[Decode(i, R, z, Q, u, ans) = D[a⋆, b⋆]] ≥ 5/8`. (`⊥` is `none`.) -/
theorem claim_7_4_3 (h H : ℕ) (hh : 3 ≤ h) (hH : h + 64 ≤ H) (σ : Seed h H) (D : MDB h)
(i : MPos h) :
avgOver (majCompat σ i) (fun R => (majQuery σ i R).toOuterMeasure
{p | majOutcome σ D i R p = some (D i.1 i.2) ∨ majOutcome σ D i R p = none}) = 1 ∧
(IsGood σ →
5 / 8 ≤ avgOver (majCompat σ i) (fun R => (majQuery σ i R).toOuterMeasure
{p | majOutcome σ D i R p = some (D i.1 i.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), Claim 7.4.3, printed p.29 (PDF p.31); Retrieval algorithms and Eq. (23)–(24), printed pp.26–27 (PDF pp.28–29)