Enhancing TreePIR for a Single-Server Setting via Resampling

Private Information Retrieval (PIR) allows a client to retrieve an entry $\text{DB}[i]$ from a public database $\text{DB}$ held by one or more servers, without revealing the queried index $i$. Traditional PIR schemes achieve sublinear server computation only under strong assumptions, such as the presence of multiple non-colluding servers or the use of public-key cryptography. To overcome these limitations, $\mathit{\text{preprocessing}}\mathit{\text{PIR}}$ schemes introduce a query-independent offline phase where the client collects $\mathit{\text{hints}}$ that enable efficient private queries during the online phase. In this work, we focus on preprocessing PIR schemes relying solely on $\mathit{\text{One-Way}}\mathit{\text{Functions}}$ (OWFs), which provide minimal cryptographic assumptions and practical implementability. We study three main constructions – TreePIR, PIANO, and PPPS – that explore different trade-offs between communication, storage, and server trust assumptions. Building upon the mechanisms introduced in PIANO and PPPS, we propose an adaptation of TreePIR to the single-server setting by introducing a dual-table hint structure (primary and backup tables) and a $\mathit{\text{resampling}}$ technique to refresh hints efficiently. Our proposed scheme achieves logarithmic upload bandwidth and $O(\sqrt{n}\log n)$ download complexity while requiring $O(\sqrt{n}\log n)$ client storage. This represents a significant improvement over prior single-server preprocessing PIR schemes such as PIANO ($O(\sqrt{n})$ bandwidth) and PPPS ($O(n^{1\mathrm{/}4})$ bandwidth), while maintaining the simplicity and minimal assumptions of the OWF-based setting.