2025/10/06 by Elian Morel, Morel, Elian
Computer Science · #Advanced Database Systems and Queries #Cloud Computing and Resource Management #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Service-Oriented Architecture and Web Services
paper · pdf · doi:10.48550/arxiv.2510.04882
openalex publication_date 2025/10/06 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28
Private Information Retrieval (PIR) allows a client to retrieve an entry DB[i] from a public database 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, preprocessing PIR schemes introduce a query-independent offline phase where the client collects hints that enable efficient private queries during the online phase. In this work, we focus on preprocessing PIR schemes relying solely on 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 resampling technique to refresh hints efficiently. Our proposed scheme achieves logarithmic upload bandwidth and O(√(n)log n) download complexity while requiring O(√(n)log n) client storage. This represents a significant improvement over prior single-server preprocessing PIR schemes such as PIANO (O(√(n)) bandwidth) and PPPS (O(n1/4) bandwidth), while maintaining the simplicity and minimal assumptions of the OWF-based setting.