{"ID":2859915,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.04882","arxiv_id":"2510.04882","title":"Enhancing TreePIR for a Single-Server Setting via Resampling","abstract":"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, \\textit{preprocessing PIR} schemes introduce a query-independent offline phase where the client collects \\textit{hints} that enable efficient private queries during the online phase. In this work, we focus on preprocessing PIR schemes relying solely on \\textit{One-Way 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 \\textit{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/4})$ bandwidth), while maintaining the simplicity and minimal assumptions of the OWF-based setting.","short_abstract":"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 no...","url_abs":"https://arxiv.org/abs/2510.04882","url_pdf":"https://arxiv.org/pdf/2510.04882v1","authors":"[\"Elian Morel\"]","published":"2025-10-06T15:03:05Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false}