Graph based weak private information retrieval improves download rates with privacy trade offs
Weak Private Information Retrieval for Graph-based Storage under $ε$-privacy
Information Theory
Summary
Private Information Retrieval (PIR) lets people download data from servers without revealing what they want. In systems where servers are connected in a network (a graph) and each data file is shared between two servers, the authors study a relaxed privacy measure called ε-privacy. They analyze how well an existing approach works under this privacy measure and find limits on how efficiently data can be retrieved. They also explore these trade-offs specifically for fully connected and bipartite network setups.
What this means in practice
- •For cloud storage engineers: Optimize data retrieval rates in distributed storage networks with known privacy relaxation.
- •For network security teams: Design retrieval protocols balancing privacy guarantees and performance in server networks modeled as graphs.
A theory result. No direct application yet.
Authors
Jayesh Seshadri, Prasad Krishnan
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.