The Capacity of Private Information Retrieval

Hua Sun; Syed A. Jafar

Source-linked AI summary

The Capacity of Private Information Retrieval

Hua Sun, Syed A. Jafar

arXiv:1602.09134v2Feb 29, 2016cs.ITcs.CRcs.IR

TL;DR

PIR asks how to retrieve one of K replicated messages efficiently while revealing nothing about its index to any individual database. The paper characterizes the exact information-theoretic capacity and presents a scheme achieving it. The capacity is (1 + 1/N + 1/N^2 + · · · + 1/N^(K−1))^-1, with the scheme retaining capacity for a remaining subset when other messages are set to zero.

Problem
PIR seeks efficient retrieval of one replicated message while revealing no information about the requested index to any individual database.
Method
The paper combines a capacity-achieving PIR scheme with an information-theoretic converse and uses query structures with random mappings of message bits.
Results
The exact capacity for K messages and N databases is (1 + 1/N + 1/N^2 + · · · + 1/N^(K−1))^-1, strictly higher than the previously best known achievable rate 1 − 1/N.
Takeaways & Limitations
Setting any subset of messages to zero leaves a scheme that achieves the PIR capacity for the remaining messages.
Takeaways & Limitations
For arbitrary finite message sizes, the naive zero-padding extension can be sub-optimal, and the optimal limited-size rate remains open in general.

Abstract

from arXiv · show

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.

1 Introduction

PIR asks how to retrieve one message from replicated databases without revealing its index, while minimizing download cost. This work determines the exact capacity for arbitrary numbers of messages and databases.

Problem setting: PIR retrieves one desired message from databases storing all messages while hiding the desired index from each individual database.The user sends queries and receives answering strings from non-communicating databases.
Connections: PIR connects to oblivious transfer, multiparty computation, secret sharing, locally decodable codes, distributed storage repair, index coding, and network coding.The paper presents capacity characterization as a step toward connecting these complementary perspectives.
Illustrative scheme: For two databases, random binary query vectors yield answers whose difference recovers the desired message while each query remains independent of its index.Each database sees an identically distributed query regardless of which message is requested.
Efficiency criterion: The rate is desired information per downloaded information bit, with upload cost negligible in the Shannon-theoretic formulation.For the example, one message bit requires downloading two bits, giving rate 1/2.
Research objective: The paper seeks the exact information-theoretic capacity for arbitrary K messages and N databases, improving on the previously known rate 1 − 1/N.Earlier bounds were a reasonable approximation for large numbers of databases but were not exact.

2 Problem Statement

The problem statement formalizes PIR with K independent messages replicated at N databases, requiring reliable recovery of the requested message and information-theoretic privacy. Capacity is defined through download rate under asymptotically large message size.

Model: K independent messages of L bits each are stored in full at each of N non-communicating databases.The user privately selects an index θ and seeks Wθ.
Protocol: For requested message Wk, the user sends query Q[k]n to database n, which returns an answer A[k]n determined by the query and stored data.The user must decode Wk from all available queries, answers, and stored messages with vanishing error probability.
Assumptions: Queries are independent of message realizations, while message independence is expressed by H(W1, · · ·, WK) = H(W1) + · · · + H(WK).The message-independence condition is used in the formal converse.
Privacy: Privacy requires the K retrieval strategies to be identically distributed from every database’s perspective.This means each database learns nothing about the requested index.
Rate and capacity: The PIR rate counts desired bits per downloaded bit, and privacy forces the expected download from each database to be the same across requested messages.The total download D is averaged over random queries.
Reliability: ε-error capacity permits error probability tending to zero as L grows, whereas zero-error capacity requires Pe = 0.Zero-error capacity is the stronger, more constrained notion.

3 Main Result: Capacity of Private Information Retrieval

The paper characterizes PIR capacity exactly as a finite geometric-sum expression and establishes it with matching achievability and converse arguments. The result also describes how capacity changes with message and database counts and how finite message lengths affect implementation.

Optimality: The paper establishes the result through a capacity-achieving scheme and an information-theoretic converse that rules out higher rates.The converse applies when Pe → 0 as message size L → ∞.
Theorem 1: The capacity for K messages and N databases is (1 + 1/N + 1/N^2 + · · · + 1/N^(K−1))^-1.Theorem 1 gives the exact information-theoretic capacity.
Comparison: The capacity is strictly higher than the previously best known achievable rate 1 − 1/N.For N > 1, the expression can also be written in an equivalent geometric form.
Dependence on K: Capacity decreases strictly with K and approaches 1 − 1/N as K approaches infinity.Thus, increasing the number of messages lowers the capacity toward the prior asymptotic value.
Dependence on N: Capacity increases strictly with N and approaches 1 as the number of databases approaches infinity.The theorem also characterizes optimal download cost per message bit as the reciprocal of the rate.
Finite message size: Messages whose size is any positive integer multiple of N^K bits achieve capacity exactly with zero error.For arbitrary sizes, zero-padding gives a naive scheme that approaches capacity for large L but can be sub-optimal for smaller messages.

4 Theorem 1: Achievability

The achievability proof introduces a finite-length zero-error PIR scheme and develops its intuition through examples before giving an algorithm for arbitrary K and N. It then proves correctness, privacy, and capacity attainment.

Scheme: A zero-error scheme for messages of length L = N^K bits per message achieves the PIR capacity.Repeated application creates schemes with message lengths approaching infinity, covering both zero-error and ε-error capacity.
Construction: The construction is developed from simple examples into an algorithmic description for arbitrary numbers of messages K and databases N.The paper revisits the examples after presenting the general formulation.

4.1 Two Examples to Illustrate the Key Ideas

The achievable PIR scheme builds queries by enforcing symmetry across databases and messages while using undesired-message side information to retrieve new desired bits. Uniformly random, private permutations preserve privacy, and the examples achieve the corresponding capacities.

The scheme iteratively applies database symmetry, message symmetry, and side information from undesired messages.These principles expand an initially focused retrieval into the full query construction.
For N = 2 and K = 2, private uniform permutations of each message’s bits instantiate the query variables a_i and b_i.The user privately generates independent random permutations before constructing queries.
Each desired bit is either downloaded directly or mixed with side information available from another database, enabling recovery by subtraction.The query structure uses sums of message bits without repeating a message bit within a query set.
Uniform random permutations make all query realizations equally likely regardless of the desired message, ensuring privacy.Databases see randomly selected message bits and sums of randomly selected pairs, not the requested index.
For N = 2 and K = 2, the scheme downloads 6 bits to retrieve 4 desired bits, achieving rate 4/6 = 2/3.This rate matches the capacity for the example.
The N = 3, K = 3 construction generalizes the same structure using independent uniform permutations of three messages and progressively larger sums.The example’s query outputs are organized across blocks and databases.

4.2 Formal Description of Achievable Scheme

The formal scheme combines a fixed query structure, a deterministic construction indexed by the desired message, and a private random mapping from placeholders to message bits. Its blocks contain balanced sums whose structure is identical across databases and desired indices.

4.2 Formal Description of Achievable Scheme: A k-sum is the sum of k distinct variables drawn from different message vectors, and its type is the set of those vector indices.
4.2 Formal Description of Achievable Scheme: The scheme has three elements: a fixed query-set structure, a deterministic algorithm depending on θ, and a private random mapping to message bits.The random mapping is unknown to the databases.
4.2.1 A Fixed Query Set Structure: Each query set is partitioned into K blocks, with block k containing all k-sum types and exactly (N −1)^(k−1) instances of each type.No message symbol appears more than once within a database’s query set.
4.2.1 A Fixed Query Set Structure: For N = 3 and K = 3, blocks contain 1-sums, 2-sums, and 3-sums with 1, 2, and 4 instances of each type, respectively.
4.2.1 A Fixed Query Set Structure: The query structure is fixed independently of θ and the database, so every query set has the same arrangement of placeholders.Figure 1 illustrates the structure of an individual block.
4.2.2 A Deterministic Algorithm: The deterministic algorithm uses a next-variable function, partitions sums into message-containing M terms and interference I terms, and initializes query sets block by block.The nomenclature M and I denotes message and interference.
4.2.2 A Deterministic Algorithm: For each database, the algorithm uses I terms from other databases’ previous blocks to create new M terms by adding a desired-message variable.The construction also generates the required instances of types that exclude the desired index.
4.2.3 Ordered Representation and Mapping to Message Bits to Produce Q[θ]: The ordered representation sorts blocks, sum types, and query elements lexicographically before mapping them to message bits through independent uniform permutations.The query notation distinguishes questions about message-bit realizations from the random variables themselves, keeping queries independent of message realizations.

4.3 The Two Examples Revisited

The revisited examples verify the scheme’s decoding, privacy, and rate claims in concrete settings. They show direct retrieval and side-information cancellation for two messages, then extend the same pattern to three databases and three messages.

The N = 2, K = 2 example uses four bits per message and displays query structures and outputs for both desired-message choices.
For either desired index, every desired bit is downloaded directly or appears with known side information from the other database.This establishes decodability for the example.
The example’s query distribution is identical across desired indices, so the database gains no information about θ.The probability of an observed query realization is the same for θ = 1 and θ = 2.
The N = 2, K = 2 example retrieves 4 desired bits from 6 downloaded bits, achieving rate 4/6 = 2/3.This matches capacity for the case.
The three-message outputs combine one-, two-, and three-message sums across successive query blocks.The displayed constructions show the same block progression for each desired-message choice.
The N = 3, K = 3 construction retrieves 27 desired bits from 39 downloaded bits, achieving rate 27/39 = 9/13.This matches capacity for the case.

4.4 Proof of Correctness, Privacy and Achieving Capacity

The proofs establish that the constructed queries have balanced structure, permit zero-error decoding, preserve privacy, and achieve the PIR capacity. The same scheme remains capacity-achieving after eliminating any subset of nonrequested messages, while message independence is required for the converse.

The query structure has the required cardinality, enabling the subsequent correctness, privacy, and rate proofs.
No variable repeats within a database query set, and each message vector contributes exactly N^(K−1) variables.
Induction shows that block k contains exactly (N −1)^(k−1) instances of every possible k-sum type.The basis is the one-variable first block, and the inductive step handles types excluding or including θ.
The scheme is zero-error decodable because desired variables appear either without interference or with interference downloaded separately from another database.It retrieves N^K desired bits in total.
The achieved rate is (1+1/N +···+ 1/N^(K−1))^−1, matching the PIR capacity.
Uniform independent permutations make every query realization equally likely for every θ, so the query and database-observable information are independent of the desired index.
The scheme’s rate remains achievable for dependent messages, but message independence is needed for the converse and the resulting rate need not be capacity in that setting.For identical messages with N = K = 2, the capacity is 1 rather than 2/3.
The construction remains correct, private, and capacity-achieving after any subset of nonrequested messages is set to zero.Desired-bit count stays fixed while the number of downloaded equations decreases.

5 Theorem 1: Converse

The converse proof establishes the PIR capacity upper bound by combining auxiliary lemmas, applying them repeatedly across messages, and taking the asymptotic message-length limit.

The converse is proved for arbitrary message length L, without assuming L = N^K.
The proof begins with useful lemmas and applies Lemma 6 repeatedly from k = 3 through K.
Combining Lemma 5 with equation (64), then dividing by L and letting L go to infinity, completes the converse.

6 Discussion

The discussion examines upload and message-size constraints and connects PIR to blind interference alignment. It also highlights constructions that preserve privacy while reducing upload or exploiting interference alignment.

Upload Cost: Large-message PIR treats upload as negligible relative to download, but upload cost can also be reduced through fewer query possibilities.For K = 2 and N = 2, grouping message bits reduces the query choice to 1 out of 2 groups rather than 2 out of 4 bits.
Upload Cost: For K = 2 and N = 2, a scheme with only two query possibilities per database remains private and reduces each database’s storage from 8 bits to 6 bits.
Upload Cost: For K = 3 and N = 2, restricting each database to three query possibilities limits capacity to 1/2, below the unconstrained PIR capacity of 4/7.
Upload Cost: Interference alignment enables recovery of each desired symbol from two equations by forcing undesired symbols into one dimension.
Message Size: The capacity-achieving scheme uses message size N^K bits, but smaller messages can still achieve capacity in some settings.
Message Size: Determining the minimum message size required for capacity remains an open direction called message-size-constrained PIR capacity.
Similarities between PIR and Blind Interference Alignment: PIR and blind interference alignment map messages to users, queries to channel coefficients, and answers to received signals.
Similarities between PIR and Blind Interference Alignment: For K > 2, PIR extends beyond existing blind interference alignment results by permitting arbitrary coherence patterns.

7 Conclusion

The paper places PIR within a broader crossover between information theory and computer science. This crossover can create opportunities for new insights.

Crossovers between information theory’s coding-rate problems and computer science’s complexity problems open opportunities for new insights.