Source-linked AI summary
Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
Karim Banawan, Sennur Ulukus
TL;DR
The paper asks how efficiently a user can privately retrieve multiple messages from replicated, non-communicating databases. It develops capacity characterizations and bounds for different demand regimes, showing exact results in several cases and near-tight bounds otherwise. The results indicate that joint retrieval is more efficient than successive single-message retrieval.
Problem
MPIR seeks the information-theoretic sum capacity for privately retrieving multiple messages without revealing which messages were requested.
Method
The paper analyzes MPIR over replicated non-colluding databases, using MDS-coded mixtures for P ≥ M/2 and a generalized staged scheme with converse bounds for P ≤ M/2.
Results
For remaining cases, the lower–upper-bound gap is at most 0.0082, with the worst case at M = 5, P = 2, and N = 2.
Takeaways & Limitations
Joint retrieval of desired messages strictly outperforms repeating a single-message capacity-achieving scheme for each message.
Takeaways & Limitations
The exact capacity remains an open problem for cases outside the characterized regimes.
Abstract
from arXiv · showhide
We consider the problem of multi-message private information retrieval (MPIR) from $N$ non-communicating replicated databases. In MPIR, the user is interested in retrieving $P$ messages out of $M$ stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR $C_s^P$ is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case $P \geq \frac{M}{2}$, we determine the exact sum capacity of MPIR as $C_s^P=\frac{1}{1+\frac{M-P}{PN}}$. The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For $P \leq \frac{M}{2}$, we develop lower and upper bounds for all $M,P,N$. These bounds match if the total number of messages $M$ is an integer multiple of the number of desired messages $P$, i.e., $\frac{M}{P} \in \mathbb{N}$. In this case, $C_s^P=\frac{1-\frac{1}{N}}{1-(\frac{1}{N})^{M/P}}$. The achievable scheme in this case generalizes the single-message capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most $0.0082$, which occurs for $M=5$, $P=2$, $N=2$. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.
1 Introduction
The paper formulates multi-message private information retrieval and characterizes its sum capacity across message-demand regimes, showing that joint retrieval can outperform successive single-message retrieval.
- Problem motivation: MPIR retrieves P messages from M replicated databases without revealing the identities of the desired messages.The databases are non-communicating and store identical copies of all messages.
- Prior work: Earlier multi-block MPIR schemes did not determine the information-theoretic capacity.Prior work used mixed data blocks, reduced communication overhead, or XOR-based constructions.
- Main results: For P ≥ M/2, the paper determines the exact MPIR sum capacity and uses MDS-coded mixtures of all messages.The result is presented as an exact characterization for this demand regime.
- Main results: Joint retrieval of the desired messages strictly outperforms successive use of single-message retrieval schemes.The paper also gives an achievable rate region describing trade-offs among the retrieval rates of the desired messages.
- Main results: For P ≤ M/2 and M/P ∈ N, the lower and upper bounds match and yield an exact sum capacity.The achievable scheme generalizes the single-message capacity-achieving scheme with an unbalanced number of stages per download round.
2 Problem Formulation
The formulation models MPIR over replicated, non-colluding databases: a user privately queries a chosen subset of messages and reconstructs it from the returned answers. Retrieval rates and sum capacity are defined from download cost under information-theoretic assumptions.
- Storage model: Each of the N non-colluding databases stores an identical copy of all M messages.This is equivalent to an (N, 1) repetition storage code.
- Retrieval model: The user selects a subset P of P message indices and sends a query to each database to retrieve the corresponding messages.The cardinality P of the potential message set is known to all databases.
- Privacy constraint: Privacy requires statistical independence between the queries and the selected message index set.The messages and queries are also assumed statistically independent because the user has no prior message knowledge.
- Answer and reliability constraints: Each database returns an answer string that is a deterministic function of its query and the stored messages.The user must reconstruct the desired messages reliably from all collected answers and the queries.
- Performance metric: The retrieval rate of message i is its length divided by the total download cost for the requested message set, and sum capacity optimizes the sum retrieval rate over private schemes.The information-theoretic formulation assumes sufficiently large message and field sizes and ignores upload cost.
3 Main Results and Discussions
The paper exactly characterizes MPIR sum capacity when P ≥ M/2 and gives matching bounds when M/P is an integer. In all remaining cases, the achievable scheme is near-optimal, while joint retrieval outperforms repeated single-message retrieval.
- Exact capacity for P ≥ M/2: For P ≥ M/2, the MPIR sum capacity is exactly characterized, with capacity strictly increasing in N and approaching 1 as N grows.The result applies to non-colluding replicated databases and covers the regime in which at least half the messages are desired.
- Comparison with repeated retrieval: For M = 3, P = 2, N = 2, the MPIR scheme achieves sum rate 4/5, exceeding the 5/7 rate from repeating the single-message scheme.The paper also gives an achievable rate region formed from single-message corner points, the symmetric sum-capacity point, and time sharing.
- Bounds for P ≤ M/2: For P ≤ M/2, lower and upper bounds are established for all M, P, and N.The bounds are derived through an achievable scheme and a converse bound.
- Exact capacity for integer M/P: When M/P is an integer, the lower and upper bounds match, yielding an exact capacity result.In this case, the sum capacity equals the single-message PIR capacity with M/P messages, although a new scheme is required to preserve privacy for every subset of P messages.
4 Achievability Proof for the Case P ≥M
For P ≥ M/2, the scheme achieves the upper bound using message symmetry, database symmetry, side information, and MDS-coded mixtures. The construction retrieves desired symbols privately and matches the sum capacity in the illustrated cases.
- Example: 8 desired bits in 10 downloads give an achievable sum rate of 8/10 in the M = 3, P = 2, N = 2 example.The scheme downloads 5 symbols from each database and retrieves four symbols from each of two desired messages.
- Scheme construction: MDS coding combines new desired symbols with previously decoded undesired symbols so the user can cancel side information and solve an invertible system.The scheme uses permutation matrices and an MDS generator matrix whose relevant submatrices are full-rank.
- Privacy: Random interleaving and uniformly random column permutations make downloaded symbols and encoding matrices independent of the desired message subset.The construction uses private interleavers and independent permutation matrices across databases to satisfy privacy.
- Comparison: Joint retrieval strictly outperforms repetition-based successive single-message retrieval in the M = 5, P = 3, N = 2 example.The cited comparison contrasts the proposed rate with the repetition-based achievable rate.
5 Achievability Proof for the Case P ≤M
For P ≤ M/2, the paper develops an achievable scheme that is optimal when M/P is an integer and otherwise incurs only a small loss from the upper bound.
- Achievability: The scheme is optimal when M is an integer multiple of P and has a small loss from the upper bound in other cases.It generalizes the ideas of the single-message scheme while retaining the stated regime P ≤ M/2.
- Achievability: Unequal numbers of stages are used across download rounds, unlike the prior single-message construction.The paper defines rounds by the number of summed symbols and stages as blocks exhausting combinations within a round.
- Achievability: The construction reduces to the single-message scheme when P = 1.
5.1 Motivating Example: M = 5, P = 2 Messages, N = 2 Databases
The M = 5, P = 2, N = 2 example designs queries backward from the final sum of all messages, using earlier rounds to create the required side information. The resulting scheme retrieves 68 desired bits in 112 downloads.
- Backward design: The scheme starts from the round summing all five messages and traces backward to determine side information needed from the other database.This reverses the usual top-down query design that begins with individual symbols.
- Stage structure: The five rounds use stage counts α1 = 5, α2 = 2, α3 = 1, α4 = 0, and α5 = 1.Round i downloads sums of i symbols, with stages supplying the combinations needed for decoding later rounds.
- Decoding: Side information from earlier rounds cancels undesired terms in later sums, including the final sum of all five messages.The construction uses symbols and mixtures from other databases to decode new desired symbols and generate later side information.
- Rate: 68 desired bits in 112 downloads produce the example’s achievable sum rate, written as 68/112.The downloads are split evenly, with 56 from each database.
5.2 Calculation of the Number of Stages
The stage counts are derived by categorizing symbol sums according to desired and undesired terms, then tracing side-information requirements backward across rounds. Vandermonde’s identity organizes the categories, while an IIR-filter representation systematically generates the stage sequence.
- Combinatorial organization: Vandermonde’s identity partitions i-term sums into categories containing k desired and i − k undesired messages.The identity also gives the number of query subgroups in each category.
- Stage recursion: Each round requires earlier-round side information to cancel undesired symbols from its i-term sums.The required stages are distributed across the remaining N − 1 databases.
- IIR representation: The stage sequence can be generated from an all-poles IIR filter by mapping its output through αk = y[(M − P) − k].The filter uses initial conditions determined by (N − 1)^(M − P) and reverses the round direction.
- Special case: For P = 1, the method yields αk = (N − 1)^(k − 1), and for N = 2 every round has one stage.This recovers the stage counts used by the single-message scheme.
5.3 General Achievable Scheme
The general achievable scheme organizes downloads into rounds and stages, using symmetry across messages and databases and previously generated side information. It ends by combining all messages and shuffling query order to preserve privacy.
- The scheme first randomly interleaves each message’s symbols, then initializes retrieval by downloading one symbol from every desired message.
- Stage allocation: The number of stages per round is determined by an IIR filter, with α_i equal to the filter output at an index corresponding to round i.
- Round construction: Each round downloads sums of symbols from the desired set and matching combinations from undesired messages to maintain message symmetry.
- Side information: Downloads are repeated across stages and databases, while undesired equations generated in one database provide side information for other databases.
- Side-information exploitation: Desired equations mix desired symbols with undesired symbols decoded from earlier rounds, including combinations of multiple desired symbols.
- Finalization: After rounds through M − P − 1, later rounds are suppressed except the final round, which mixes all M messages; query order is then uniformly shuffled.
5.4 Decodability, Privacy, and Calculation of the Achievable Rate
The scheme is designed so that downloaded interference becomes usable side information, enabling decoding while randomized symbol mappings and query ordering preserve privacy. Its stage counts and download totals are computed through the IIR-filter recurrence.
- Decodability: Reliability follows because each desired symbol is mixed with an undesired equation that can be decoded from another database.
- Decodability: The scheme downloads exactly the undesired equations needed as side information in subsequent rounds and databases.
- Privacy: Privacy follows from randomized message-symbol mappings and randomized query order, allowing any P-message subset to remain compatible with fixed queries at one database.
- Rate calculation: The IIR filter uses initial conditions y[−P] = (N − 1)^(M − P) and y[−P + 1] = ··· = y[−1] = 0 to determine α_i.
- Rate calculation: The total download and undesired-equation counts are obtained by summing combinations across rounds and stages.
- Achievable rate: The resulting achievable rate is the quantity identified as equation (31) in Theorem 2.
5.5 Further Examples for the Case P ≤M
The examples instantiate the scheme for several parameter choices, including cases where it meets the upper bound. They also expose a trade-off between coding and query complexity.
- M = 4, P = 2, N = 2: For M = 4, P = 2, N = 2, the stage sequence uses 2 individual-symbol stages, 1 two-symbol-sum stage, no three-symbol-sum stage, and 1 all-message stage.
- M = 4, P = 2, N = 2: The M = 4, P = 2, N = 2 query table downloads individual symbols from all messages at both databases before using sums as side information.
- M = 4, P = 2, N = 2: For M = 4, P = 2, N = 2, the scheme matches the upper bound and achieves the optimal sum rate because M/P is an integer.
- Scheme comparison: The two schemes trade field size against upload complexity: MDS coding requires q ≥ M, while the uncoded scheme can use the storage field but may require exponentially many queries.
- Larger N: For N > 2, an example uses stage counts α_1 = 6, α_2 = 4, α_3 = 4, α_4 = 0, and α_5 = 8, retrieving 252 desired symbols in 354 downloads.
- Larger M, P, and N: A larger example with N = 3 uses stage counts 67, 30, 12, 8, 0, 0, and 16 across seven rounds.
- Larger M, P, and N: The achievable sum rate in the larger example is 3933/37, with a gap of 166 compared with the stated bound.
6 Converse Proof
The converse proof establishes upper bounds for MPIR by exploiting symmetry, privacy, reliability, and interference lower bounds. An induction reduces problems with fixed P and M messages to smaller instances.
- Converse setup: The upper bound is tight when P ≥ M/2, and the proof extends the single-message converse to multiple desired messages.
- Symmetry and privacy: The proof assumes, without loss of generality, symmetric schemes and fixes one database’s response independently of the desired message subset.
- Interference bounds: For P ≥ M/2, an interference lower bound quantifies the uncertainty contributed by undesired messages in answer strings.
- Interference bounds: The converse uses reliability, deterministic answer functions, independence, conditioning, and the symmetry lemma to derive the interference constraint.
- Induction: For P > 2, grouping desired messages into blocks of size P yields an inductive relation that reduces an M-message problem to one with M − 2P messages.
- Interference conditioning: The interference conditioning lemma bounds the remaining uncertainty after conditioning on one disjoint P-message subset.
- Induction: Applying the induction hypothesis and evaluating the resulting sum produces the MPIR upper bound.
7 Conclusions
The paper establishes exact MPIR sum-capacity results in key parameter regimes and bounds the remaining cases. It also shows that jointly retrieving desired messages is more efficient than repeating single-message retrieval.
- The exact sum capacity is determined when the number of desired messages is at least half the total number of stored messages.
- When the total number of messages is an integer multiple of the number of desired messages, the sum capacity is given by a closed-form expression.The expression is described as resembling the single-message PIR capacity expression when the number of messages is M/P.
- Joint retrieval of the desired messages strictly outperforms repeating the single-message capacity-achieving scheme for each message.
- For the remaining cases, the paper derives lower and upper bounds rather than an exact capacity.
- 0.0082 is the worst-case gap between the lower and upper bounds, occurring for N = 2, M = 5, and P = 2.The gap decreases monotonically in N according to numerical observations.