Towards Practical Private Information Retrieval from MDS Array Codes

Jie Li*, David Karpuk, Camilla Hollanti

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Private information retrieval (PIR) is the problem of privately retrieving one out of M original files from N severs, i.e., each individual server gains no information on the identity of the file that the user is requesting. Usually, the M files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the N servers. Compared to mere replication, MDS-coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR protocols from MSR-coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR-coded servers as a special case. Particularly, only the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS-/MSR-coded servers. By choosing different MDS array codes, the new PIR protocol can have varying advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-)optimal repair bandwidth, 3) implementable over the binary field mathbf {F}-{2}.

Original languageEnglish
Article number9037091
Pages (from-to)3415-3425
Number of pages11
JournalIEEE Transactions on Communications
Volume68
Issue number6
DOIs
Publication statusPublished - Jun 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • Capacity
  • MDS array codes
  • private information retrieval (PIR)
  • repair bandwidth
  • sub-packetization

Fingerprint Dive into the research topics of 'Towards Practical Private Information Retrieval from MDS Array Codes'. Together they form a unique fingerprint.

Cite this