Weak Private Information Retrieval for Graph-based Storage
摘要
A distributed storage system with graph-based replication consists of a collection of databases and the files they contain. The databases (or servers) are represented as the vertices of a graph, while each file is stored in a distinct pair of servers and is represented by an edge of this graph. Private information retrieval (G-PIR) on such a graph-based storage system involves a client which seeks to retrieve a desired file via a query-response protocol, without leaking the identity of the desired file index to any database. The goal of G-PIR is to maximize the rate (reciprocal of the total normalized download) under the privacy constraint. Prior work on G-PIR has involved perfect information-theoretic privacy (i.e., null leakage). However, if the privacy constraint is relaxed, then PIR protocols could be designed that have even higher rates. We term such protocols as Graph-based Weak Private Information Retrieval (G-WPIR) protocols and initiate their formal study in this work. We propose a G-WPIR scheme for arbitrary graphs, and identify the trade-offs it achieves between rate and privacy, under two well known leakage metrics: mutual information leakage and maximal leakage. Our protocol employs minimal subpacketization (representing a file-size constraint) and employs a simple probabilistic query realization to obtain the smooth trade-off. We extend this protocol with some modifications to two special classes of graphs, the complete graphs and the complete bipartite graphs, and identify the corresponding rate-privacy trade-offs achieved.
正文
A distributed storage system with graph-based replication consists of a collection of databases and the files they contain. The databases (or servers) are represented as the vertices of a graph, while each file is stored in a distinct pair of servers and is represented by an edge of this graph. Private information retrieval (G-PIR) on such a graph-based storage system involves a client which seeks to retrieve a desired file via a query-response protocol, without leaking the identity of the desired file index to any database. The goal of G-PIR is to maximize the rate (reciprocal of the total normalized download) under the privacy constraint. Prior work on G-PIR has involved perfect information-theoretic privacy (i.e., null leakage). However, if the privacy constraint is relaxed, then PIR protocols could be designed that have even higher rates. We term such protocols as Graph-based Weak Private Information Retrieval (G-WPIR) protocols and initiate their formal study in this work. We propose a G-WPIR scheme for arbitrary graphs, and identify the trade-offs it achieves between rate and privacy, under two well known leakage metrics: mutual information leakage and maximal leakage. Our protocol employs minimal subpacketization (representing a file-size constraint) and employs a simple probabilistic query realization to obtain the smooth trade-off. We extend this protocol with some modifications to two special classes of graphs, the complete graphs and the complete bipartite graphs, and identify the corresponding rate-privacy trade-offs achieved. Authors: Shodasakshari Vidya, Chandan Anand, Prasad Krishnan Categories: cs.IT, cs.CR PDF: https://arxiv.org/pdf/2607.21014v1
标签
- category:cs.cr
- category:cs.it
- primary_category:cs.it
- source:arxiv
- type:paper
扩展字段
{
"arxiv_id": "2607.21014v1",
"authors": [
"Shodasakshari Vidya",
"Chandan Anand",
"Prasad Krishnan"
],
"categories": [
"cs.IT",
"cs.CR"
],
"comment": null,
"doi": null,
"entry_id": "https://arxiv.org/abs/2607.21014v1",
"pdf_url": "https://arxiv.org/pdf/2607.21014v1",
"primary_category": "cs.IT",
"search_query": "cat:cs.CR",
"updated_at": "2026-07-23T07:55:59+00:00"
}