Paper 2024/719

Client-Efficient Online-Offline Private Information Retrieval

Hoang-Dung Nguyen, Virginia Tech
Jorge Guajardo, Robert Bosch LLC – RTC
Thang Hoang, Virginia Tech

Private Information Retrieval (PIR) permits clients to query entries from a public database hosted on untrusted servers in a privacy-preserving manner. Traditional PIR model suffers from high computation and/or bandwidth cost due to entire database processing for privacy. Recently, Online-Offline PIR (OO-PIR) has been suggested to improve the practicality of PIR, where query-independent materials are precomputed beforehand to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&P’24, CRYPTO’23) successfully reduce the online processing overhead to sublinear, they still impose sustainable bandwidth and storage burdens on the client, especially when operating on large databases. In this paper, we propose Pirex, a new OO-PIR scheme with eminent client performance while maintaining the sublinear server processing efficiency. Specifically, Pirex offers clients with sublinear processing, minimal inbound bandwidth, and low storage requirements. Our Pirex design is fairly simple yet efficient, where the majority of operations are 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 experimental results demonstrated that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. Concretely, with a 1 TB database, Pirex only takes 0.8s to query a 256-KB entry, compared with 30-220s by the state-of-the-art.

Note: Minor fixes on typo and math errors

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
nhd @ vt edu
Jorge GuajardoMerchan @ us bosch com
thanghoang @ vt edu
2024-05-18: last of 4 revisions
2024-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hoang-Dung Nguyen and Jorge Guajardo and Thang Hoang},
      title = {Client-Efficient Online-Offline Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2024/719},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.