t-Private Information Retrieval Schemes Using Transitive Codes

R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, A. Horlemann-Trautmann, D. Karpuk, I. Kubjas

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)

Abstract

Private information retrieval (PIR) schemes for coded storage with colluding servers are presented, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. In the special case of no server collusion, this rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems. While many PIR schemes in the literature require ?eld sizes that grow with the number of servers and ?les in the system, we focus especially on the case of a binary base ?eld, for which Reed-Muller codes serve as an important and explicit class of examples.
Original languageEnglish
Pages (from-to)2107-2118
JournalIEEE Transactions on Information Theory
Volume65
Issue number4
Early online date2018
DOIs
Publication statusPublished - Apr 2019
MoE publication typeA1 Journal article-refereed

Keywords

  • Servers
  • Information retrieval
  • Linear codes
  • Electronic mail
  • Indexes
  • Private Information Retrieval
  • transitive codes
  • Reed-Muller codes

Fingerprint Dive into the research topics of 't-Private Information Retrieval Schemes Using Transitive Codes'. Together they form a unique fingerprint.

Cite this