Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost

Abstract

We propose a new capacity-achieving code for the private information retrieval (PIR) problem, and show that it has the minimum message size (being one less than the number of servers) and the minimum upload cost (being roughly linear in the number of messages) among a general class of capacity-achieving codes, and in particular, among all capacity-achieving linear codes. Different from existing code constructions, the proposed code is asymmetric, and this asymmetry appears to be the key factor leading to the optimal message size and the optimal upload cost. The converse results on the message size and the upload cost are obtained by a strategic analysis of the information theoretic proof of the PIR capacity, from which a set of critical properties of any capacity-achieving code in the code class of interest is extracted. The symmetry structure of the PIR problem is then analyzed, which allows us to construct symmetric codes from asymmetric ones, yielding a meaningful bridge between the proposed code and existing ones in the literature.

Revised with more examples to improve the readability

References in corpus (6)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Symmetry, Outer Bounds, and Code Constructions: A Computer-Aided Investigation on the Fundamental Limits of Caching
• An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level, Small Field Size and All-Node Repair
• On private information retrieval array codes
• Linear Network Coding over Rings, Part I: Scalar Codes and Commutative Alphabets
• Coded Caching with Low Subpacketization Levels

Cited by in corpus (5)

• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• On the Storage Cost of Private Information Retrieval
• On the Capacity of Locally Decodable Codes
• The Capacity of Multi-round Private Information Retrieval from Byzantine Databases
• A New Design of Private Information Retrieval for Storage Constrained Databases