Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 55 min ago
PreprintarXiv licencearXiv

The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers

  • Rui Sun
  • Yiwei Zhang
Open at sourcePDFDOICite

Abstract

We consider the problem of private information retrieval from MDS-coded databases with T colluding servers, U robust servers, and B Byzantine servers, referred to as U-B-MDS-TPIR. In the U-B-MDS-TPIR setting, M files are stored across N servers, and in this paper each file is independently encoded using an (N,K) GRS code. We characterize the capacity among linear, full support-rank U-B-MDS-TPIR schemes as C=(N−U−2B)/(N−U)(1+(K+T−1)/(N−U−2B)+⋯+((K+T−1)/(N−U−2B))M−1)−1 when N−U−2B≥ KT. When K=1 or T=1, the same expression gives the capacity without the linearity and full support-rank restrictions. We further extend the construction to the retrieval of P out of M files. For P ≥ M/2, the resulting multi-file scheme achieves capacity when K=1 or T=1.

Related

  1. Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
    Mohamed Nomeir, Shreya Meel, Sennur Ulukus
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Weak Private Information Retrieval for Graph-based Storage under ε-privacy
    Jayesh Seshadri, Prasad Krishnan
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Quantum Private Information Retrieval on Forests
    Mohamed Nomeir, Sennur Ulukus
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv
  4. Local Private Information Retrieval for Graph-Based Replicated Systems
    Shreya Meel, Mohamed Nomeir, Sennur Ulukus
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Communication with Adversarial Users: Byzantine Models in Multi-User Information Theory
    Minglai Cai, Christian Deppe, Neha Sangwan
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{sun2026capacity,
  title = {{The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers}},
  author = {Rui Sun and Yiwei Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37412},
  eprint = {2610.37412},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37412},
}
RIS
TY  - UNPB
TI  - The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
AU  - Rui Sun
AU  - Yiwei Zhang
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.37412
UR  - https://arxiv.org/abs/2610.37412
AB  - We consider the problem of private information retrieval from MDS-coded databases with T colluding servers, U robust servers, and B Byzantine servers, referred to as U-B-MDS-TPIR. In the U-B-MDS-TPIR setting, M files are stored across N servers, and in this paper each file is independently encoded using an (N,K) GRS code. We characterize the capacity among linear, full support-rank U-B-MDS-TPIR schemes as C=(N−U−2B)/(N−U)(1+(K+T−1)/(N−U−2B)+⋯+((K+T−1)/(N−U−2B))^M−1)^−1 when N−U−2B≥ KT. When K=1 or T=1, the same expression gives the capacity without the linearity and full support-rank restrictions. We further extend the construction to the retrieval of P out of M files. For P ≥ M/2, the resulting multi-file scheme achieves capacity when K=1 or T=1.
ER  -