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

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

arXiv:2604.22505v1 [cs.CR] 24 Apr 2026

Pengzhen Ke,

Yuxuan Qin,

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 selectivefailure 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. I NTRODUCTION Private Information Retrieval (PIR) [1] allows a client to retrieve a target database block xα ∈ x = (x1 , . . . , xn ) while preserving the privacy of the retrieval index α ∈ [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 [2]–[27]. 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 α. While early PIR protocols typically assume honest-butcurious 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α . This concern has spurred extensive research on PIR protocols resilient to malicious servers [3]–[5], [8], [9], [11]–[15], [17]–[22], [24], [27], which are of particular interest in cloud computing scenarios. Among existing solutions for malicious server tolerance, two representative types of verifiable PIR protocols stand 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).

Liang Feng Zhang

out, both equipped with integrity guarantees (i.e., they ensure the client can either recover the correct xα or output ⊥ to indicate invalid responses): Authenticated PIR (APIR) and PIR with Result Verification (PIR-RV). As a stateof-the-art error-detecting PIR scheme, APIR [20] 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α ) or rejects it (outputs ⊥). In contrast, PIR-RV [17], [21], a relaxed variant of APIR, does not require resistance to selective-failure attacks; its privacy guarantee only ensures that colluding servers cannot infer α 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. A. Related Works 1) Information-Theoretic PIR: Multi-server informationtheoretic PIR (itPIR) was first formalized by Chor et al. [1], with subsequent works [2], [6], [7] 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. 2) Malicious-Resilient PIR: To tolerate malicious servers, verifiable PIR schemes [3]–[5], [8], [9], [11]–[21], [24] introduce integrity guarantees, enabling the client to detect or even correct incorrect responses. Among them, itPIR-RV [16], [17], [21] achieves information-theoretic (v, ϵ)-integrity (i.e., the probability that the client accepts an incorrect response is at most ϵ, enven if up to v servers collude maliciously) and only guarantees basic perfect or statistical privacy; APIR [20]

TABLE I C OMPARISON OF REPRESENTATIVE MALICIOUS - RESILIENT PIR SCHEMES AND OUR CONSTRUCTIONS . A LL SCHEMES ASSUME ℓ SERVERS AND TOLERATE t CORRUPTED SERVERS FOR PRIVACY.

and Y are statistically indistinguishable, i.e., their statistical distance ∆(X, Y ) is negligible in the security parameter. A. Information-Theoretic Authenticated PIR

Scheme [21] [16] [20] [24] Theorem 2 Theorem 3

Corrupted Servers Selective-Failure for Integrity (v) Attack Resilience ℓ−1 t t t ℓ−1 t

× × ✓ ✓ ✓ ✓

Security Model Statistical Statistical Computational Statistical Statistical Statistical

provides strengthened privacy with resistance to selectivefailure attacks but relies on computational assumptions, for which no information-theoretic variant has been formally defined. 3) APIR vs. PIR-RV: Existing works treat APIR and PIRRV 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. B. Our Contributions This work makes four key contributions to informationtheoretic malicious-resilient PIR: • We propose information-theoretic Authenticated PIR (itAPIR), requiring statistical t-privacy against selectivefailure attacks and (v, ϵ)-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 selectivefailure-attack resilience. • We prove a conversion theorem: any perfect/statistical t-private itPIR-RV scheme with (v, ϵ)-integrity, where v ≥ t and ϵ is negligible, can be transformed into a statistically t-private itAPIR scheme. • We instantiate the theorem with existing efficient itPIRRV 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. II. P RELIMINARIES Notations. N denotes the set of natural numbers {1, 2, 3, . . .}. For any positive integer n, we denote [n] = {1, 2, . . . , n} and {aj }j∈[n] = {a1 , a2 , . . . , an }. The indicator function 1{P} for a proposition P, which outputs 1 if P holds true and 0 otherwise. For two probability distributions X and Y over the same finite set: X ≡ Y means X and Y are perfectly equivalent (identical probability distributions), i.e., their statistical distance ∆(X, Y ) = 0; X ≈s Y means X

The concept of Authenticated PIR [20] was originally introduced with a computational security level. In this work, we present its definition in the information-theoretic setting. Informally, an ℓ-server information-theoretic APIR (itAPIR) scheme involves ℓ servers {Sj }j∈[ℓ] , each storing a copy of the same database x = (x1 , . . . , xn ) ∈ ({0, 1}m )n (each entry xi is an m-bit block), and a client seeking to retrieve xα for some α ∈ [n]. The scheme guarantees that the client can correctly recover xα when all ℓ servers {Sj }j∈[ℓ] are honest and respond correctly, or output a special symbol ⊥ to indicate incorrect responses. The scheme is said to be t-private in the information-theoretic sense: any coalition of up to t malicious servers gains statistically no information about the client’s retrieval index α, even if the adversary learns whether the client accepts the retrieved result or outputs the rejection symbol ⊥. Definition 1 (itAPIR). An ℓ-server itAPIR scheme Γ = (Que, Ans, Rec) consists of three algorithms executed by the client and servers as specified below: κ • ({qj }j∈[ℓ] , aux) ← Que(1 , n, α): A randomized querying algorithm executed by the client. It takes the security parameter κ, the database size n, and retrieval index α ∈ [n] as input, and outputs ℓ queries {qj }j∈[ℓ] (with qj sent to server Sj ) and auxiliary information aux for reconstruction. • aj ← Ans(x, qj ): A deterministic answering algorithm executed by server Sj (j ∈ [ℓ]). It takes the database x = (x1 , . . . , xn ) ∈ ({0, 1}m )n and query qj as input, and outputs a response aj . • y ← Rec({aj }j∈[ℓ] , aux): A deterministic reconstructing algorithm executed by the client. It takes the responses {aj }j∈[ℓ] and auxiliary information aux as input, and outputs either the correct value y = xα (when all responses are valid) or the symbol y =⊥ (indicating at least one invalid response). To formalize the above goals, an itAPIR scheme Γ must satisfy the following three properties: Definition 2 (itAPIR Correctness). Informally, Γ is correct if the reconstruction algorithm Rec outputs the correct value xα when all ℓ servers respond honestly. Formally, for any security parameter κ ∈ N, database size n ∈ N, data entry size m ∈ N, database x ∈ ({0, 1}m )n , any retrieval index α ∈ [n], and queryauxiliary pair ({qj }j∈[ℓ] , aux) ← Que(1κ , n, α), let y ←
Rec {Ans(x, qj )}j∈[ℓ] , aux . Then: Pr [y = xα ] = 1. Definition 3 (itAPIR Statistical Privacy). Informally, Γ is statistically t-private if any coalition of up to t malicious servers gains no information about the client’s retrieval index

α, even if the adversary learns whether the client accepts the result or rejects it (outputs ⊥). This captures security against selective-failure attacks, a critical strengthened privacy property of APIR. Formally, let the subset T ⊆ [ℓ] with cardinality |T| ≤ t be the set of the indices of corrupted servers, that is, the adversary controls the servers {Sj }j∈T . For any probabilistic computationally unbounded two-stage adversary A with two polynomial-time algorithms A0 , A1 , any database size n ∈ N, any data entry size m ∈ N, any database x ∈ ({0, 1}m )n , and any retrieval index α ∈ [n], define the real experiment:   ({qj }j∈[ℓ] , aux) ← Que(1κ , n, α),           (stA , {ãj }j∈T ) ← A0 (x, {qj }j∈T ),        a ← Ans(x, q ) ∀j ∈ [ℓ] \ T,  j j REALα = β : .  y ← Rec({aj }j ∈T / ∪ {ãj }j∈T , aux),           b ← 1{y ̸=⊥},       β ← A1 (stA , b) The scheme is statistically t-private if there exists a two-stage simulator Sim with two polynomial algorithm Sim0 , Sim1 such that REALα ≈s IDEALSim for all α ∈ [n], where IDEALSim is defined as:   (stSim , {qj′ }j∈T )       κ     ← Sim (1 , n, x, T), 0        (st , {ã }  A j j∈T ) . IDEALSim = β : ′  ← A0 (x, {qj }j∈T ),           b ← Sim1 (stSim , {ãj }j∈T ),       β ← A1 (stA , b) Regarding the absence of a “perfectly private itAPIR‘’ definition, we note that such a notion (requiring REALα ≡ IDEALSim for all α) is logically feasible in theory. However, our core conversion theorem (Theorem 1) reveals a fundamental constraint: the (v, ϵ)-integrity of itPIR-RV introduces a negligible statistical error ϵ, which propagates to the privacy guarantee of the upgraded itAPIR scheme. This makes perfect privacy unattainable via the itPIR-RV upgrade path. Thus, we focus only on statistical privacy for itAPIR in this work. Definition 4 (itAPIR Integrity). Informally, the scheme Γ satisfies (v, ϵ)-integrity if no coalition of up to v servers can deceive the client with retrieval index α into outputting a result y ∈ / {xα , ⊥} by providing fraudulent responses. Formally, for any adversary A controlling a set of servers V ⊆ [ℓ] of cardinality at most v, any database x ∈ ({0, 1}m )n , and any index α ∈ [n], the probability that the client outputs an incorrect value is bounded by ϵ:   y∈ / {xα , ⊥} :   ({qj }j∈[ℓ] , aux) ← Que(1κ , n, α),      ≤ ϵ. {ãj }j∈V ← A(x, {qj }j∈V ), Pr      aj ← Ans(x, qj ) ∀j ∈ / V,   y ← Rec({aj }j ∈V / ∪ {ãj }j∈V , aux)

B. PIR with Result Verification An information-theoretic ℓ-server PIR with Result Verification (itPIR-RV) [16], [17], [21], [23], [25] scheme is a relaxed variant of the information-theoretic APIR (itAPIR) scheme (Section II-A). It shares the same correctness and (v, ϵ)-integrity properties as itAPIR. The only key difference lies in privacy: unlike itAPIR (which requires statistical privacy against selective-failure attacks), itPIR-RV does not guarantee resistance to selective-failure attacks. Its privacy only ensures that colluding servers gain no information about α from query distributions alone (ignoring the client’s acceptance/rejection outcome), and includes two informationtheoretic flavors: perfect privacy and statistical privacy. Definition 5 (itPIR-RV Correctness). Informally, Π is correct if the reconstruction algorithm Rec outputs the correct value xα when all ℓ servers respond honestly. This property is identical to itAPIR correctness (Definition 2). Definition 6 (itPIR-RV Perfect Privacy). Informally, an itPIR-RV scheme Π = (Que, Ans, Rec) is perfectly t-private if any coalition of up to t servers gains absolutely no information about the client’s retrieval index α from query distributions alone. No adversary—even with unbounded computational power—can distinguish query distributions for different α. Formally, for any security parameter κ ∈ N, database size n ∈ N, any index α ∈ [n], and any subset T ⊆ [ℓ] with |T| ≤ t, let the query distribution:  REALα = {qj }j∈T : ({qj }j∈[ℓ] , aux) ← Que(1κ , n, α) . There exists a simulator Sim′ such that for any α ∈ [n], the ideal distribution:  IDEALSim′ = {qj }j∈T ← Sim′ (1κ , n, T) , satisfies REALα ≡ IDEALSim′ . Definition 7 (itPIR-RV Statistical Privacy). Informally, an itPIR-RV scheme Π = (Que, Ans, Rec) is statistically tprivate if any coalition of up to t servers gains statistically no information about the client’s retrieval index α from query distributions alone. Formally, for any security parameter κ ∈ N, database size n ∈ N, any index α ∈ [n], and any subset T ⊆ [ℓ] with |T| ≤ t, let REALα and IDEALSim′ be defined as in Definition 6. There exists a simulator Sim′ such that for any α ∈ [n]: REALα ≈s IDEALSim′ . Remark 1. Perfect t-privacy (Definition 6) is strictly stronger than statistical t-privacy (Definition 7): perfect distributional equivalence (X ≡ Y ) implies statistical indistinguishability (X ≈s Y ), so any perfectly t-private itPIRRV scheme is inherently statistically t-private. An itPIR-RV scheme is deemed privacy-preserving if it satisfies either of these two definitions (only one is required).

Remark 2. The privacy definitions above (Definitions 6 and 7) are equivalent to the standard formulation for informationtheoretic PIR. Let ∼ denote ≡ (perfect) or ≈s (statistical), where REALα0 ∼ REALα1 (for any distinct α0 , α1 ∈ [n]) is the standard privacy condition. Mutual equivalence holds: (i) (⇒) Suppose a scheme satisfies either perfect or statistical t-privacy (per Definitions 6/7), i.e., there exists a simulator Sim′ such that REALα ∼ IDEALSim′ for all α ∈ [n]. By transitivity of ∼ (equivalence or indistinguishability), we have REALα0 ∼ REALα1 for any distinct α0 , α1 ∈ [n]. (ii) (⇐) Suppose REALα0 ∼ REALα1 for any distinct α0 , α1 ∈ [n]. Construct a simulator Sim′ that samples from REALα (for any fixed α ∈ [n]). For any α′ ∈ [n], REALα′ ∼ REALα , so REALα′ ∼ IDEALSim′ , satisfying the respective privacy definition. Definition 8 (itPIR-RV Integrity). Informally, the scheme Π satisfies (v, ϵ)-integrity if no coalition of up to v servers can deceive the client with retrieval index α into outputting a result y ∈ / {xα , ⊥} by providing fraudulent responses. This property is identical to itAPIR integrity (Definition 4). III. F ROM IT PIR-RV TO ITAPIR In Sections II-A and II-B, we defined itAPIR (Definition 1) and itPIR-RV (a relaxed itAPIR variant lacking selectivefailure attack resistance). A natural question arises: Under what conditions can an itPIR-RV scheme upgrade to an itAPIR scheme, and how to derive practical itAPIR constructions? This section addresses both via two contributions: First, we prove a key conversion theorem: an itPIR-RV scheme satisfying specific integrity and privacy properties can be directly regarded as an itAPIR scheme, as it inherently achieves the strengthened privacy (resistance to selectivefailure attacks) required by itAPIR. Second, using this theorem with existing efficient itPIR-RV schemes, we present two concrete itAPIR constructions to verify the theorem’s practicality. Informally, the core insight of the conversion is as follows: The only gap between itPIR-RV and itAPIR lies in privacy—while itPIR-RV only guarantees query privacy (either perfect or statistical, itAPIR requires statistical privacy against selective-failure attacks. The (v, ϵ)-integrity of itPIRRV (with v ≥ t) bridges this gap: it limits the probability that adversaries (controlling up to t ≤ v servers) can submit malicious answers that deceive the client into accepting an incorrect result (i.e., y ∈ / {xα , ⊥}) to a negligible value ϵ. Combining this integrity guarantee with the privacy of itPIRRV, we show that the adversary’s view (including queries and the acceptance/rejection signal b) in the real itAPIR experiment is statistically indistinguishable from that in the ideal experiment—thus satisfying the full privacy requirement of itAPIR. Formally, we state the conversion theorem below, followed by a rigorous proof to validate the above intuition. Theorem 1. Let Π = (Que, Ans, Rec) be an ℓ-server itPIRRV scheme satisfying either perfect t-privacy (Definition 6)

or statistical t-privacy (Definition 7). If Π satisfies (v, ϵ)integrity (Definition 8) for v ≥ t and a negligible function ϵ in the security parameter κ, then Π is an ℓ-server statistically t-private itAPIR scheme that satisfies the selective-failure attack resistance required by itAPIR’s statistical privacy (Definition 3). Proof. To prove the theorem, we only need to show that Π satisfies the statistical privacy requirement of itAPIR, i.e., privacy against selective-failure attacks. For any probabilistic computationally unbounded adversary A = (A0 , A1 ) (controlling a subset T ⊆ [ℓ] of servers with |T| ≤ t), let a simulator Sim = (Sim0 , Sim1 ) proceed as follows—using the underlying simulator Sim′ of scheme Π (from itPIR-RV’s privacy definition (either Definition 6 or 7)): Sim0 (1κ , n, x, T)

Sim1 (stSim , {ãj }j∈T ) ′

κ

1: {qj }j∈T ← Sim (1 , n, T), 2: ∀j ∈ T, aj ← Ans(x, qj ), 3: stSim ← {aj }j∈T , 4: return (stSim , {qj }j∈T ).

1: {aj }j∈T ← stSim , 2: ∀j ∈ T, δj = ãj − aj , 3: b ← 1{∧j∈T (δj = 0)}, 4: return b.

To bridge the real and ideal privacy experiments and verify indistinguishability, we define a sequence of hybrid experiments H0 , H1 , H2 , H3 as follows: •

H0 : This is the real privacy experiment REALα (Definition 3). The challenger runs the protocol honestly for the retrieval index α. A0 receives queries for the corrupted servers and returns potentially malformed answers. A1 receives a bit b indicating whether the client accepted the result.

H0 =

         

({qj }j∈[ℓ] , aux) ← Que(1κ , n, α), ∀j ∈ [ℓ], aj ← Ans(x, qj ), β:

         •

(stA , {ãj }j∈T ) ← A0 (x, {qj }j∈T ),

         

y ← Rec({aj }j∈[ℓ]\T ∪ {ãj }j∈T , aux),      b ← 1{y ̸=⊥},    β ← A1 (stA , b)

.

H1 : Same as H0 except for the computation of the acceptance bit b: instead of determining b via the client’s reconstruction algorithm Rec (checking if y ̸=⊥), the challenger computes b by verifying whether the adversary’s answers {ãj }j∈T match the honest answers {aj }j∈T (generated from the same queries). The bit b is set to 1 if and only if all answers are identical.

H1 =

                  

β:

 ({qj }j∈[ℓ] , aux) ← Que(1κ , n, α),      ∀j ∈ T, aj ← Ans(x, qj ),    (st , {ã } ) ← A (x, {q } ), A

j j∈T

0

∀j ∈ T, δj = ãj − aj , b ← 1{∧j∈T (δj = 0)}, β ← A1 (stA , b)

j j∈T

        

.

•

H2 : Same as H1 except for the generation of queries {qj }j∈T : instead of using the honest query algorithm   {qj }j∈T ← Sim′ (1κ , n, T),           ∀j ∈ T, aj ← Ans(x, qj ),        (st , {ã }  ) ← A (x, {q } ), A j j∈T 0 j j∈T H2 = β : .    ∀j ∈ T, δj = ãj − aj ,         b ← 1 {∧j∈T (δj = 0)} ,        β ← A1 (stA , b)

Que (which depends on the retrieval index α), queries are generated via the simulator Sim′ (from itPIR-RV’s privacy definition (either Definition 6 or 7)). • H3 : Identical in structure to H2 , and corresponds to the ideal privacy experiment IDEALSim (Definition 3). This experiment operates without access to the client’s retrieval index α.   β:         κ   (st , {q } ) ← Sim (1 , n, x, T),   Sim j j∈T 0   H3 =

(stA , {ãj }j∈T ) ← A0 (x, {qj }j∈T ),    b ← Sim1 (stSim , {ãj }j∈T ),     β ← A1 (stA , b)

.

      

We now prove the indistinguishability of the hybrid experiments. To quantify this, we first define an event for each hybrid: For j ∈ {0, 1, 2, 3}, let Wj be the event that the output of the hybrid experiment Hj is “1”. • Hybrid H1 is identical to H0 except for how the acceptance bit b is set: H0 sets b = 1{y ̸=⊥}, while H1 sets b = 1{∧j∈T (δj = 0)}. The two hybrids differ only if the adversary submits incorrect answers (∃j ∈ T, ãj ̸= aj ) but the client’s Rec algorithm fails to output ⊥ (i.e., the client accepts an incorrect value). By the (v, ϵ)-integrity property of itPIR-RV (Definition 8), the probability of this event is bounded by ϵ. Thus: | Pr[W0 ] − Pr[W1 ]| ≤ ϵ. •

Hybrid H2 differs from H1 only in the generation of queries {qj }j∈T : H1 uses the real algorithm Que(1κ , n, α), while H2 uses the simulator Sim′ from itPIR-RV’s privacy definition (either Definition 6 or 7). By the itPIR-RV scheme’s t-privacy guarantee, the two query distributions are statistically indistinguishable, with perfect equivalence being a strict special case of statistical indistinguishability. Since the adversary’s entire view is determined solely by these queries, the hybrids’ output distributions are also statistically indistinguishable, giving: | Pr[W1 ] − Pr[W2 ]| ≤ negl(κ)

•

(i.e., H1 ≈s H2 ),

where negl(κ) denotes a negligible function in κ. Hybrid H3 is fully equivalent to H2 : H2 ’s query generation matches Sim0 , and its bit b computation corresponds to Sim1 . All operations in H2 map one-to-one to H3 , so they implement the same random process: Pr[W2 ] = Pr[W3 ]

(i.e., H2 ≡ H3 ).

Combining the indistinguishability of consecutive hybrids, we have: | Pr[W0 ] − Pr[W3 ]| ≤ ϵ + negl(κ) = negl2 (κ), where the inequality follows from the hybrid bounds, and the equality holds as ϵ is negligible (by the theorem’s premise) and sums of negligible functions are negligible (negl2 (κ) denotes the combined function). Recall that REALα = H0 and IDEALSim = H3 . This directly implies that REALα ≈s IDEALSim . We thus conclude that the scheme Π satisfies the statistical privacy requirement of itAPIR (Definition 3), including resistance to selective-failure attacks. This completes the proof of the theorem. Theorem 2. There exists an ℓ-server itAPIR scheme satisfying the following properties: • Statistical t-privacy against selective-failure attacks, • (v,ϵ)-integrity, 
ℓ2 nℓ 1/(⌊(2ℓ−1)/t⌋−1) • O log p communication comt t plexity, 3 where 2 ≤ ℓ ≤ 5, 1 ≤ t < ℓ, v = ℓ − 1, ϵ = p−2 , and p denotes the size of a finite field. Proof. The desired itAPIR scheme is constructed by leveraging our conversion theorem (Theorem 1) and the informationtheoretic PIR-RV (itPIR-RV) construction in [21]. Theorem 3. There exists an ℓ-server itAPIR scheme satisfying the following properties: • Statistical t-privacy against selective-failure attacks, • (v, ϵ)-integrity, ⌊(2(ℓ−t)−1)/t⌋−1 • n (log n + log ϵ−1 )(ℓ − t)1+o(1) ℓ2+o(1) communication complexity, where ℓ ≥ 2, 1 ≤ t < ℓ/2, v = t, ϵ > 0. Proof. The desired itAPIR scheme is constructed by leveraging our conversion theorem (Theorem 1) and the homomorphic MAC-based PIR construction in [16]. IV. C ONCLUSION We introduced information-theoretic Authenticated PIR (itAPIR), formalized its relation to itPIR-RV, and showed that any suitable itPIR-RV scheme can be converted into a secure itAPIR scheme. Based on this result, we obtained two concrete itAPIR constructions for small-server and generalserver settings, both achieving sublinear communication complexity. Overall, our work clarifies the landscape of informationtheoretic malicious-resilient PIR and provides an assumptionfree approach to constructing itAPIR from existing itPIRRV schemes [16], [21], with potential relevance to quantumresistant PIR in malicious environments.

R EFERENCES [1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” Journal of the ACM (JACM), vol. 45, no. 6, pp. 965–981, 1998. [2] A. Beimel and Y. Ishai, “Information-theoretic private information retrieval: A unified construction,” in Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings 28. Springer, 2001, pp. 912–926. [3] A. Beimel and Y. Stahl, “Robust information-theoretic private information retrieval,” in International Conference on Security in Communication Networks. Springer, 2002, pp. 326–341. [4] E. Y. Yang, J. Xu, and K. H. Bennett, “Private information retrieval in the presence of malicious failures,” in Proceedings 26th Annual International Computer Software and Applications. IEEE, 2002, pp. 805–810. [5] I. Goldberg, “Improving the robustness of private information retrieval,” in 2007 IEEE Symposium on Security and Privacy (SP’07). IEEE, 2007, pp. 131–148. [6] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” Journal of the ACM (JACM), vol. 55, no. 1, pp. 1–16, 2008. [7] K. Efremenko, “3-query locally decodable codes of subexponential length,” in Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 39–44. [8] C. Devet, I. Goldberg, and N. Heninger, “Optimally robust private information retrieval,” in 21st USENIX Security Symposium (USENIX Security 12), 2012, pp. 269–283. [9] L. F. Zhang and R. Safavi-Naini, “Verifiable multi-server private information retrieval,” in International Conference on Applied Cryptography and Network Security. Springer, 2014, pp. 62–79. [10] H. Sun and S. A. Jafar, “The capacity of private information retrieval,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075– 4088, 2017. [11] ——, “The capacity of robust private information retrieval with colluding databases,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2017. [12] K. Banawan and S. Ulukus, “The capacity of private information retrieval from byzantine and colluding databases,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1206–1219, 2018. [13] K. Kurosawa, “How to correct errors in multi-server pir,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2019, pp. 564–574. [14] L. Zhao, X. Wang, and X. Huang, “Verifiable single-server private information retrieval from lwe with binary errors,” Information Sciences, vol. 546, pp. 897–923, 2021. [15] S. Ben-David, Y. T. Kalai, and O. Paneth, “Verifiable private information retrieval,” in Theory of Cryptography Conference. Springer, 2022, pp. 3–32. [16] R. Eriguchi, K. Kurosawa, and K. Nuida, “On the optimal communication complexity of error-correcting multi-server pir,” in Theory of Cryptography Conference. Springer, 2022, pp. 60–88. [17] P. Ke and L. F. Zhang, “Two-server private information retrieval with result verification,” in 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 408–413. [18] L. F. Zhang, H. Wang, and L.-P. Wang, “Byzantine-robust private information retrieval with low communication and efficient decoding,” in Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, 2022, pp. 1079–1085. [19] L. Zhu, C. Lin, F. Lin, and L. F. Zhang, “Post-quantum cheating detectable private information retrieval,” in IFIP International Conference on ICT Systems Security and Privacy Protection. Springer, 2022, pp. 431–448. [20] S. Colombo, K. Nikitin, H. Corrigan-Gibbs, D. J. Wu, and B. Ford, “Authenticated private information retrieval,” in 32nd USENIX security symposium (USENIX Security 23), 2023, pp. 3835–3851. [21] P. Ke and L. F. Zhang, “Private information retrieval with result verification for more servers,” in International Conference on Applied Cryptography and Network Security. Springer, 2023, pp. 197–216. [22] S. Kruglik, S. H. Dau, H. M. Kiah, and H. Wang, “Two-server private information retrieval with optimized download rate and result verification,” in 2023 IEEE International Symposium on Information Theory (ISIT). IEEE, 2023, pp. 1354–1359.

[23] R. Eriguchi, K. Kurosawa, and K. Nuida, “Efficient and generic methods to achieve active security in private information retrieval and more advanced database search,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 92–121. [24] B. Alon and A. Beimel, “On the definition of malicious private information retrieval,” in 6th Conference on Information-Theoretic Cryptography (ITC 2025). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025, pp. 8–1. [25] J. Li, P. Ke, and L. F. Zhang, “Efficient information-theoretic distributed point functions with general output groups,” Designs, Codes and Cryptography, vol. 93, no. 5, pp. 1501–1530, 2025. [26] L. F. Zhang, “A unified framework for constructing informationtheoretic private information retrieval,” Pragmatic Cybersecurity, vol. 1, no. 1, p. 3, 2025. [27] P. Ke, L. F. Zhang, H. Wang, and L.-P. Wang, “Efficient DPF-based error-detecting information-theoretic private information retrieval over rings,” Cybersecurity, vol. 9, no. 1, p. 149, 2026.