Paper 2026/1077

Authenticated and Incremental Single-Server Private Information Retrieval

Zengpeng Li, School of Cyber Science and Technology, Shandong University, Qingdao 266237, The State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou 310058

Mei Wang, School of Cyber Science and Technology, Shandong University, Qingdao 266237

Abstract

Authenticated Private Information Retrieval (Authenticated PIR) allows the client to retrieve the desired database entry without revealing any information about the query, while safely aborting if malicious behavior by the server is detected (presented in USENIX '23). However, two key challenges remain: existing single-server authenticated PIR schemes with sublinear online communication have not yet been clearly and fully implemented; incremental updates to the digest introduce unnecessary overhead. In this paper, we implement the previously outlined idea and present two complete and concrete single-server authenticated PIR schemes with $O(\sqrt{N})$ online communication, namely LWE-AuthPIR and DDH-AuthPIR, along with detailed security proofs. Furthermore, we introduce the notion of single-server authenticated and incremental PIR and propose a corresponding concrete construction, LWE-AuthIncPIR. LWE-AuthIncPIR supports immediate updates to individual entries and integrates a communication-efficient row aggregation for periodic update scenarios. When 1\%-8\% of the entries in a 1GB database are modified, LWE-AuthIncPIR reduces offline preprocessing computation by 19-88$\times$ compared to previous incremental update method. In the password breach detection, LWE-AuthIncPIR achieves a 67$\times$ reduction in preprocessing time and a 2.9$\times$ reduction in communication overhead.

@misc{cryptoeprint:2026/1077,
      author = {Pengfei Lu and Zengpeng Li and Mei Wang},
      title = {Authenticated and Incremental Single-Server Private Information Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1077},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1077}
}