Paper 2025/2074

VIA: Communication-Efficient Single-Server Private Information Retrieval

Xukun Wang, Key Laboratory of Mathematical Sciences AMSS, Chinese Academy of Sciences

Zhifang Zhang, Key Laboratory of Mathematical Sciences AMSS, Chinese Academy of Sciences

Abstract

Private Information Retrieval (PIR) is a crucial component in many privacy-preserving systems, with Offline/Online PIR attracting significant attention. Recent works have focused on eliminating offline communication overhead. However, existing constructions incur high online communication costs as a trade-off. To address this, we propose VIA, a single-server PIR scheme that eliminates offline communication while achieving $O{_\lambda}(\log N)$ online communication complexity. Experimental evaluations demonstrate that for a 32 GB database, VIA requires only 690 KB of online communication---a $3.7\times$ reduction compared to state-of-the-art schemes without offline communication---while attaining a throughput of 3.11 GB/s. Furthermore, we introduce VIA-C, a variant of VIA that allows offline communication. Compared to previous communication-efficient schemes, VIA-C achieves a $24.5\times$ reduction in online communication, requiring only 2.1 KB for a 32 GB database (with 14.8 MB offline communication). Moreover, VIA-C can naturally extend to VIA-B that supports batch queries. Compared to previous communication-efficient batch PIR schemes, VIA-B achieves a $3.5\times$ reduction in query size and a $127\times$ reduction in response size for a 1 GB database of 1-byte records. The designs of our schemes rely on a novel DMux-CMux structure and LWE-to-RLWE conversion techniques.

Note: The URL of the open-source code has been updated.

@misc{cryptoeprint:2025/2074,
      author = {Chenyang Liu and Xukun Wang and Zhifang Zhang},
      title = {{VIA}: Communication-Efficient Single-Server Private Information Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2074},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2074}
}