Capacity-achieving private information retrieval scheme with a smaller sub-packetization

Wenqin Zhang, Zhengchun Zhou, Udaya Parampalli, Vladimir Sidorenko, Sihem Mesnager

Research output: Contribution to journalArticlepeer-review

Abstract

Private information retrieval (PIR) allows a user to retrieve one out of M messages from N servers without revealing the identity of the desired message. Every message consists of L symbols (packets) from an additive group and the length L is called the sub-packetization. A PIR scheme with download cost (DC) D=L is implemented by querying D sums of the symbols to servers. We assume that each uncoded server can store up to tLM=N symbols, t ε {1, 2,…, N). The minimum DC of storage constrained PIR was determined by Attia et al. in 2018 to be DCmin = 1 + 1=t + 1=t2 +… + 1=tM-1. The capacity of storage constrained PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired symbols that can be privately retrieved per bit of downloaded symbols. Tandon et al. designed a capacity-achieving PIR scheme with sub-packetization L’ = (Nt)tM of each message. In this paper, we design a PIR scheme with t times smaller sub- packetization L’/t and with the minimum DC for any parameters N,M,t. We also prove that tM-1 is a factor of sub-packetization L for any capacity- achieving PIR scheme from storage constrained servers.

Original languageEnglish
Pages (from-to)347-363
Number of pages17
JournalAdvances in Mathematics of Communications
Volume15
Issue number2
DOIs
Publication statusPublished - 2021
Externally publishedYes

Keywords

  • Minimum download cost
  • Private information retrieval
  • Storage constrained servers
  • Sub-packetization

Fingerprint

Dive into the research topics of 'Capacity-achieving private information retrieval scheme with a smaller sub-packetization'. Together they form a unique fingerprint.

Cite this