Fault-Tolerant Private Information Retrieval via Threshold Distributed Point Functions

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.