The Capacity of Private Information Retrieval

Abstract

In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of $K$ messages from $N$ non-communicating databases (each holds all $K$ messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For $K$ messages and $N$ databases, we show that the PIR capacity is $(1+1/N+1/N^2+\cdots +1/N^{K-1}{)}^{-1}$. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.

References in corpus (1)

• Blind Interference Alignment for Private Information Retrieval

Cited by in corpus (11)

• Private Information Retrieval from Coded Databases with Colluding Servers
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• Directed Information as Privacy Measure in Cloud-based Control
• Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length
• The Capacity of Private Information Retrieval with Private Side Information Under Storage Constraints
• Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
• Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding