VIA: Communication-Efficient Single-Server Private Information Retrieval

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-theart schemes without offline communication-while attaining a throughput of $3.11 ~\text{GB} / \mathrm{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 communicationefficient 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.