{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T15:29:11Z","timestamp":1787585351897,"version":"build-2736575974"},"reference-count":31,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T00:00:00Z","timestamp":1787443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\u22121)-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.<\/jats:p>","DOI":"10.3390\/e28090945","type":"journal-article","created":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T14:49:34Z","timestamp":1787582974000},"page":"945","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fault-Tolerant Private Information Retrieval via Threshold Distributed Point Functions"],"prefix":"10.3390","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-4906-2103","authenticated-orcid":false,"given":"Dazeng","family":"Yuan","sequence":"first","affiliation":[{"name":"Department of Basic Medicine, Dazhou Vocational College of Chinese Medicine, Dazhou 635000, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0136-8301","authenticated-orcid":false,"given":"Xiheng","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610032, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2949-832X","authenticated-orcid":false,"given":"Bin","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610032, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,8,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/293347.293350","article-title":"Private information retrieval","volume":"45","author":"Chor","year":"1998","journal-title":"J. ACM (JACM)"},{"key":"ref_2","first-page":"159","article-title":"PIR-PSI: Scaling Private Contact Discovery","volume":"4","author":"Demmler","year":"2018","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., and Zeldovich, N. (2023, January 23\u201326). Private web search with tiptoe. Proceedings of the 29th Symposium on Operating Systems Principles, Koblenz, Germany.","DOI":"10.1145\/3600006.3613134"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs, H., Boneh, D., and Mazi\u00e8res, D. (2015). Riposte: An anonymous messaging system handling millions of users. Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP), IEEE.","DOI":"10.1109\/SP.2015.27"},{"key":"ref_5","unstructured":"Dauterman, E., Feng, E., Luo, E., Popa, R.A., and Stoica, I. (2020, January 4\u20136). DORY: An encrypted search system with distributed trust. Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), Virtual Event."},{"key":"ref_6","unstructured":"Menon, S.J., and Wu, D.J. (2024, January 14\u201316). YPIR: High-Throughput Single-Server PIR with silent preprocessing. Proceedings of the 33rd USENIX Security Symposium (USENIX Security 24), Philadelphia, PA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Fisch, B., Lazzaretti, A., Liu, Z., and Papamanthou, C. (2024, January 14\u201318). ThorPIR: Single server PIR via homomorphic thorp shuffles. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, Salt Lake City, UT, USA.","DOI":"10.1145\/3658644.3690326"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Lin, W.K., Mook, E., and Wichs, D. (2023, January 20\u201323). Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA.","DOI":"10.1145\/3564246.3585175"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Shi, E., Aqeel, W., Chandrasekaran, B., and Maggs, B. (2021). Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. Proceedings of the Annual International Cryptology Conference, Springer.","DOI":"10.1007\/978-3-030-84259-8_22"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zhou, M., Park, A., Zheng, W., and Shi, E. (2024). Piano: Extremely simple, single-server PIR with sublinear server computation. Proceedings of the 2024 IEEE Symposium on Security and Privacy (SP), IEEE.","DOI":"10.1109\/SP54263.2024.00055"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ghoshal, A., Zhou, M., and Shi, E. (2024). Efficient pre-processing PIR without public-key cryptography. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-031-58751-1_8"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Wang, Z., and Ren, L. (2025). Single-server client preprocessing PIR with tight space-time trade-off. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-031-91095-1_4"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Eriguchi, R., and Nuida, K. (2025). A Survey on Private Information Retrieval: Information-Theoretic Constructions and Error-Correction Techniques. Mathematical Foundations for Post-Quantum Cryptography: Crypto-Math CREST, Springer.","DOI":"10.1007\/978-981-96-1218-5_24"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Woodruff, D., and Yekhanin, S. (2005). A geometric approach to information-theoretic private information retrieval. Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC\u201905), IEEE.","DOI":"10.1109\/CCC.2005.2"},{"key":"ref_15","unstructured":"Devet, C., Goldberg, I., and Heninger, N. (2012, January 8\u201310). Optimally robust private information retrieval. Proceedings of the 21st USENIX Security Symposium (USENIX Security 12), Bellevue, WA, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2968443","article-title":"2-server PIR with subpolynomial communication","volume":"63","author":"Dvir","year":"2016","journal-title":"J. ACM (JACM)"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Lazzaretti, A., Liu, Z., Fisch, B., Miao, P., and Papamanthou, C. (2025). Multi-server Doubly Efficient PIR in the Classical Model and Beyond. Proceedings of the Theory of Cryptography Conference, Springer.","DOI":"10.1007\/978-3-032-12290-2_20"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Boyle, E., Gilboa, N., and Ishai, Y. (2015). Function secret sharing. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-662-46803-6_12"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Boyle, E., Gilboa, N., and Ishai, Y. (2016, January 24\u201328). Function secret sharing: Improvements and extensions. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978429"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Goel, A., Wang, M., and Wang, Z. (2025). Multiparty Distributed Point Functions. Proceedings of the Annual International Cryptology Conference, Springer.","DOI":"10.1007\/978-3-032-01884-7_5"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Park, A., Leong, T., Maturana, F., Zheng, W., and Rashmi, K. (2024). Communication-efficient, fault tolerant PIR over erasure coded storage. Proceedings of the 2024 IEEE Symposium on Security and Privacy (SP), IEEE.","DOI":"10.1109\/SP54263.2024.00168"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Guo, J., Shuai, M., Wang, Q., Li, W., and Lin, J. (2022). Replicated additive secret sharing with the optimized number of shares. Proceedings of the International Conference on Security and Privacy in Communication Systems, Springer.","DOI":"10.1007\/978-3-031-25538-0_20"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1462","DOI":"10.1109\/TBDATA.2026.3689015","article-title":"Constant-Round Privacy-Preserving KNN Classification Based on Function Secret Sharing","volume":"12","author":"Liu","year":"2026","journal-title":"IEEE Trans. Big Data"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"11279","DOI":"10.1109\/TIFS.2025.3622066","article-title":"MSecKNN: Maliciously Secure Outsourced KNN Classification Under Multiple Distance Metrics","volume":"20","author":"Li","year":"2025","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2551","DOI":"10.1109\/TDSC.2025.3628356","article-title":"SecOIR: Enhancing Privacy and Accuracy in Outsourced Image Retrieval via Function Secret Sharing and Deep Hashing","volume":"23","author":"Li","year":"2026","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1109\/TIFS.2023.3337940","article-title":"SecKNN: FSS-based secure multi-party KNN classification under general distance functions","volume":"19","author":"Li","year":"2023","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_27","first-page":"56","article-title":"Secret sharing scheme realizing general access structure","volume":"72","author":"Ito","year":"1989","journal-title":"Electron. Commun. Jpn. (Part III Fundam. Electron. Sci.)"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Lindell, Y. (2017). How to Simulate It - A Tutorial on the Simulation Proof Technique. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, Springer.","DOI":"10.1007\/978-3-319-57048-8"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1145\/98163.98167","article-title":"Implementing fault-tolerant services using the state machine approach: A tutorial","volume":"22","author":"Schneider","year":"1990","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Beimel, A., and Stahl, Y. (2002). Robust information-theoretic private information retrieval. Proceedings of the International Conference on Security in Communication Networks, Springer.","DOI":"10.1007\/3-540-36413-7_24"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Francati, D., and Venturi, D. (2024). Evolving secret sharing made short. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Springer.","DOI":"10.1007\/978-981-96-0941-3_3"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/9\/945\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T14:53:19Z","timestamp":1787583199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/9\/945"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,23]]},"references-count":31,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2026,9]]}},"alternative-id":["e28090945"],"URL":"https:\/\/doi.org\/10.3390\/e28090945","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,23]]}}}