Paper 2026/1273

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

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.