Fault-Tolerant Private Information Retrieval via Threshold Distributed Point Functions Authors: Dazeng Yuan, Xiheng Liu, Bin Liu Published: 2026 ABSTRACT Multi-server private information retrieval (PIR) based on function secret sharing (FSS) has emerged as a prominent paradigm for achieving sublinear communication. However, standard FSS constructions require full server participation, making them highly vulnerable to single-node fail-stop faults. Existing fault-tolerant schemes mitigate this but inevitably inflate the response overhead to scale with the database size N (e.g., O(N)). To overcome this limitation, we propose a fault-tolerant PIR (FT-PIR) protocol based on a newly designed (t,p)-threshold distributed point function (FT-DPF). By introducing a hierarchical recursive patching mechanism, our scheme transforms rigid all-party evaluations into flexible t-out-of-p reconstructions. This architecture completely decouples the response communication from N and ensures efficient client-side reconstruction via lightweight XOR aggregations. Formal analysis proves that our stateless protocol guarantees (t−1)-computational privacy under the semi-honest model. Theoretical analysis demonstrates that the proposed FT-PIR achieves a response complexity bounded by O(Fmaxlevel(t,p)). Comprehensive experimental evaluations confirm that our implementation significantly reduces practical communication and computation overheads, outperforming the state-of-the-art scheme. 1. Introduction Private information retrieval (PIR) is a fundamental cryptographic primitive that enables a client to retrieve specific records from a public database containing N items without revealing the query index [1]. As a cornerstone for privacy-preserving data access, PIR has seen widespread adoption in private contact discovery [2], private web search [3], anonymity networks [4], and encrypted search systems [5]. Historically, PIR research has bifurcated into two primary architectures based on the underlying trust model: single-server and multi-server PIR. Single-server PIR operates without non-collusion assumptions and is predominantly driven by two technical paradigms: homomorphic encryption (HE) and hint-based preprocessing. However, both paradigms encounter inherent mechanistic bottlenecks. In HE-based constructions, schemes employing packing techniques to optimize bandwidth [6] suffer from prohibitive homomorphic computational overheads. Even with homomorphic Thorp shuffles to minimize circuit depth [7], the high constant-factor costs of HE evaluations remain a significant barrier. To accelerate online performance, recent schemes introduced preprocessing mechanisms [8] to achieve sublinear query times, albeit by imposing substantial state storage overhead on the client. Alternatively, a parallel route leverages hint-based preprocessing [9,10,11,12]. While these schemes utilize lightweight symmetric primitives to yield attractive time–space trade-offs, they mandatorily require exhaustive offline database scans. Furthermore, their hint mechanisms face periodic and heavy reconstruction burdens due to limited query budgets, restricting their practical viability in high-frequency scenarios. To circumvent the performance bottlenecks of single-server models, multi-server PIR achieves highly efficient retrieval by distributing trust across p non-colluding servers. Under this architecture, information-theoretic (IT) constructions based on algebraic coding have been extensively studied [13]. These schemes utilize polynomials and erasure codes to establish a communication efficiency of O(N1/3) [14] and optimal robustness bounds [15], ultimately achieving sub-polynomial communication via matching vector codes [16]. Despite these theoretical milestones, IT-PIR typically involves complex finite-field operations that concretely diminish their practical bandwidth advantages. Although recent advancements like multi-server preprocessing [17] attempt to amortize online computation, they inevitably force the client to maintain persistent states, failing to simultaneously balance sub-polynomial communication, stateless operation, and efficient fault tolerance. Parallel to IT-PIR, the function secret sharing (FSS) paradigm has emerged as an efficient approach for constructing lightweight multi-server PIR [18,19]. Specifically, its core instantiation for point queries—the distributed point function (DPF)—enables clients to compress query key overhead to O(logN). However, scaling standard DPFs from a two-server to a p-server environment (p≥3) initially introduced severe scalability issues, with request bandwidth exhibiting exponential growth (O(2pN)) relative to the number of servers [18]. While recent combinatorial design optimizations have successfully compressed this multi-party key size to O(p3N) [20], a far more critical vulnerability persists: standard FSS-based PIR protocols are exceptionally fragile as they require all p servers to remain online during the evaluation and reconstruction phases. While recent state-of-the-art works have introduced fault-tolerant DPF mechanisms to enhance system robustness [21], such approaches inevitably inflate the response overhead to O(N), essentially tying the downlink cost to the database size. To overcome this limitation, we propose a novel fault-tolerant PIR scheme (FT-PIR) grounded in a newly designed fault-tolerant DPF (FT-DPF). By leveraging a recursive patching mechanism, our scheme successfully generalizes a base (2,p)-threshold DPF into a (t,p)-threshold setting. This architecture enables the client to reconstruct the target data using responses from any t surviving servers. Consequently, as compared in Table 1, our protocol achieves a robust and lightweight retrieval process that effectively decouples the response complexity from N. 1.1. Our Contributions The main contributions of this paper are summarized as follows:A Novel (t,p)-Fault-Tolerant DPF Scheme: We formally define and construct a generalized (t,p)-fault-tolerant distributed point function (FT-DPF) through a hierarchical, bottom-up design. Specifically, we first optimize the key length of the state-of-the-art multi-party DPF [20]. Building upon this optimized DPF, we construct a highly efficient base (2,p) DPF scheme. Finally, we introduce a recursive patching mechanism to extend this base construction into a generalized (t,p)-threshold setting. This allows any t surviving servers to correctly reconstruct the evaluation, thereby tolerating up to p−t fail-stop failures.FT-PIR Protocol with Database-Size-Independent Response Overhead: Built upon our generalized FT-DPF, we propose a stateless, fault-tolerant PIR protocol. Unlike Shamir-based schemes burdened by an O(N) response overhead, our architecture completely decouples response communication from N, bounding the complexity to O(Fmaxlevel(t,p)). Given that practical non-colluding deployments treat p as a small constant relative to large-scale datasets (N≫p≥t), this design achieves flexible scalability for large-scale datasets. Furthermore, the client-side reconstruction relies purely on straightforward XOR aggregations, avoiding the heavy algebraic interpolations typical of traditional robust schemes.Formal Security and Performance Evaluation: We prove (t−1)-computational privacy under the semi-honest model. Theoretical and empirical results demonstrate that our protocol decouples response overhead from the database size and achieves sublinear queries, significantly outperforming the state-of-the-art [21]. A Novel (t,p)-Fault-Tolerant DPF Scheme: We formally define and construct a generalized (t,p)-fault-tolerant distributed point function (FT-DPF) through a hierarchical, bottom-up design. Specifically, we first optimize the key length of the state-of-the-art multi-party DPF [20]. Building upon this optimized DPF, we construct a highly efficient base (2,p) DPF scheme. Finally, we introduce a recursive patching mechanism to extend this base construction into a generalized (t,p)-threshold setting. This allows any t surviving servers to correctly reconstruct the evaluation, thereby tolerating up to p−t fail-stop failures. A Novel (t,p)-Fault-Tolerant DPF Scheme: We formally define and construct a generalized (t,p)-fault-tolerant distributed point function (FT-DPF) through a hierarchical, bottom-up design. Specifically, we first optimize the key length of the state-of-the-art multi-party DPF [20]. Building upon this optimized DPF, we construct a highly efficient base (2,p) DPF scheme. Finally, we introduce a recursive patching mechanism to extend this base construction into a generalized (t,p)-threshold setting. This allows any t surviving servers to correctly reconstruct the evaluation, thereby tolerating up to p−t fail-stop failures. FT-PIR Protocol with Database-Size-Independent Response Overhead: Built upon our generalized FT-DPF, we propose a stateless, fault-tolerant PIR protocol. Unlike Shamir-based schemes burdened by an O(N) response overhead, our architecture completely decouples response communication from N, bounding the complexity to O(Fmaxlevel(t,p)). Given that practical non-colluding deployments treat p as a small constant relative to large-scale datasets (N≫p≥t), this design achieves flexible scalability for large-scale datasets. Furthermore, the client-side reconstruction relies purely on straightforward XOR aggregations, avoiding the heavy algebraic interpolations typical of traditional robust schemes. FT-PIR Protocol with Database-Size-Independent Response Overhead: Built upon our generalized FT-DPF, we propose a stateless, fault-tolerant PIR protocol. Unlike Shamir-based schemes burdened by an O(N) response overhead, our architecture completely decouples response communication from N, bounding the complexity to O(Fmaxlevel(t,p)). Given that practical non-colluding deployments treat p as a small constant relative to large-scale datasets (N≫p≥t), this design achieves flexible scalability for large-scale datasets. Furthermore, the client-side reconstruction relies purely on straightforward XOR aggregations, avoiding the heavy algebraic interpolations typical of traditional robust schemes. Formal Security and Performance Evaluation: We prove (t−1)-computational privacy under the semi-honest model. Theoretical and empirical results demonstrate that our protocol decouples response overhead from the database size and achieves sublinear queries, significantly outperforming the state-of-the-art [21]. Formal Security and Performance Evaluation: We prove (t−1)-computational privacy under the semi-honest model. Theoretical and empirical results demonstrate that our protocol decouples response overhead from the database size and achieves sublinear queries, significantly outperforming the state-of-the-art [21]. 1.2. Organization The remainder of this paper is organized as follows. Section 2 introduces the necessary cryptographic preliminaries. Section 3 formalizes the system model and definitions. Building upon this foundation, Section 4 details the core technical contribution: the hierarchical construction of the generalized threshold DPF. Section 5 then deploys this primitive to construct the fault-tolerant PIR protocol. Section 6 formalizes the composite security paradigm and provides theoretical proofs for query privacy and fault tolerance. Section 7 presents a comprehensive efficiency evaluation, encompassing both theoretical analysis and experimental comparisons. Section 8 reviews the existing literature on single-server and multi-server PIR architectures. Finally, Section 9 concludes the paper and outlines directions for future work. 2. Preliminaries In this section, we introduce some essential preliminary concepts such as DPF [18,20] and replicated secret sharing [22]. Table 2 lists the key notations used in this paper. 2.1. Distributed Point Function A distributed point function (DPF) [18,19] is a cryptographic primitive that enables a client to secretly share a point function across multiple servers. Let (G,+) be an Abelian group. A point function fα,β:{0,1}n→G is defined such that fα,β(x)=β if x=α, and 0 otherwise, where α∈{0,1}n is the target input and β∈G∖{0} is the non-zero output value. In a p-party DPF, the client splits fα,β into p distinct keys k1,…,kp. This splitting guarantees that any strict subset of the keys reveals no information about the secret parameters (α,β), yet the aggregated evaluations of all keys at a given point x correctly reconstruct fα,β(x). Conceptually, these keys act as secret shares of a vector of length N=2n, where all elements are zero except for the index corresponding to α. Formally, a DPF scheme is defined as follows: (Distributed Point Function [18]). A p-party DPF scheme over the domain {0,1}n and an Abelian group (G,+) comprises two probabilistic polynomial-time (PPT) algorithms (Gen,Eval) satisfying the following properties: Syntax:–(k1,…,kp)←Gen(1λ,α,β): Takes as input a security parameter λ, a target index α∈{0,1}n, and a payload β∈G. It outputs a p-tuple of keys (k1,…,kp).–yi←Eval(i,ki,x): Takes as input a party index i∈[p], the corresponding key ki, and an evaluation point x∈{0,1}n. It outputs a group element yi∈G.Correctness: For any α∈{0,1}n, β∈G, and any x∈{0,1}n, if (k1,…,kp)←Gen(1λ,α,β), then it holds with probability 1 that ∑i=1pEval(i,ki,x)=fα,β(x).Privacy: For any strict subset of indices I⊂[p] (i.e., |I|