Private Information Retrieval from Coded Databases with Colluding Servers

Ragnar Freij-Hollanti, Oliver Gnilke, Camilla Hollanti, David Karpuk

Research output: Contribution to journalArticleScientificpeer-review

88 Citations (Scopus)
143 Downloads (Pure)

Abstract

We present a general framework for private information retrieval (PIR) from arbitrary coded databases that allows one to adjust the rate of the scheme to the suspected number of colluding servers. If the storage code is a generalized Reed--Solomon code of length $n$ and dimension $k$, we design PIR schemes that achieve a PIR rate of $\frac{n-(k+t-1)}{n}$ while protecting against any $t$ colluding servers, for any $1\leq t\leq n-k$. This interpolates between the previously studied cases of $t=1$ and $k=1$ and achieves PIR capacity in both of these cases asymptotically as the number of files in the database grows.

Original languageEnglish
Pages (from-to)647–664
Number of pages18
JournalSIAM Journal on Applied Algebra and Geometry
Volume1
Issue number1
DOIs
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • private information retrieval
  • distributed storage systems
  • generalized Reed--Solomon codes

Fingerprint Dive into the research topics of 'Private Information Retrieval from Coded Databases with Colluding Servers'. Together they form a unique fingerprint.

Cite this