Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Padding transfer: PIR at power-of-four database lengths implies PIR at every database length

Open
ITPIRPreproc.MatchVec.power_four_padding

by Jesko · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyp2o-batch-stoc27apaddingprivate-information-retrieval

Suppose one uniform single-server PIR scheme with streaming client preprocessing satisfies the following for every integer h≥3h\ge3h≥3 and security parameter λ≥1\lambda\ge1λ≥1, at database length N=4hN=4^hN=4h: perfect privacy, correctness error at most T2−λT2^{-\lambda}T2−λ, preprocessing work KN1+η(h)λcK N^{1+\eta(h)}\lambda^cKN1+η(h)λc, online communication KλNη(h)K\lambda N^{\eta(h)}KλNη(h), offline communication KNK\sqrt NKN​, and preprocessing storage, client storage, and client/server work per retrieval bounded by KN1/2+η(h)λcK N^{1/2+\eta(h)}\lambda^cKN1/2+η(h)λc, for constants K,cK,cK,c and η(h)→0\eta(h)\to0η(h)→0.

Then there is one uniform scheme for every database length n≥1n\ge1n≥1, a function ε(n)→0\varepsilon(n)\to0ε(n)→0, and constants C,c′C,c'C,c′ with perfect privacy, correctness error at most T2−λT2^{-\lambda}T2−λ, and bounds

preprocessing work≤Cn1+ε(n)λc′,online communication≤Cλnε(n),offline communication≤Cn,\text{preprocessing work}\le C n^{1+\varepsilon(n)}\lambda^{c'},\quad \text{online communication}\le C\lambda n^{\varepsilon(n)},\quad \text{offline communication}\le C\sqrt n,preprocessing work≤Cn1+ε(n)λc′,online communication≤Cλnε(n),offline communication≤Cn​,

while preprocessing storage, client storage, and client/server work per retrieval are at most

Cn1/2+ε(n)λc′.C n^{1/2+\varepsilon(n)}\lambda^{c'}.Cn1/2+ε(n)λc′.

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.

Preamble
import Mathlib.Analysis.SpecialFunctions.Pow.Asymptotics
import Definitions.Def_ITPIRPreproc_MatchVec_Model
open scoped ENNReal
open Filter Topology
Formal statement
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
Source
Dujmovic, Lai, Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/572.pdf, §5.2 printed p.16 (padded matrix layout), proof of Theorem 5.1 printed p.20 (padding changes bounds by a constant factor), proof of Theorem 6.1 printed p.24.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me