Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings 1
Pengzhen Ke, Liang Feng Zhang, Huaxiong Wang, Li-Ping Wang · 2026
Read Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings 1 by Pengzhen Ke, Liang Feng Zhang, Huaxiong Wang, Li-Ping Wang (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-00411.txt.
Introduction
Ke and colleagues propose a ring-based scheme for private information retrieval with error detection. The best current method leans on distributed point functions, but its finite-field design forces prime-order functions with very large keys under information-theoretic privacy. Its dual-key layout also adds needless traffic. Built over a prime-power ring instead, the new scheme sidesteps the field constraint, uses its point functions more efficiently, and shrinks keys sharply for large deployments.
Catalog record
| CREATOR | Pengzhen Ke, Liang Feng Zhang, Huaxiong Wang, Li-Ping Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49270 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00411
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings 1 Pengzhen Ke, Liang Feng Zhang, Huaxiong Wang, Li-Ping Wang Abstract Authenticated private information retrieval (APIR) is the state-of-the-art error-detecting private information retrieval (ED-PIR), using Distributed Point Functions (DPFs) for subpolynomial complexity and privacy. However, its finite field structure restricts it to prime-order DPFs, leading to prohibitively large key sizes under information-theoretic settings, while its dual-DPF-key design introduces unnecessary communication overhead, limiting its practicality for large-scale deployments. This paper proposes a novel ring-based information-theoretic ED-PIR (itED-PIR) scheme that overcomes these limitations by leveraging prime-power-order information-theoretic DPFs (itDPFs). Built over a prime-power ring, the proposed scheme breaks APIR’s field-induced constraint to enable more efficient DPF utilization, significantly reducing key size growth and rendering the scheme feasible for high-security scenarios. Additionally, a single-itDPF-key design halves query-side communication overhead by eliminating APIR’s redundant dual-key setup, without compromising privacy or verifiability. Beyond immediate efficiency gains, this work establishes a lightweight, flexible framework for constructing DPF-based malicious-resilient private information retrieval, opening new avenues for privacy-preserving data retrieval in distributed storage systems and post-quantum privacy protocols. keywords Private Information Retrieval, Distributed Point Function, Malicious Servers, Verifiable Computation 1 1 footnotetext: This work has been accepted for publication in Cybersecurity and is currently in press. 1 Introduction Private information retrieval (PIR) enables a client to retrieve a target database block x_{\alpha}\in{\bf x}=(x_{1},\ldots,x_{n}) while keeping the index \alpha\in[n] private from servers. For large-scale data, 7 proves that a trivial PIR scheme with O(n) communication complexity is impractical. Thus, multi-server information-theoretic PIR ( 2 ; 21 ; 10 ) has become the dominant direction. In this model, the database is replicated across servers, and t -privacy guarantees no coalition of up to t servers infers the retrieval index \alpha . A critical challenge in multi-server PIR is addressing malicious servers: these may return incorrect responses (due to attacks, network failures, or outdated data), leading to erroneous retrieval results. Among existing solutions for error detection, Authenticated PIR (APIR) ( 8 ) is a state-of-the-art Error-Detecting PIR (ED-PIR) scheme that leverages Distributed Point Functions (DPFs) to achieve subpolynomial communication complexity, providing a foundational solution for privacy-preserving retrieval with error detection. However, APIR suffers from following limitations. First, APIR relies on a dual-DPF-key design (two DPF keys per server) to implement its verification logic. This redundant design introduces unnecessary communication overhead. Second, APIR is strictly constrained to finite field constructions, limiting its compatibility to DPFs with prime-order output groups \mathbb{G}=(\mathbb{Z}_{p},+) . This constraint excludes the use of more efficient prime-power-order output group DPFs (over \mathbb{Z}_{p^{\tau}} for \tau\geq 2 ) and leads to inefficiency. These limitations motivate the development of a new ED-PIR scheme that retains the subpolynomial communication efficiency of APIR’s DPF-based framework, while eliminating its key redundancy and field-related constraints. To achieve these objectives, this paper presents a ring-based information-theoretic ED-PIR scheme instantiated from prime-power-order output group DPFs, which delivers significant efficiency improvements over APIR by addressing both of its foundational limitations. 1.1 Related Work Information-Theoretic PIR. Multi-server information-theoretic PIR (itPIR) was first formalized by 7 , with subsequent works 2 ; 21 ; 10 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. Malicious-Resilient PIR. To mitigate the risks posed by malicious responses, malicious-resilient PIR schemes ( 3 ; 20 ; 13 ; 9 ; 22 ; 18 ; 19 ; 1 ; 16 ; 24 ; 4 ; 14 ; 23 ; 25 ; 8 ; 15 ) introduce verification guarantees that allow the client to detect or even correct incorrect responses. Among these schemes, ED-PIR ( 14 ; 15 ; 11 ) achieves information-theoretic privacy and is (\ell-1,\epsilon) -verifiable for \ell servers with polylogathic communication complexity. In contrast, APIR ( 8 ) also achieves information-theoretic privacy but is (1,\epsilon) -verifiable, and has subpolynomial communication complexity. Information-Theoretic DPF. Information-Theoretic DPF (itDPF) was first introduced by 5 , which presents a statistically private scheme for 3 servers (with t=1 ) and output additive group \mathbb{Z}_{p} (for p\geq 2 ), as well as a perfectly private scheme for 4 servers and output additive group \mathbb{Z}_{p^{\tau}} (for p\geq 3 ). The work by 17 completes the perfectly private scheme for 4 servers with output additive group \mathbb{Z}_{p^{\tau}} (for p=2 ); additionally, it further proposes a t -private scheme for any t\geq 1 , along with a scheme where the key size is subpolynomially related to the size of the output field. Scheme \ell t Algebraic Structure Privacy Verifiable Communication Complexity Corollary 1 3 1 \mathbb{R}_{p} Statistical \bigl(1,\frac{1}{p-1}\bigr) O\bigl(\lambda\log p\cdot 2^{c_{1}(p)s(n)}\bigr) 4 1 \mathbb{R}_{p} Statistical \bigl(1,\frac{1}{p-1}\bigr) O\bigl(\lambda\cdot 2^{10s(n)}+\lambda\log p\bigr) Corollary 2 4 1 \mathbb{R}_{p^{\tau}} Perfect \bigl(1,\frac{1}{p^{\tau}-p^{\tau-1}}\bigr) O\bigl(\tau\log p\cdot 2^{c_{2}(p)s(n)}\bigr) Corollary 3 8 1 \mathbb{R}_{p} Perfect \bigl(1,\frac{1}{p-1}\bigr) O\bigl(2^{10s(n)}+\log p\bigr) Corollary 4 d(t+1) t \mathbb{R}_{p} Perfect \bigl(t,\frac{1}{p-1}\bigr) O\bigl(\log p\cdot n^{1/\lfloor(2d+1)/t\rfloor}\bigr) \text{APIR}^{\dagger} 3 1 \mathbb{F}_{p} Statistical \bigl(1,\frac{1}{p-1}\bigr) O\bigl(\lambda\log p\cdot 2^{c_{1}(p)s(n)}\bigr) 4 1 \mathbb{F}_{p} Perfect \bigl(1,\frac{1}{p-1}\bigr) O\bigl(\log p\cdot 2^{2p\cdot s(n)}\bigr) Table 1: Concrete instantiations information-theoretic ED-PIR Schemes ( \ell : the number of servers; t : the number of colluding servers; p : a prime; d,\tau : positive integers; \mathbb{R}_{p},\mathbb{R}_{p^{\tau}} : the ring \mathbb{R}_{p}=(\mathbb{Z}_{p},+,\cdot),\mathbb{R}_{p^{\tau}}=(\mathbb{Z}_{p^{\tau}},+,\cdot) ; c_{1},c_{2} : the function such that c_{1}(2)=6,c(3)=10,c(p)=2p for p\geq 5 ), c_{2}(2)=6,c_{2}(p)=2p for p\geq 3 ; s(n) : shorthand for \sqrt{\log n\log\log n} . \dagger : APIR ( 8 ) 1.2 Contributions This paper addresses the key inefficiencies of the state-of-the-art APIR scheme in 8 under the information-theoretic setting by proposing a novel ring-based information-theoretic ED-PIR scheme, with concrete diverse instantiations presented in Table 1 . As the first contribution, the information-theoretic ED-PIR scheme is constructed over the prime-power ring \mathbb{R}=(\mathbb{Z}_{p^{\tau}},+,\cdot) , breaking itAPIR’s finite field constraint that limits support to prime-order information-theoretic DPFs. This enables the design of a novel 4 -server perfectly 1 -private information-theoretic ED-PIR scheme with subpolynomial communication complexity (Corollary 2 in Table 1 ). Additionally, a single-DPF-key query framework is designed for ED-PIR, eliminating the dual-key redundancy of APIR and halving query-side communication overhead without any tradeoffs in privacy or verifiability. As the second contribution, a diverse set of concrete information-theoretic ED-PIR instantiations are provided (Table 1 ), covering 3 , 4 , 8 , and general d(t+1) server architectures, both statistical and perfect privacy, and collusion tolerance for t=1 to arbitrary t\geq 1 . This offers solutions for distributed storage systems with varying requirements, while maintaining subpolynomial communication complexity. 1.3 Technique Overview This work proposes a novel information-theoretic ED-PIR scheme constructed over the ring \mathbb{R}=(\mathbb{Z}_{p^{\tau}},+,\cdot) , which leverages a single DPF key per server to reduce query-side communication overhead. Error detection is realized via a ring-based verification check. Taking a binary database as an example, suppose the client intends to retrieve the element x_{\alpha}\in\{0,1\} from the database {\bf x}=(x_{1},\dots,x_{n}) . The client randomly selects an invertible element \beta\in\mathbb{R}^{\ast} (the unit group of \mathbb{R} ), then sends the DPF key corresponding to the point function f_{\alpha,\beta} to each server, and receives responses from the servers. In the absence of interference from malicious servers, the sum of these responses should be {\sf res}=\sum_{i\in[n]}f_{\alpha,\beta}(i)\cdot x_{i} , which equals x_{\alpha}\in\{0,1\} . If the result does not belong to \{0,1\} , the verification check identifies it as erroneous. The privacy guarantee of the DPF ensures that