Appendix A — least word length and prime-power parameters
DefinitionITPIRPreproc_MatchVec_PolynomialParameterscryptographyfinite-differencesmatching-vectors
For a family with rows, define to be the least natural number satisfying , as in Appendix A. Define for . Thus is the least power of strictly exceeding . The family uses exponents and .
The prime-power choice uses the square-root threshold needed by the dimension bound, as noted in the formalization of the original matching-vector milestone. These are mathematical parameter definitions, not RAM programs. The least-word-length definition uses the witness solely to justify existence; it does not claim that this witness is used by an efficient implementation.
Definition code
import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialConstruction
import Mathlib.Data.Nat.Sqrt
import Mathlib.Analysis.SpecialFunctions.Pow.Asymptotics
import Mathlib.Algebra.Order.Floor.Semiring
namespace ITPIRPreproc.MatchVec.PolynomialConstruction
/-- The least word length with enough row words, as in Appendix A. -/
noncomputable def wordLength (h : ℕ) : ℕ := Nat.find (show ∃ ell : ℕ, 2^h ≤ ell^ell from
⟨2^h, le_self_pow (by
have hp : 0 < 2^h := by positivity
omega) (by positivity)⟩)
/-- The least exponent whose prime power exceeds the square root of the word length. -/
def primeExponent (p ell : ℕ) : ℕ := Nat.clog p (Nat.sqrt ell + 1)
/-- The prime-power exponents used for the indexed family at size 2^h. -/
noncomputable def exponent2 (h : ℕ) : ℕ := primeExponent 2 (wordLength h)
noncomputable def exponent3 (h : ℕ) : ℕ := primeExponent 3 (wordLength h)
end ITPIRPreproc.MatchVec.PolynomialConstruction
Source
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