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|
2), the algorithm first assigns foundational keys to the initial t servers. For any incrementally added server Psub[i] (i>t), the allocation proceeds in two critical phases:1.Conflict Inheritance and Resolution: The new server Psub[i] first inherits the complete structural state of its corresponding conflict party Psub[conflict] (where conflict=i−t). Subsequently, fresh patch components from V1 and V2 are assigned to both parties respectively, precisely resolving the primary cryptographic conflict at that level.2.Dimensional Degradation: For the remaining t−2 components, the scheme applies a polynomial-size combinatorial permutation to re-partition the PRG seeds. By recursively invoking the allocation function, the architecture elegantly collapses the remaining high-order sharing requirements into a manageable (t−2)-of-(i−2) sub-problem. As visualized in Figure 7, auxiliary patch keys are precisely generated at the specified hierarchical depth. Algorithm 4 Generalized (t,p)-Threshold DPF: Evaluation and ReconstructionRequire:DPF.{Eval2ofp,Rec2ofp}: Pairwise algorithms imported from Algorithm 2.Prec: A sorted list of t surviving server indices.Fmaxlevel(t,p): Maximum sharing level function defined in Equation (4). DPF.Evaltofp(j,Kj,x): 1:Yj←DPF.Eval2ofp(j,Kj,x). ▹ Local evaluation intrinsically matches the pairwise logic. 2:return Yj.DPF.Rectofp(t,p,Prec,Psub,{Yi}i∈Prec): 1:Initialize output bit y←0. 2:if t=2 then 3: return DPF.Rec2ofp(2,p,Prec,Psub,{Yj}j∈Prec). 4:end if 5:Map surviving servers to relative 1-based indices: Ind←(Index(Psub,m)∣m∈Prec). 6:while true do 7: if Ind[t]=t then 8: y←⨁j=1tYPrec[j][1]; break. ▹ Base case: XOR first shares of baseline servers. 9: else10: conflict←Ind[t]−t. ▹ Calculate the conflict index for server Prec[t].11: if conflict∈Ind then12: reclevel←Fmaxlevel(t,Ind[t]−1)+1. ▹ Determine the active target level.13: yconf←YPsub[conflict][reclevel]⊕YPrec[t][reclevel]. ▹ Primary conflict resolution.14: Prec′←Prec∖{Psub[conflict],Prec[t]}.15: Psub′←{m∈Psub∣m2): The algorithm first maps each element in the surviving set to its relative 1-based index array Ind within the current participating subset Psub. It then iteratively traverses the sharing topology via a deterministic loop:–Base t-party Subset: If the maximum current index satisfies Ind[t]=t, the foundational base subset is reached. The target bit is recovered directly by XOR-accumulating the first elements of the evaluation shares from these initial t servers.–Direct Conflict Resolution: It computes the conflict index conflict=Ind[t]−t. If conflict∈Ind, a direct structural conflict is identified. The algorithm determines the target active level reclevel, extracts the primary resolution yconf by XORing the corresponding shares, prunes the evaluated suffix vectors, and reduces the operation into a (t−2) sub-problem. (If t−2=1, it directly extracts the scalar bit; otherwise, it resolves recursively).–Conflict Party Substitution: If conflict∉Ind, it implies the conflict party is absent and its role must be delegated. The algorithm performs a response substitution: the highest-index active server Prec[t] is replaced by its conflict party Psub[conflict]. The active set is then re-sorted, and the index mapping Ind is synchronized to continue the iterative traversal towards the base subset.
Base Case (t=2): The function directly invokes the pairwise base reconstruction logic.
Base Case (t=2): The function directly invokes the pairwise base reconstruction logic.
Iterative Traversal and Conflict Resolution (t>2): The algorithm first maps each element in the surviving set to its relative 1-based index array Ind within the current participating subset Psub. It then iteratively traverses the sharing topology via a deterministic loop:–Base t-party Subset: If the maximum current index satisfies Ind[t]=t, the foundational base subset is reached. The target bit is recovered directly by XOR-accumulating the first elements of the evaluation shares from these initial t servers.–Direct Conflict Resolution: It computes the conflict index conflict=Ind[t]−t. If conflict∈Ind, a direct structural conflict is identified. The algorithm determines the target active level reclevel, extracts the primary resolution yconf by XORing the corresponding shares, prunes the evaluated suffix vectors, and reduces the operation into a (t−2) sub-problem. (If t−2=1, it directly extracts the scalar bit; otherwise, it resolves recursively).–Conflict Party Substitution: If conflict∉Ind, it implies the conflict party is absent and its role must be delegated. The algorithm performs a response substitution: the highest-index active server Prec[t] is replaced by its conflict party Psub[conflict]. The active set is then re-sorted, and the index mapping Ind is synchronized to continue the iterative traversal towards the base subset.
Iterative Traversal and Conflict Resolution (t>2): The algorithm first maps each element in the surviving set to its relative 1-based index array Ind within the current participating subset Psub. It then iteratively traverses the sharing topology via a deterministic loop:
–Base t-party Subset: If the maximum current index satisfies Ind[t]=t, the foundational base subset is reached. The target bit is recovered directly by XOR-accumulating the first elements of the evaluation shares from these initial t servers.
Base t-party Subset: If the maximum current index satisfies Ind[t]=t, the foundational base subset is reached. The target bit is recovered directly by XOR-accumulating the first elements of the evaluation shares from these initial t servers.
–Direct Conflict Resolution: It computes the conflict index conflict=Ind[t]−t. If conflict∈Ind, a direct structural conflict is identified. The algorithm determines the target active level reclevel, extracts the primary resolution yconf by XORing the corresponding shares, prunes the evaluated suffix vectors, and reduces the operation into a (t−2) sub-problem. (If t−2=1, it directly extracts the scalar bit; otherwise, it resolves recursively).
Direct Conflict Resolution: It computes the conflict index conflict=Ind[t]−t. If conflict∈Ind, a direct structural conflict is identified. The algorithm determines the target active level reclevel, extracts the primary resolution yconf by XORing the corresponding shares, prunes the evaluated suffix vectors, and reduces the operation into a (t−2) sub-problem. (If t−2=1, it directly extracts the scalar bit; otherwise, it resolves recursively).
–Conflict Party Substitution: If conflict∉Ind, it implies the conflict party is absent and its role must be delegated. The algorithm performs a response substitution: the highest-index active server Prec[t] is replaced by its conflict party Psub[conflict]. The active set is then re-sorted, and the index mapping Ind is synchronized to continue the iterative traversal towards the base subset.
Conflict Party Substitution: If conflict∉Ind, it implies the conflict party is absent and its role must be delegated. The algorithm performs a response substitution: the highest-index active server Prec[t] is replaced by its conflict party Psub[conflict]. The active set is then re-sorted, and the index mapping Ind is synchronized to continue the iterative traversal towards the base subset.
5. The Proposed Fault-Tolerant PIR Scheme
Building upon the generalized (t,p)-threshold DPF constructed in Section 4, we now formalize our robust PIR scheme. The protocol proceeds in three standard phases: Query, Evaluation, and Reconstruction, as detailed in Algorithm 5 and visually summarized in Figure 9. Let the database be modeled as an array of N records DB=(DB[1],…,DB[N]), where each record DB[i] is treated as an integer value. Algorithm 5 Fault-Tolerant PIR Based on Generalized (t,p)-Threshold DPFNotation: We utilize the generalized DPF algorithms DPF.{Inittofp,Sharetofp,Evaltofp,Rectofp} established in Algorithms 3 and 4. Fmaxlevel(t,p) is the maximum sharing level function defined in Equation (4). The database contains N records, formulated as DB=(DB[1],…,DB[N]). Input: Client’s target index α∈[N].Output: The retrieved record DB[α]. PIR.Query(t,p,1λ,N,α): 1:Let Psub←[p]. ▹ Initialize the reference subset to include all p servers. 2:Generate base keys: V←Inittofp(t,p,1λ,fα,1). 3:Distribute via recursive patching: (K1,…,Kp)←Sharetofp(t,p,V,Psub). 4:return query sets (K1,…,Kp) to servers 1,…,p, respectively.PIR.Eval(j,Kj,DB): 1:Initialize RESj←0. ▹ Allocate a zero vector of dimension Fmaxlevel(t,p). 2:for i=1 to N do 3: Extract share vector for the current index: Yj(i)←Evaltofp(j,Kj,i). 4: Accumulate response: RESj←RESj⊕Yj(i)·DB[i]. ▹ Scalar-vector multiplication with integer DB[i]. 5:end for 6:return RESj.PIR.Rec(t,p,Prec,Psub,{RESi}i∈Prec): 1:Execute iterative reconstruction: y←Rectofp(t,p,Prec,Psub,{RESi}i∈Prec). 2:return y. ▹ Successfully recover y=DB[α].
Notation: We utilize the generalized DPF algorithms DPF.{Inittofp,Sharetofp,Evaltofp,Rectofp} established in Algorithms 3 and 4. Fmaxlevel(t,p) is the maximum sharing level function defined in Equation (4). The database contains N records, formulated as DB=(DB[1],…,DB[N]).
Notation: We utilize the generalized DPF algorithms DPF.{Inittofp,Sharetofp,Evaltofp,Rectofp} established in Algorithms 3 and 4. Fmaxlevel(t,p) is the maximum sharing level function defined in Equation (4). The database contains N records, formulated as DB=(DB[1],…,DB[N]).
Input: Client’s target index α∈[N].
Input: Client’s target index α∈[N].
Output: The retrieved record DB[α].
Output: The retrieved record DB[α].
PIR.Query(t,p,1λ,N,α):
PIR.Query(t,p,1λ,N,α):
1:Let Psub←[p]. ▹ Initialize the reference subset to include all p servers.
Let Psub←[p]. ▹ Initialize the reference subset to include all p servers.
2:Generate base keys: V←Inittofp(t,p,1λ,fα,1).
Generate base keys: V←Inittofp(t,p,1λ,fα,1).
3:Distribute via recursive patching: (K1,…,Kp)←Sharetofp(t,p,V,Psub).
Distribute via recursive patching: (K1,…,Kp)←Sharetofp(t,p,V,Psub).
4:return query sets (K1,…,Kp) to servers 1,…,p, respectively.
return query sets (K1,…,Kp) to servers 1,…,p, respectively.
PIR.Eval(j,Kj,DB):
PIR.Eval(j,Kj,DB):
1:Initialize RESj←0. ▹ Allocate a zero vector of dimension Fmaxlevel(t,p).
Initialize RESj←0. ▹ Allocate a zero vector of dimension Fmaxlevel(t,p).
2:for i=1 to N do
for i=1 to N do
3: Extract share vector for the current index: Yj(i)←Evaltofp(j,Kj,i).
Extract share vector for the current index: Yj(i)←Evaltofp(j,Kj,i).
4: Accumulate response: RESj←RESj⊕Yj(i)·DB[i]. ▹ Scalar-vector multiplication with integer DB[i].
Accumulate response: RESj←RESj⊕Yj(i)·DB[i]. ▹ Scalar-vector multiplication with integer DB[i].
5:end for
end for
6:return RESj.
return RESj.
PIR.Rec(t,p,Prec,Psub,{RESi}i∈Prec):
PIR.Rec(t,p,Prec,Psub,{RESi}i∈Prec):
1:Execute iterative reconstruction: y←Rectofp(t,p,Prec,Psub,{RESi}i∈Prec).
Execute iterative reconstruction: y←Rectofp(t,p,Prec,Psub,{RESi}i∈Prec).
2:return y. ▹ Successfully recover y=DB[α].
return y. ▹ Successfully recover y=DB[α].
5.1. Protocol Description
(1)Query Generation (PIR.Query). To privately retrieve the target record without revealing its index α to the servers, the client executes a PIR request. Specifically, the client initializes the reference subset Psub←[p] and encapsulates α into a set of cryptographic query keys via the (t,p)-DPF base generation algorithm. It then distributes the query shares (K1,…,Kp) to the respective servers. The communication cost in this phase is precisely bounded by the key expansion of the (t,p)-DPF.
Query Generation (PIR.Query). To privately retrieve the target record without revealing its index α to the servers, the client executes a PIR request. Specifically, the client initializes the reference subset Psub←[p] and encapsulates α into a set of cryptographic query keys via the (t,p)-DPF base generation algorithm. It then distributes the query shares (K1,…,Kp) to the respective servers. The communication cost in this phase is precisely bounded by the key expansion of the (t,p)-DPF.
(2)Server Evaluation (PIR.Eval). Upon receiving the query share Kj, server j expands it into a local secret-shared indicator vector. The server then evaluates the query by computing the inner product between this indicator vector and the database DB. Specifically, this inner product is realized by computing the scalar multiplication of the generated Boolean share vector Yj(i)∈{0,1}Fmaxlevel(t,p) with each integer record DB[i], and accumulating the results via bitwise XOR to form the final response vector RESj.
Server Evaluation (PIR.Eval). Upon receiving the query share Kj, server j expands it into a local secret-shared indicator vector. The server then evaluates the query by computing the inner product between this indicator vector and the database DB. Specifically, this inner product is realized by computing the scalar multiplication of the generated Boolean share vector Yj(i)∈{0,1}Fmaxlevel(t,p) with each integer record DB[i], and accumulating the results via bitwise XOR to form the final response vector RESj.
(3)Fault-Tolerant Reconstruction (PIR.Rec). Suppose the client only receives responses from a surviving subset of servers Prec where |Prec|=t. The client executes the iterative reconstruction algorithm over the received response vectors {RESi}i∈Prec. Through the deterministic substitution of conflict parties, the client circumvents the missing servers and extracts the target record DB[α].
Fault-Tolerant Reconstruction (PIR.Rec). Suppose the client only receives responses from a surviving subset of servers Prec where |Prec|=t. The client executes the iterative reconstruction algorithm over the received response vectors {RESi}i∈Prec. Through the deterministic substitution of conflict parties, the client circumvents the missing servers and extracts the target record DB[α].
5.2. Correctness via Linear Homomorphism
The correctness of the retrieval relies on the XOR linear homomorphism of our reconstruction algorithm Rectofp. Because the reconstruction function consists solely of linear XOR operations, it commutatively penetrates the summation performed by the servers. The client’s reconstruction can be expressed as:(5)y=Rectofp(t,p,Prec,Psub,{RESj}j∈Prec)=Rectofp(t,p,Prec,Psub,{⨁i=1N(Yj(i)·DB[i])}j∈Prec)=⨁i=1N[Rectofp(t,p,Prec,Psub,{Yj(i)}j∈Prec)]·DB[i]. By the correctness of the underlying (t,p)-DPF, the evaluation Rectofp yields the scalar 1 if and only if i=α, and 0 otherwise. Consequently, all non-target integer records are entirely canceled out, collapsing the equation exclusively to the desired term y=1·DB[α]=DB[α].
6. Security and Availability Analysis
In this section, we rigorously formalize our composite security paradigm and present the theoretical proofs demonstrating the privacy and high availability of the proposed (t,p)-FT-PIR scheme.
6.1. Security Paradigm and Assumptions
Recall the threat model formulated in Section 3.2; our architecture integrates diverse cryptographic primitives, yielding a composite security paradigm bound by the weakest link principle:The optimized RSS provides perfect (information-theoretic) security [22,27].The Randomized Special Combinatorial Design guarantees statistical security [20]. Specifically, for any unauthorized coalition of up to t−1 servers, the probability distributions of the seed assignments derived from G0 and G1 are statistically indistinguishable. We directly inherit the formal definitions and rigorous proofs of this statistical proximity from [20].The core DPF key expansion relies on Pseudorandom Generators (PRGs), inherently offering computational security [19].
The optimized RSS provides perfect (information-theoretic) security [22,27].
The optimized RSS provides perfect (information-theoretic) security [22,27].
The Randomized Special Combinatorial Design guarantees statistical security [20]. Specifically, for any unauthorized coalition of up to t−1 servers, the probability distributions of the seed assignments derived from G0 and G1 are statistically indistinguishable. We directly inherit the formal definitions and rigorous proofs of this statistical proximity from [20].
The Randomized Special Combinatorial Design guarantees statistical security [20]. Specifically, for any unauthorized coalition of up to t−1 servers, the probability distributions of the seed assignments derived from G0 and G1 are statistically indistinguishable. We directly inherit the formal definitions and rigorous proofs of this statistical proximity from [20].
The core DPF key expansion relies on Pseudorandom Generators (PRGs), inherently offering computational security [19].
The core DPF key expansion relies on Pseudorandom Generators (PRGs), inherently offering computational security [19].
Consequently, the overall protocol achieves computational security bounded by the underlying PRG against PPT adversaries. Furthermore, our scheme operates in the plain model, requiring no trusted setup or hybrid public-key infrastructure. We adopt a standard simulation-based proof framework [28] to demonstrate that the joint view of any unauthorized coalition can be perfectly simulated without any knowledge of the target index α.
6.2. Formal Privacy Proof
Given the established paradigm, we formally define the privacy requirement and provide the theoretical proof.
Let λ be the security parameter and N be the database size. A (t,p)-FT-PIR protocol achieves (t−1)-computational query privacy if, for any target index α∈[N] and any unauthorized coalition of servers I⊂[p] bounded by |I|