The Capacity of Symmetric Private Information Retrieval Under Arbitrary Collusion and Eavesdropping Patterns

Jiale Cheng, Nan Liu, Wei Kang, Yang LiIEEE Trans. IFS 2020 · DOI

TL;DR

This paper tackles the complex problem of Symmetric Private Information Retrieval (SPIR) by considering arbitrary patterns of server collusion and eavesdropping. The authors introduce a unified framework that quantifies the system's capacity, demonstrating that the combined effect of these adversarial patterns can be captured by a single parameter derived from a linear programming problem. This work provides a significant step towards understanding the fundamental limits of secure data retrieval in realistic, non-ideal network conditions.

What Problem Does This Paper Address?

In the realm of private information retrieval (PIR), users want to retrieve data from servers without revealing their query to any single server. Symmetric PIR (SPIR) adds another layer of privacy: servers must collectively ensure the user doesn't learn about any undesired messages. However, real-world scenarios are more complex. Servers might collude to share information, and external eavesdroppers might try to intercept communications. Previous work often simplified these threats by assuming symmetric collusion (e.g., any T servers collude) or symmetric eavesdropping. This paper addresses the gap by considering arbitrary patterns of both collusion and eavesdropping, aiming to find the capacity of SPIR under these more general and realistic adversarial models.

Methods

The core of this paper lies in its theoretical framework for analyzing the SPIR capacity under arbitrary collusion and eavesdropping patterns. The authors define a "joint pattern" that unifies both collusion and eavesdropping structures. They then formulate a linear programming problem (LP1) whose optimal solution, denoted as $F^*$, directly influences the SPIR capacity. The capacity is shown to be $1 - \frac{1}{F^*}$ under certain conditions related to common randomness. The proof involves constructing an achievable scheme based on the solution of LP1 and a converse argument using a dual linear programming problem (LP2). This approach allows for a unified treatment of various collusion and eavesdropping scenarios.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework for Collusion and Eavesdropping: The paper's most significant contribution is the introduction of a "joint pattern" that elegantly combines arbitrary collusion and eavesdropping patterns into a single entity. This allows for a unified analysis of their collective impact on SPIR capacity.
  • Interchangeability of Collusion and Eavesdropping: A key finding is that, in terms of SPIR capacity, collusion and eavesdropping constraints are interchangeable. The system's resilience is determined by the combined structure of the joint pattern, not by the individual patterns in isolation.
  • Linear Programming as the Determinant: The capacity of the SPIR problem under these complex adversarial conditions is directly linked to the optimal solution of a specific linear programming problem. This provides a powerful computational tool for determining capacity for any given pattern.
  • Generalization of Prior Results: The paper shows that its general framework naturally encompasses and generalizes previously known results for simpler cases, such as symmetric collusion or no eavesdropping, validating its approach.

Key Results

The paper establishes the capacity of the SPIR problem under arbitrary collusion pattern $P_c$ and eavesdropping pattern $P_e$ as:

$C(P_c, P_e) = \begin{cases} 1 - \frac{1}{F^*} & \text{if } \rho \ge \frac{1}{F^* - 1} \\ 0 & \text{otherwise} \end{cases}$

where $F^*$ is the optimal value of the linear programming problem (LP1): $\max \mathbf{1}^T \mathbf{y}$ subject to $B_{P_j}\mathbf{y} \le \mathbf{1}_{M_j}$ and $\mathbf{y} \ge \mathbf{0}_N$. Here, $B_{P_j}$ is the incidence matrix of the joint pattern $P_j$, and $\rho$ is the amount of common randomness shared between servers relative to the message size.

As special cases, the paper derives the capacity for:

  • SPIR under arbitrary collusion patterns (by setting $P_e = \emptyset$).
  • SPIR under arbitrary eavesdropping patterns (by setting $P_c = \{\{1\}, \dots, \{N\}\}$).
  • PIR under arbitrary eavesdropping patterns.

Limitations and Future Work

  • Focus on Replicated Databases: The current work focuses on replicated databases. Extending the framework to other storage models, such as MDS-coded databases, would be a valuable future direction.
  • PIR with Arbitrary Collusion and Eavesdropping: While the paper provides results for SPIR, the problem of PIR with arbitrary colluding and eavesdropping patterns is explicitly stated as an open area for future research. The interaction between these patterns in the PIR context is noted as complex.
  • Practical Implementation: The theoretical results provide fundamental limits. Future work could explore practical coding schemes that achieve or approach these capacities in real-world systems.

Summary updated

BibTeX
@article{cheng2020capacity,
  author = {Jiale Cheng and Nan Liu and Wei Kang and Yang Li},
  title = {{The Capacity of Symmetric Private Information Retrieval Under Arbitrary Collusion and Eavesdropping Patterns}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2020},
  doi = {10.1109/tifs.2022.3201375},
}
Figure