Claim 7.4.2 — the majority query is uniform on , also conditional on ok; the fail branch has probability at most
OpenITPIRPreproc.MatchVec.Supplement.claim_7_4_2cryptographymajority-constructionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrieval
Let with . Fix an integer , with . Fix a seed, and for a target sample
Then:
- is uniform on , the branch included: for every key ;
- conditional on , is also uniform on : for every ;
- there is a single number such that for every target and every key , returns with probability exactly .
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 over is the average over (avgOver). Conditional uniformity is stated in product form. By clause 3, , 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)