Claim 5.2.1 — compatibility and overlap of the basic matching-vector keys; the sampler (9) is uniform on
ProvedITPIRPreproc.MatchVec.claim_5_2_1cryptographymatching-vectorsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrieval
Let with , and let () satisfy (7) with the vectors pairwise distinct. Consider the key space with and . For every pair of distinct positions and in ,
Moreover, if is uniform, the key of (9) is uniform on .
This gives property (i) of Definition 4.1 for the basic construction, and its sampler statement is reused for the matrix part of the activation-bit sampler (15) in Claim 6.2.1.
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)⁻¹·#{…} and averages (#R_i)⁻¹·Σ_{R∈R_i}; the image law of the uniform 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_BasicKeys import Definitions.Def_ITPIRPreproc_MatchVec_OneCompatibleHint open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec
/-- Claim 5.2.1, printed p.18 (PDF p.20). For a matching-vector family (7) with distinct
`v_a mod 2`, `m = 2^h`, the basic key space `R = F₂^{h×d}` and `S(R) = {(a, R v_a)}`: for distinct
positions `i, j`, `Pr_{R←R}[i ∈ S(R)] = 1/m` and `Pr_{R←R_i}[j ∈ S(R)] ≤ 1/m`; the sampler (9)
maps the uniform law on `R` to the uniform law on `R_i`. -/
theorem claim_5_2_1 (h d : ℕ) (u v : Fin (2 ^ h) → Fin d → ZMod 6) (hh : 3 ≤ h)
(hmv : IsMVFamily (2 ^ h) d u v) :
(∀ i j : Pos h, i ≠ j →
(Fintype.card (BasicKey h d) : ℝ≥0∞)⁻¹ * (basicCompat v i).card = (2 ^ h : ℝ≥0∞)⁻¹ ∧
avgOver (basicCompat v i) (fun R => if basicSel v R j then 1 else 0) ≤
(2 ^ h : ℝ≥0∞)⁻¹) ∧
∀ (i : Pos h) (R : BasicKey h d),
(Fintype.card (BasicKey h d) : ℝ≥0∞)⁻¹ *
(Finset.univ.filter fun R₀ => basicSampler u v i R₀ = R).card =
if basicSel v R i then ((basicCompat v i).card : ℝ≥0∞)⁻¹ else 0 := by sorry
end ITPIRPreproc.MatchVec
Source
Jesko Dujmovic, Zhengnan Lai, Daniel Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572 (October 2026), Claim 5.2.1, printed p.18 (PDF p.20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.