This work proposes a fault-tolerant PIR protocol based on a newly designed (t,p)-threshold distributed point function (FT-DPF), and proves that the stateless protocol guarantees (t−1)-computational privacy under the semi-honest model.
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.
Leveraging TFSS, ThORY achieves leakage-free keyword search and document identifier retrieval under a (t,p)-threshold model, hiding access, search, and volume patterns against any adversary corrupting fewer than t servers.
C. Kumar, Sikhar Patranabis, Debdeep Mukhopadhyay· IACR Communications in Crypt...· 0 citations
SVIiT is described as communication-reduced relative to the evaluated MPC baselines rather than universally lightweight, and its present practical scope is primarily high-bandwidth LAN or provider-edge deployments.
Tingting Chen· ICST Transactions on Scalabl...· 0 citations
A novel VMKSE scheme (VMKSE-BFF) is presented by adopting BFF, which can simultaneously support verifiability of and secure data sharing in a multi-user setting and a comparison with the existing VMKSE schemes is provided.
Yandong Su, Bing-Hang Wang, Yan-Jie Xiang et al.· Mathematics· 0 citations
Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients is presented, and is shown to be highly efficient and scalable.
Dimitris Mouris, Lucas Piske, Pratik Sarkar et al.· IACR Cryptology ePrint Archi...· 0 citations
It is proved that TriVer satisfies client data privacy, aggregation correctness, and aggregation-result non-forgeability in the Random Oracle Model under ECDLP hardness, HPRF pseudorandomness, and hash collision resistance, against a fully malicious server that may collude with a subset of aggregators and clients.
Guang-Ye Zhu, Liqiang Wu, Weidong Du· Journal of King Saud Univers...· 0 citations
Currently, existing group signature schemes with user-controlled and sequential linkability (GS-UCSL) suffer from critical limitations: they lack post-quantum security, cannot efficiently revoke malicious signers, grant excessive tracing power to group managers (GM), and rely on heavy revocation lists or secure channels that incur high computation or communication overhead. To address these issues, we propose an efficient lattice-based conditional privacy-preserving GS-UCSL (LCGS-UCSL). Our scheme is built on lattice cryptography to achieve post-quantum security, and unifies implicit linkability, explicit linkability, and sequential linkability under user autonomous control. We design a polynomial-based revocation mechanism that eliminates revocation list verification and secure-channel token updates, enabling lightweight and privacy-preserving member revocation. To curb GM’s overreach, we introduce key-oblivious encryption to split users into traceable and non-traceable types without their awareness, and use cuckoo hashing to realize O(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1)$$\end{document} registry operations. We further integrate signature aggregation and non-interactive zero-knowledge proofs of knowledge to optimize batch verification and reduce communication overhead. We formally prove the scheme’s anonymity, traceability, Existential Unforgeability under Chosen-Message Attack, and non-frameability in the random oracle model, and validate its practicality via performance analysis. The results show that LCGS-UCSL achieves comprehensive functionality with competitive efficiency, filling the gap toward post-quantum secure GS-UCSL with efficient revocation and balanced privacy.
