Claim 6.2.3 — the activation-bit decoder never errs and recovers with probability
ProvedITPIRPreproc.MatchVec.claim_6_2_3cryptographymatching-vectorsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrieval
Let with , and let satisfy (7) with the vectors pairwise distinct. For every database and target , sample
and set and . Then
This is property (iii) of Definition 4.1 for the activation-bit primitive, with recovery probability exactly one half.
Formalization Note The decoder's value lies in ; the bit is compared through its embedding .
Differences from the source:
- encoding: Pr over (R, ρ) ← R⁺_i and the coins of Query → average over R⁺_i of the probability under the uniform coins (γ, δ); reason: uniform laws on finite sets; same probabilities
- encoding: Decode(…) ∈ {D[a⋆, b⋆], ⊥} with D[a⋆, b⋆] a bit and Decode a value of F₃ → Option (ZMod 3), compared with the image 0/1 ∈ F₃ of the bit D a⋆ (colIdx b⋆); reason: the paper's decoder returns an element of F₃ or ⊥; same statement
Preamble
import Mathlib import Definitions.Def_ITPIRPreproc_MatchVec_ActivationPrimitive open scoped ENNReal
Formal statement
namespace ITPIRPreproc.MatchVec
/-- Claim 6.2.3, printed p.23 (PDF p.25). For every 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)`: the decoder's output lies in `{D[a⋆, b⋆], ⊥}` with probability `1` and equals
`D[a⋆, b⋆]` with probability exactly `1/2`. -/
theorem claim_6_2_3 (h d : ℕ) (u v : Fin (2 ^ h) → Fin d → ZMod 6) (hh : 3 ≤ h)
(hmv : IsMVFamily (2 ^ h) d u v) :
∀ (D : DB h) (i : Pos h),
avgOver (actCompat v i) (fun K => (actQuery u i K).toOuterMeasure
{p | actDecode u i K (actHint v D K) p.1 p.2 (actAnswer v D p.1) =
some (bitF3 (D i.1 (colIdx i.2))) ∨
actDecode u i K (actHint v D K) p.1 p.2 (actAnswer v D p.1) = none}) = 1 ∧
avgOver (actCompat v i) (fun K => (actQuery u i K).toOuterMeasure
{p | actDecode u i K (actHint v D K) p.1 p.2 (actAnswer v D p.1) =
some (bitF3 (D i.1 (colIdx i.2)))}) = 2⁻¹ := 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.3, printed p.23 (PDF p.25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.