Lower Bound on the Redundancy of PIR Codes

Abstract

We prove that the redundancy of a $k$-server PIR code of dimension $s$ is $\Omega (\sqrt{s})$ for all $k\ge 3$. This coincides with a known upper bound of $O(\sqrt{s})$ on the redundancy of PIR codes. Moreover, for $k=3$ and $k=4$, we determine the lowest possible redundancy of $k$-server PIR codes exactly. Similar results were proved independently by Mary Wootters using a different method.

References in corpus (1)

• PIR with Low Storage Overhead: Coding instead of Replication

Cited by in corpus (11)

• A general private information retrieval scheme for MDS coded databases with colluding servers
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Lengthening and Extending Binary Private Information Retrieval Codes
• Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length
• Binary, Shortened Projective Reed Muller Codes for Coded Private Information Retrieval
• PIR Codes with Short Block Length
• On the Storage Cost of Private Information Retrieval
• Locality and Availability of Array Codes Constructed from Subspaces
• Capacity-Achieving Private Information Retrieval Schemes from Uncoded Storage Constrained Servers with Low Sub-packetization
• Visible Rank and Codes with Locality
• Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding