Converse for Multi-Server Single-Message PIR with Side Information

Li Su, Michael Gastpar

TL;DR

This paper tackles the challenge of private information retrieval (PIR) from multiple servers when the user already possesses some side information. They establish the exact capacity for this scenario, proving that the previously proposed "Partition-and-Coding" scheme is optimal. This work is significant because it fully characterizes the performance limits of private data retrieval under these common conditions.

What Problem Does This Paper Address?

Imagine you want to download a specific file from a distributed storage system (like a cloud service with data spread across multiple servers). The crucial part is that you want to do this without the servers knowing which file you're interested in. This is the core of Private Information Retrieval (PIR). Now, add a twist: you already have some related files (side information) on your device. This side information can potentially help you download the desired file more efficiently. However, it also complicates the privacy aspect, as the servers might infer your request by observing how you use your side information. This paper addresses the problem of Multi-Server Single-Message PIR with Side Information (MSPIR-SI), aiming to find the maximum rate at which a user can download a single message privately, given they have $M$ side information messages and the data is stored across $N$ non-colluding servers, each holding $K$ messages. The servers know the number of side information messages the user has, but not their specific indices.

Methods

The paper's main contribution is a converse bound on the achievable download rate. This means they prove an upper limit on how fast a user can download data privately under these conditions. They achieve this by introducing a novel concept called "virtual side information." For any given query a server receives, and for any specific message the user might want, virtual side information represents the set of side information indices that would be needed to recover that message, given the server's response. This concept is crucial for their proof. They then leverage this to show that the capacity is precisely characterized by a formula involving the number of servers ($N$), the number of side information messages ($M$), and the total number of messages ($K$).

The paper also discusses the achievability of this bound, referring to a "Partition-and-Coding" scheme proposed by Kadhe et al. They generalize this scheme and demonstrate that it achieves the derived capacity, thus fully characterizing the problem.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Virtual Side Information: This is the core conceptual innovation. It allows the authors to reason about the information available to the servers and the user in a unified way, even when the actual side information indices are unknown to the servers. It provides a way to analyze the privacy-utility trade-off.
  • Capacity Characterization: The paper fully characterizes the capacity for MSPIR-SI, meaning they've found the ultimate limit for this problem. This is a significant theoretical achievement.
  • Generalization of Existing Work: The work extends previous results on PIR with side information from single-server to multi-server settings and also covers cases where the number of messages is not perfectly divisible by $M+1$.
  • Symmetry is Key: The proofs rely heavily on symmetry arguments, showing that without loss of generality, certain assumptions can be made about the virtual side information to simplify the analysis.

Key Results

The paper establishes the capacity of the Multi-Server Single-Message Private Information Retrieval with Side Information (MSPIR-SI) problem as:

$C(K, M, N) = \left(1 + \frac{1}{N} + \frac{1}{N^2} + \cdots + \frac{1}{N\left\lceil {\frac{K}{{M + 1}}} \right\rceil - 1} \right)^{-1}$

This formula represents the maximum achievable download rate. The paper proves this by:

  1. Deriving a converse bound (upper bound on capacity) using the concept of virtual side information.
  2. Showing that the Partition-and-Coding scheme (a generalization of prior work) achieves this bound, thus confirming it as the exact capacity.

Limitations and Future Work

  • Asymmetric Coding Scheme Example: The paper presents an example of an asymmetric coding scheme that is suboptimal, highlighting the complexity of designing optimal schemes when virtual side information differs across servers. This suggests that achieving optimal rates can be challenging in practice.
  • Focus on Information-Theoretic Capacity: The results are information-theoretic, meaning they assume ideal, error-free communication and unlimited computational power. Future work could explore practical implementations with finite computation and noise.
  • Generalization to Other PIR Variants: The paper focuses on single-message PIR. Extending these results to multi-message PIR or other variations with side information would be a natural next step.

Summary updated

Abstract

Multi-server single-message private information retrieval is studied in the presence of side information. In this problem, K independent messages are replicatively stored at N non-colluding servers. The user wants to privately download one message from the servers without revealing the index of the message to any of the servers, leveraging its M side information messages. We assume that the servers only know the number of the side information messages available at the user but not their indices. We prove a converse bound on the maximum download rates, which coincides with the known achievability scheme proposed by Kadhe et. al.. Hence, we characterize the capacity for this problem, which is${\left( {1 + \frac{1}{N} + \frac{1}{{{N^2}}} + \cdots + \frac{1}{{N\left\lceil {\frac{K}{{M + 1}}} \right\rceil - 1}}} \right)^{ - 1}}$. The proof leverages a novel concept that we call virtual side information, which, for a fixed query and any message, identifies the side information that would be needed in order to recover that message.
BibTeX
@misc{su2018converse,
  author = {Li Su and Michael Gastpar},
  title = {{Converse for Multi-Server Single-Message PIR with Side Information}},
  year = {2018},
  eprint = {1809.09861},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.09861},
}

Loading related content...

Figure