Two-Level Private Information Retrieval

Ruida Zhou, Chao Tian, Hua Sun, James S. Plank

Abstract

Standard Private Information Retrieval (PIR) models assume a uniform privacy requirement across all data, which can lead to significant bandwidth inefficiencies when messages have varying levels of sensitivity. This paper introduces the "Two-Level" PIR model, where messages are partitioned into two sets with distinct privacy requirements. We propose two novel coding schemes—Non-uniform Successive Cancellation (NS) and Non-uniform Block Cancellation (NB)—to achieve higher retrieval rates than traditional symmetric PIR. We also derive capacity upper bounds and demonstrate through numerical analysis that these schemes provide substantial coding gains by exploiting the "slack" in lower-privacy requirements.

Introduction

Private Information Retrieval (PIR) is a fundamental problem in information theory where a user seeks to download a specific file from a set of $N$ servers without revealing the identity of the file. In the classical $T$-colluding PIR model, privacy must be maintained even if any $T$ servers collude. However, real-world data often exhibits heterogeneous sensitivity. For instance, a user might require high-level privacy for political content but only basic privacy for public domain media.

Treating all messages with the highest level of protection is inefficient. This work formulates a Two-Level PIR system where $K_1$ messages require protection against $T_1$ colluding servers, while the remaining $K_2$ messages require protection against a smaller number $T_2$ ($T_2 < T_1$). The objective is to characterize the capacity—the maximum possible retrieval rate—of such a system.

Proposed Coding Schemes

To address the broken symmetry in two-level PIR, we developed two primary achievability schemes:

Non-uniform Successive Cancellation (NS) Scheme

The NS scheme generalizes standard symmetric PIR by partitioning messages into groups and applying Maximum Distance Separable (MDS) codes with parameters tailored to each group's privacy level. It manages interference symbols across different layers of the download, ensuring that undesired symbols can be canceled out successively. This scheme is particularly effective when the two privacy levels $T_1$ and $T_2$ are relatively close.

Non-uniform Block Cancellation (NB) Scheme

The NB scheme treats the system as a mixture of different privacy blocks. It constructs "pure-interference" tables and mixes them with stacked versions of standard PIR codes. By leveraging the lower privacy requirements of the second message set, the NB scheme excels when the higher privacy level $T_1$ approaches the total number of servers $N$.

Example of the coding group structure and interference management in the proposed schemes.

Capacity Bounds and Results

We derived a general capacity upper bound ($\\overline{R}$) using an inductive proof technique based on Shannon entropy and privacy constraints. While this bound reduces to the known capacity of standard PIR when $T_1 = T_2$, we found that it is not always tight for all parameters. For specific cases, such as a (3, 2:2, 1:3) system, computer-aided methods were used to tighten the bound further.

Numerical analysis confirms that both the NS and NB schemes outperform naive baselines that treat all messages with $T_1$ privacy. The performance gap between the schemes depends on the system parameters, as illustrated below.

Performance comparison of NS and NB schemes against the capacity upper bound as a function of $K_1$ and $T_1$.

Conclusion

This work demonstrates that accounting for heterogeneous privacy requirements in PIR systems leads to significant efficiency gains. By breaking the symmetry of standard PIR and developing non-uniform coding strategies, we can achieve higher retrieval rates while maintaining strict privacy guarantees. Future research will explore extending these results to multi-level privacy hierarchies and considering storage-constrained or coded-storage scenarios.

Summary updated

BibTeX
@article{zhou2022two,
  author = {Ruida Zhou and Chao Tian and Hua Sun and James S. Plank},
  title = {{Two-Level Private Information Retrieval}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2022},
  doi = {10.1109/jsait.2022.3181216},
}
Figure