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.