Appendix A — correctness, parity separation, and dimension of the polynomial matching vectors
ProvedITPIRPreproc.MatchVec.polynomial_matching_vectorscryptographyfinite-differencesmatching-vectors
Let be natural numbers, put , and suppose and . Choose any distinct words and any enumeration by of all pairs with , , and .
Use the CRT signal and binomial-inversion coefficients from the polynomial-construction definitions, and form
Then these vectors satisfy Equation (7): diagonal inner products are modulo , and each off-diagonal inner product is modulo or modulo . The vectors are pairwise distinct. Moreover,
and, when , . Terms with vanish.
This is the algebraic and combinatorial correctness part of Appendix A. It is valid for any injective indexing of row words and any enumeration of coordinates; it does not assert a uniform RAM implementation or the final subpolynomial bound in terms of .
Preamble
import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialConstruction import Mathlib.Tactic open ITPIRPreproc.MatchVec ITPIRPreproc.MatchVec.PolynomialConstruction open Finset
Formal statement
theorem ITPIRPreproc.MatchVec.polynomial_matching_vectors (ell a b m d : ℕ)
(hk : 1 ≤ degree a b) (hsize : ell < 2^a * 3^b)
(rows : Fin m ↪ (Fin ell → Fin ell))
(coords : Fin d ≃ Coordinate ell (degree a b)) :
IsMVFamily m d
(fun r j => leftVector (coefficient ell a b) (rows r) (coords j))
(fun r j => rightVector (rows r) (coords j)) ∧
d = ∑ t ∈ range (degree a b + 1), ell.choose t * ell^t ∧
(1 ≤ ell → d ≤ (degree a b + 1) * ell^(2 * degree a b)) := by sorrySource
Jesko Dujmovic, Zhengnan Lai, Daniel Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572, Appendix A, printed pp.36-37 (PDF pp.38-39), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/572.pdf