Client-Efficient Online-Offline Private Information Retrieval
Hoang-Dung Nguyen, Jorge Guajardo, Thang Hoang · Proceedings on Privacy Enhancing Technologies · 2025
Private Information Retrieval (PIR) permits clients to query data entries from a public database hosted on untrusted servers while preserving client privacy. Traditional PIR models suffer from high computation and/or bandwidth overhead due to linear database processing. Recently, Online-Offline PIR (OO-PIR) has been proposed to improve PIR practicality by precomputing query-independent materials to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&P’24, CRYPTO’23) successfully reduce online processing cost to sublinear levels, they still impose substantial bandwidth and storage burdens on the client, especially when operating on large databases. In this paper, we propose Pirex, a new two-server OO-PIR scheme with semi-honest security that offers minimal client-side inbound bandwidth and storage costs while retaining sublinear processing efficiency. The Pirex design is simple, with most operations being naturally low-cost and streamlined (e.g., XOR, PRF, modular arithmetic). We have fully implemented Pirex and evaluated its real-world performance using commodity hardware. Our results show that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. With a 1 TB database, Pirex takes only 55 ms to retrieve a 4 KB entry, compared to 9–30 seconds for state-of-the-art approaches. For practical databases with billions of 4 KB entries, Pirex requires just 16 KB of inbound bandwidth—up to three orders of magnitude more efficient.