Paper 2026/1273

Achieving Tight Space-Time Tradeoff and Practical Performance in Preprocessing PIR with Multi-level Recursion

Bo Peng, Peking University

Zhechen Li, Ant Group

Cheng Hong, Ant Group

Mingxun Zhou, Hong Kong University of Science and Technology

Abstract

Client-specific preprocessing PIR supports sublinear online private queries after a linear-time offline phase that prepares client-specific hints. The relevant lower bound is tight: any scheme with $S$ bits of client storage and online cost $T$ must satisfy $S \cdot T = \Omega(n)$. Most practical random-set schemes fall short by a $\kappa$ factor in client storage, while the known constant-factor-optimal schemes, WR-PIR (Eurocrypt 2025) and Balanced PIR (S&P 2026), rely on complex hint-management machinery and incur high concrete costs. We present Multi-level PIR, a preprocessing PIR scheme that matches this tight space-time tradeoff using only simple random-set components. The main idea is a multi-level composition: early levels are allowed to fail with noticeable probability, and later levels are invoked only when these query-independent failures occur. This 'waterfall' structure drives the overall failure probability down to negligible while keeping expected online cost and client storage at $O(\sqrt{n})$. Our implementation shows that this simpler structure gives competitive concrete performance. Compared with Piano and S3PIR, two prior state-of-the-art practical schemes, Multi-level PIR achieves a $9$-$20\times$ client space reduction; compared with Balanced PIR, it reduces preprocessing time by about $8$-$45\times$ and online communication by about $5$-$67\times$ in our evaluated settings, while remaining competitive in other online metrics. As an additional theoretical result, we give a more involved variant with $O(n^{1/4})$ online communication, the first constant-factor-optimal preprocessing PIR scheme with sub-$\sqrt{n}$ online communication.

@misc{cryptoeprint:2026/1273,
      author = {Chang Shi and Bo Peng and Zhechen Li and Cheng Hong and Mingxun Zhou},
      title = {Achieving Tight Space-Time Tradeoff and Practical Performance in Preprocessing {PIR} with Multi-level Recursion},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1273},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1273}
}