Claim 6.2.1 — compatibility and overlap with activation bits; the sampler (15) is uniform on
ProvedITPIRPreproc.MatchVec.claim_6_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 the keys compatible with . For every pair of distinct positions and in ,
Moreover, if is uniform, the output of the sampler (15) is uniform on .
This is property (i) of Definition 4.1 for the activation-bit primitive: the first inequality of (3) holds with equality, and the overlap probability is below the required .
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_ActivationPrimitive open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec
/-- Claim 6.2.1, printed p.22 (PDF p.24). For a matching-vector family (7) with distinct
`v_a mod 2`, `m = 2^h`, the key space `R⁺ = F₂^{h×d} × F₂^d` and the set (14): for distinct
positions `i, j`, `Pr_{(R,ρ)←R⁺}[i ∈ S(R, ρ)] = 1/(2m)` and `Pr_{(R,ρ)←R⁺_i}[j ∈ S(R, ρ)] ≤ 1/(2m)`;
the sampler (15) maps the uniform law on `R⁺` to the uniform law on `R⁺_i`. -/
theorem claim_6_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 (ActKey h d) : ℝ≥0∞)⁻¹ * (actCompat v i).card = (2 * 2 ^ h : ℝ≥0∞)⁻¹ ∧
avgOver (actCompat v i) (fun K => if actSel v K j then 1 else 0) ≤
(2 * 2 ^ h : ℝ≥0∞)⁻¹) ∧
∀ (i : Pos h) (K : ActKey h d),
(Fintype.card (ActKey h d) : ℝ≥0∞)⁻¹ *
(Finset.univ.filter fun K₀ => actSampler u v i K₀ = K).card =
if actSel v K i then ((actCompat 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 6.2.1, printed p.22 (PDF p.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.