Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

Razane Tajeddine, Oliver W. Gnilke, David Karpuk, Ragnar Freij-Hollanti, Camilla Hollanti

Research output: Contribution to journalJournal articleResearchpeer-review

42 Citations (Scopus)

Abstract

The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n,k] Reed-Solomon storage code is designed, protecting against t-collusion, and handling up to b Byzantine and r unresponsive servers, when n>k+t+2b+r-1. This scheme achieves a PIR rate of ((n-r-(k+2b+t-1))/n-r). In the case where the capacity is known, namely, when k=1, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.

Original languageEnglish
Article number8598994
JournalIEEE Transactions on Information Theory
Volume65
Issue number6
Pages (from-to)3898-3906
Number of pages9
ISSN0018-9448
DOIs
Publication statusPublished - Jun 2019

Keywords

  • Byzantine
  • information retrieval
  • Privacy
  • Reed-Solomon codes
  • reliability
  • robustness
  • servers

Fingerprint

Dive into the research topics of 'Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers'. Together they form a unique fingerprint.

Cite this