pipette
ENEnglish

Weak Private Information Retrieval for Graph-based Storage under -privacy

Jayesh Seshadri, Prasad Krishnan

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.