Appendix A — explicit subpolynomial dimension bound
ProvedITPIRPreproc.MatchVec.polynomial_parameter_boundsasymptoticscryptographymatching-vectors
Let , let be the least natural number satisfying , and let and be the least powers of and strictly exceeding . Put . For any bijective enumeration by of the coordinates in the polynomial construction,
The constant 1000 is a convenient absolute constant, not an optimized value. This makes the asymptotic dimension claim in Appendix A explicit for all . It is a dimension and parameter theorem; it makes no RAM implementation claim.
Preamble
import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialParameters open ITPIRPreproc.MatchVec ITPIRPreproc.MatchVec.PolynomialConstruction
Formal statement
theorem ITPIRPreproc.MatchVec.polynomial_parameter_bounds (h d : ℕ) (hh : 3 ≤ h)
(coords : Fin d ≃ Coordinate (wordLength h) (degree (exponent2 h) (exponent3 h))) :
2^h ≤ (wordLength h)^(wordLength h) ∧
1 ≤ degree (exponent2 h) (exponent3 h) ∧
wordLength h < 2^(exponent2 h) * 3^(exponent3 h) ∧
(d:ℝ) ≤ (2:ℝ)^(1000 * Real.sqrt ((h:ℝ)*Real.log h)) := 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