Information-Theoretic Authenticated PIR: From PIR-RV To APIR

Pengzhen Ke, Yuxuan Qin, Liang Feng Zhang · 2026

Read Information-Theoretic Authenticated PIR: From PIR-RV To APIR by Pengzhen Ke, Yuxuan Qin, Liang Feng Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22505.txt.

Introduction

Ke, Qin, and Zhang tackle private database lookup under hostile servers. Private retrieval hides which entry a client wants, yet a malicious server can still corrupt the answer. Earlier authenticated schemes resist selective-failure tricks but lean on computational hardness. Verified information-theoretic schemes give integrity without such assumptions, yet offer only weak query privacy and no selective-failure defense. The authors define unconditionally secure authenticated retrieval rigorously, place the verified variant beneath it as a relaxed cousin, and prove valid verified schemes upgrade directly with no extra overhead.

Catalog record

CREATORPengzhen Ke, Yuxuan Qin, Liang Feng Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32427
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.22505

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Information-Theoretic Authenticated PIR: From PIR-RV To APIR Thanks: Pengzhen Ke, Yuxuan Qin, and Liang Feng Zhang are with the School of Information Science and Technology, ShanghaiTech University, Shanghai, China. Email: { \{ kepzh, qinyx2022, zhanglf } \} @shanghaitech.edu.cn. These authors contributed equally: Pengzhen Ke, Yuxuan Qin. This work was supported in part by the National Natural Science Foundation of China (No. 62372299). Pengzhen Ke, Yuxuan Qin, Liang Feng Zhang Abstract Private Information Retrieval (PIR) allows clients to retrieve database entries without leaking retrieval indices, yet malicious servers seriously compromise retrieval correctness. Existing Authenticated PIR (APIR) schemes resist selective-failure attacks but rely on computational hardness assumptions. In contrast, information-theoretic PIR with Result Verification (itPIR-RV) achieves integrity without computational assumptions, yet only provides relaxed query privacy with no defense against selective-failure attacks. This paper focuses on unconditionally secure information-theoretic APIR (itAPIR) constructions. We propose the rigorous information-theoretic security definition for itAPIR with statistical privacy against selective-failure attacks and integrity as core properties, formalize the hierarchical relation between itAPIR and itPIR-RV as a relaxed variant with identical integrity but basic query privacy, and prove a conversion theorem that valid itPIR-RV schemes can be directly upgraded to secure itAPIR with no extra overhead. Our work bridges the theoretical gap, simplifies itAPIR design, and enables quantum-resistant PIR in malicious server environments. I Introduction Private Information Retrieval (PIR) [ 6 ] allows a client to retrieve a target database block x_{\alpha}\in{\bf x}=(x_{1},\ldots,x_{n}) while preserving the privacy of the retrieval index \alpha\in[n] from the involved servers. For large-scale databases, a naive PIR scheme incurring O(n) communication complexity is impractical. Thus, multi-server information-theoretic PIR has become a leading research direction [ 3 , 4 , 21 , 12 , 22 , 9 , 8 , 23 , 19 , 20 , 2 , 17 , 26 , 5 , 10 , 14 , 24 , 27 , 7 , 15 , 16 , 11 , 1 , 18 , 25 , 13 ] . In this model, the database is replicated across multiple servers, and the notion of t -privacy ensures that no coalition of up to t servers can infer the client’s retrieval index \alpha . While early PIR protocols typically assume honest-but-curious servers, a critical challenge in practical multi-server PIR deployments lies in addressing malicious servers. Such servers may collude with each other to return incorrect responses (due to active attacks, network anomalies, or outdated data), aiming to deceive the client into reconstructing an erroneous value rather than the target x_{\alpha} . This concern has spurred extensive research on PIR protocols resilient to malicious servers [ 4 , 21 , 12 , 8 , 23 , 20 , 2 , 17 , 26 , 5 , 14 , 24 , 27 , 7 , 15 , 16 , 1 , 13 ] , which are of particular interest in cloud computing scenarios. Among existing solutions for malicious server tolerance, two representative types of verifiable PIR protocols stand out, both equipped with integrity guarantees (i.e., they ensure the client can either recover the correct x_{\alpha} or output \perp to indicate invalid responses): Authenticated PIR (APIR) and PIR with Result Verification (PIR-RV). As a state-of-the-art error-detecting PIR scheme, APIR [ 7 ] achieves subpolynomial communication complexity via Distributed Point Functions (DPFs) and features a strengthened privacy guarantee—resistance against selective-failure attacks . Specifically, APIR’s privacy holds even if colluding malicious servers learn whether the client accepts the result (outputs x_{\alpha} ) or rejects it (outputs \perp ). In contrast, PIR-RV [ 14 , 15 ] , a relaxed variant of APIR, does not require resistance to selective-failure attacks; its privacy guarantee only ensures that colluding servers cannot infer \alpha from query distributions alone, without accounting for the client’s acceptance/rejection outcome. Notably, existing APIR schemes are solely constructed under the computational security model, relying on cryptographic hardness assumptions (e.g., DPF security under computational assumptions). This limits their applicability in high-security scenarios (e.g., secure multi-party computation, quantum-resistant systems) where computational assumptions may be compromised. To address this gap, this work focuses on constructing information-theoretic (it-) APIR schemes—schemes that achieve unconditional security without relying on any computational assumptions. As a core contribution, we further establish a formal connection between itPIR-RV and itAPIR: we prove that an itPIR-RV scheme satisfying specific integrity conditions can be upgraded to an itAPIR scheme, thereby providing a constructive path to realizing information-theoretically secure APIR. I-A Related Works I-A 1 Information-Theoretic PIR Multi-server information-theoretic PIR (itPIR) was first formalized by Chor et al. [ 6 ] , with subsequent works [ 3 , 22 , 9 ] optimizing its communication complexity to sublinear or even polylogarithmic levels. These schemes achieve unconditional t -privacy but assume honest-but-curious servers, lacking resilience to malicious responses. I-A 2 Malicious-Resilient PIR To tolerate malicious servers, verifiable PIR schemes [ 4 , 21 , 12 , 8 , 23 , 20 , 2 , 17 , 26 , 5 , 14 , 24 , 27 , 10 , 7 , 15 , 1 ] introduce integrity guarantees, enabling the client to detect or even correct incorrect responses. Among them, itPIR-RV [ 14 , 10 , 15 ] achieves information-theoretic (v,\epsilon) -integrity (i.e., the probability that the client accepts an incorrect response is at most \epsilon , enven if up to v servers collude maliciously) and only guarantees basic perfect or statistical privacy; APIR [ 7 ] provides strengthened privacy with resistance to selective-failure attacks but relies on computational assumptions, for which no information-theoretic variant has been formally defined. I-A 3 APIR vs. PIR-RV Existing works treat APIR and PIR-RV as independent primitives, but their theoretical connection (especially in the information-theoretic setting) remains unstudied—this gap limits the construction of high-security itAPIR schemes. I-B Our Contributions This work makes four key contributions to information-theoretic malicious-resilient PIR: • We propose information-theoretic Authenticated PIR (itAPIR), requiring statistical t -privacy against selective-failure attacks and (v,\epsilon) -integrity against malicious servers. • We clarify the relation between itAPIR and itPIR-RV, showing that itPIR-RV is a relaxed variant of itAPIR with the same integrity guarantee but without selective-failure-attack resilience. • We prove a conversion theorem: any perfect/statistical t -private itPIR-RV scheme with (v,\epsilon) -integrity, where v\geq t and \epsilon is negligible, can be transformed into a statistically t -private itAPIR scheme. • We instantiate the theorem with existing efficient itPIR-RV schemes to obtain two concrete itAPIR constructions for small-server and general-server settings, both with sublinear communication complexity. To highlight the differences between prior schemes and our results, Table I summarizes representative malicious-resilient PIR constructions. TABLE I: Comparison of representative malicious-resilient PIR schemes and our constructions. All schemes assume \ell servers and tolerate t corrupted servers for privacy. Scheme Corrupted Servers for Integrity ( v ) Selective-Failure Attack Resilience Security Model [ 15 ] \ell-1 \times Statistical [ 10 ] t \times Statistical [ 7 ] t \checkmark Computational [ 1 ] t \checkmark Statistical Theorem 2 \ell-1 \checkmark Statistical Theorem 3 t \checkmark Statistical II Preliminaries Notations. \mathbb{N} denotes the set of natural numbers \{1,2,3,\ldots\} . For any positive integer n , we denote [n]=\{1,2,\ldots,n\} and \{a_{j}\}_{j\in[n]}=\{a_{1},a_{2},\ldots,a_{n}\} . The indicator function \mathds{1}\{\mathcal{P}\} for a proposition \mathcal{P} , which outputs 1 if \mathcal{P} holds true and 0 otherwise. For two probability distributions X

Read the complete text