Claim 6.2.2 — the activation-bit query is uniform on
ProvedITPIRPreproc.MatchVec.claim_6_2_2cryptographymatching-vectorsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrieval
Let with , and let satisfy (7) with the vectors pairwise distinct. For every target , if is uniform and , that is, for independent uniform , , then
This is property (ii) of Definition 4.1 for the activation-bit primitive: the query the server sees carries no information about the target.
Differences from the source:
- encoding: (R, ρ) ← R⁺_i, (Q, u) ← Query(i, (R, ρ)) ⟹ Q ≡ Unif(R⁺) → for every Q₀, the average over R⁺_i of Pr[Q = Q₀] equals 1/|R⁺|; reason: the law of Q under the uniform key of R⁺_i, pointwise on a finite set; same statement
Preamble
import Mathlib import Definitions.Def_ITPIRPreproc_MatchVec_ActivationPrimitive open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec
/-- Claim 6.2.2, printed p.22 (PDF p.24). For every target `i = (a⋆, b⋆)`, if `(R, ρ) ← R⁺_i`
and `(Q, u) ← Query(i, (R, ρ))`, the query `Q = (Q, ρ̃)` is uniform on `R⁺`. -/
theorem claim_6_2_2 (h d : ℕ) (u v : Fin (2 ^ h) → Fin d → ZMod 6) (hh : 3 ≤ h)
(hmv : IsMVFamily (2 ^ h) d u v) :
∀ (i : Pos h) (Q₀ : ActKey h d),
avgOver (actCompat v i) (fun K => (actQuery u i K).toOuterMeasure {p | p.1 = Q₀}) =
(Fintype.card (ActKey h d) : ℝ≥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.2, printed p.22 (PDF p.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.