Weak Private Information Retrieval for Graph-based Storage under ε-privacy
Abstract
The problem of Private Information Retrieval (PIR) across graph-based replicated systems has seen a surge of interest in recent literature. In such systems, servers are modeled as the vertices of a graph, and each file is represented by an edge connecting the pair of servers that store it. While previous research on Graph-PIR (G-PIR) has focused mostly on perfect information-theoretic privacy, relaxing this constraint has the potential for significantly higher retrieval rates. In this work, we consider the setting of Graph-based Weak Private Information Retrieval (G-WPIR), under an ε-privacy metric. We adapt an existing G-WPIR scheme for arbitrary graphs to analyze its performance under the ε-privacy metric. Additionally, we establish a lower bound on the expected download cost for arbitrary graphs under the ε-privacy metric and derive from it an explicit rate upper bound for complete graphs. Finally, we show the achievable rate-privacy trade-offs for two specific graph classes---complete graphs and complete bipartite graphs.
Related
- The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
- Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
- Local Private Information Retrieval for Graph-Based Replicated Systems
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- Quantum Private Information Retrieval on Forests
BibTeX
@misc{seshadri2026weak,
title = {{Weak Private Information Retrieval for Graph-based Storage under $ε$-privacy}},
author = {Jayesh Seshadri and Prasad Krishnan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19456},
eprint = {2610.19456},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19456},
}
RIS
TY - UNPB
TI - Weak Private Information Retrieval for Graph-based Storage under ε-privacy
AU - Jayesh Seshadri
AU - Prasad Krishnan
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19456
UR - https://arxiv.org/abs/2610.19456
AB - The problem of Private Information Retrieval (PIR) across graph-based replicated systems has seen a surge of interest in recent literature. In such systems, servers are modeled as the vertices of a graph, and each file is represented by an edge connecting the pair of servers that store it. While previous research on Graph-PIR (G-PIR) has focused mostly on perfect information-theoretic privacy, relaxing this constraint has the potential for significantly higher retrieval rates. In this work, we consider the setting of Graph-based Weak Private Information Retrieval (G-WPIR), under an ε-privacy metric. We adapt an existing G-WPIR scheme for arbitrary graphs to analyze its performance under the ε-privacy metric. Additionally, we establish a lower bound on the expected download cost for arbitrary graphs under the ε-privacy metric and derive from it an explicit rate upper bound for complete graphs. Finally, we show the achievable rate-privacy trade-offs for two specific graph classes---complete graphs and complete bipartite graphs.
ER -