Padding transfer: PIR at power-of-four database lengths implies PIR at every database length
OpenITPIRPreproc.MatchVec.power_four_paddingSuppose one uniform single-server PIR scheme with streaming client preprocessing satisfies the following for every integer and security parameter , at database length : perfect privacy, correctness error at most , preprocessing work , online communication , offline communication , and preprocessing storage, client storage, and client/server work per retrieval bounded by , for constants and .
Then there is one uniform scheme for every database length , a function , and constants with perfect privacy, correctness error at most , and bounds
while preprocessing storage, client storage, and client/server work per retrieval are at most
All bounds are worst-case and include the temporary storage specified by the PIR model. The scheme never receives the number of retrievals as input.
This is the padding step used after the power-of-two matrix construction in the proof of Theorem 6.1. It isolates the passage from matrix-sized databases to arbitrary lengths, including implementation overhead and adaptive privacy/correctness.
Formalization Note The hypothesis packages the scheme and all its constants existentially. The conclusion is the resource specification of Theorem 6.1. This is a generalization of the paper's padding step to any uniform scheme satisfying the displayed power-of-four bounds; it does not assume the matching-vector construction or compiler.
import Mathlib.Analysis.SpecialFunctions.Pow.Asymptotics import Definitions.Def_ITPIRPreproc_MatchVec_Model open scoped ENNReal open Filter Topology
namespace ITPIRPreproc.MatchVec
theorem power_four_padding
(hSquare :
∃ S : Scheme, S.WellFormed ∧
∃ η : ℕ → ℝ, Tendsto η atTop (𝓝 0) ∧
∃ (K : ℝ) (c : ℕ), ∀ h lam : ℕ, 3 ≤ h → 1 ≤ lam →
PerfectlyPrivate S (4^h) lam ∧
Correct S (4^h) lam (fun T => (T : ℝ≥0∞) * (2⁻¹ : ℝ≥0∞)^lam) ∧
MeetsBudget S (4^h) lam
{ preWork := K * ((4^h : ℕ) : ℝ)^(1+η h) * (lam:ℝ)^c
preSpace := K * ((4^h : ℕ) : ℝ)^((1:ℝ)/2+η h) * (lam:ℝ)^c
online := K * lam * ((4^h : ℕ) : ℝ)^(η h)
offline := K * Real.sqrt (4^h : ℕ)
clientWork := K * ((4^h : ℕ) : ℝ)^((1:ℝ)/2+η h) * (lam:ℝ)^c
clientSpace := K * ((4^h : ℕ) : ℝ)^((1:ℝ)/2+η h) * (lam:ℝ)^c
serverWork := K * ((4^h : ℕ) : ℝ)^((1:ℝ)/2+η h) * (lam:ℝ)^c }) :
∃ S : Scheme, S.WellFormed ∧
∃ ε : ℕ → ℝ, Tendsto ε atTop (𝓝 0) ∧
∃ (C : ℝ) (c : ℕ), ∀ n lam : ℕ, 1 ≤ n → 1 ≤ lam →
PerfectlyPrivate S n lam ∧
Correct S n lam (fun T => (T : ℝ≥0∞) * (2⁻¹ : ℝ≥0∞) ^ lam) ∧
MeetsBudget S n lam
{ preWork := C * (n : ℝ) ^ (1 + ε n) * (lam : ℝ) ^ c
preSpace := C * (n : ℝ) ^ ((1 : ℝ) / 2 + ε n) * (lam : ℝ) ^ c
online := C * lam * (n : ℝ) ^ (ε n)
offline := C * Real.sqrt n
clientWork := C * (n : ℝ) ^ ((1 : ℝ) / 2 + ε n) * (lam : ℝ) ^ c
clientSpace := C * (n : ℝ) ^ ((1 : ℝ) / 2 + ε n) * (lam : ℝ) ^ c
serverWork := C * (n : ℝ) ^ ((1 : ℝ) / 2 + ε n) * (lam : ℝ) ^ c } := by sorry
end ITPIRPreproc.MatchVec