The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems

• URL: http://arxiv.org/abs/2602.16700v1
• Date: Wed, 18 Feb 2026 18:46:58 GMT
• Title: The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems
• Abstract summary: We study the problem of SPIR on graph-replicated database systems.<n>Each message is replicated at exactly two servers.<n>We quantify the minimum amount of common randomness required to achieve the capacity.
• Score: 43.914623898157856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In symmetric private information retrieval (SPIR), a user communicates with multiple servers to retrieve from them a message in a database, while not revealing the message index to any individual server (user privacy), and learning no additional information about the database (database privacy). We study the problem of SPIR on graph-replicated database systems, where each node of the graph represents a server and each link represents a message. Each message is replicated at exactly two servers; those at which the link representing the message is incident. To ensure database privacy, the servers share a set of common randomness, independent of the database and the user's desired message index. We study two cases of common randomness distribution to the servers: i) graph-replicated common randomness, and ii) fully-replicated common randomness. Given a graph-replicated database system, in i), we assign one randomness variable independently to every pair of servers sharing a message, while in ii), we assign an identical set of randomness variable to all servers, irrespective of the underlying graph. In both settings, our goal is to characterize the SPIR capacity, i.e., the maximum number of desired message symbols retrieved per downloaded symbol, and quantify the minimum amount of common randomness required to achieve the capacity. To this goal, in setting i), we derive a general lower bound on the SPIR capacity, and show it to be tight for path and regular graphs through a matching converse. Moreover, we establish that the minimum size of common randomness required for SPIR is equal to the message size. In setting ii), the SPIR capacity improves over the first, more restrictive setting. We show this through capacity lower bounds for a class of graphs, by constructing SPIR schemes from PIR schemes.

Related papers

• Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results [39.20087907351314]
  We introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system.<n>This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements.<n>We derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements.
  arXiv  Detail & Related papers  (2026-09-14T17:03:36Z)
• Local Private Information Retrieval for Graph-Based Replicated Systems [39.20087907351314]
  We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems.<n>In our proposed privacy setting, the user is concerned with hiding the message index from a particular server.<n>We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
  arXiv  Detail & Related papers  (2026-08-31T17:50:47Z)
• Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems [39.20087907351314]
  We introduce a novel setting where the user's privacy is governed by the servers' storage structure.<n>In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server.<n>We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
  arXiv  Detail & Related papers  (2026-05-11T17:25:10Z)
• Private Information Retrieval for Graph-based Replication with Minimal Subpacketization [3.795745240553126]
  We design new minimal-subpacketization schemes for information-theoretic private information retrieval on graph-based replicated databases.<n>In graph-based replication, the system consists of $K$ files replicated across $N$ servers according to a graph with $N$ vertices and $K$ edges.<n>The client wants to retrieve one desired file, while keeping the index of the desired file private from each server via a query-response protocol.
  arXiv  Detail & Related papers  (2026-01-15T00:34:27Z)
• Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
  We revisit the problem of symmetric private information retrieval in settings where the database replication is modeled by a simple graph.<n>We let all the servers share some common randomness, independent of the messages.<n>We quantify the improvement in SPIR capacity, i.e., the maximum ratio of the number of desired and downloaded symbols.
  arXiv  Detail & Related papers  (2025-10-29T17:40:40Z)
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
  symmetric private information retrieval on replicated databases modeled by a simple graph.<n>We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph.
  arXiv  Detail & Related papers  (2025-07-23T17:51:08Z)
• New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage [39.51026717015587]
  We study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems.<n>We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds.
  arXiv  Detail & Related papers  (2025-04-29T16:05:42Z)
• Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
  We consider the private information retrieval problem for a multigraph-based replication system.<n>Our goal is to establish upper and lower bounds on the PIR capacity of the $r$-multigraph.
  arXiv  Detail & Related papers  (2025-01-29T18:48:22Z)
• QuTE: decentralized multiple testing on sensor networks with false discovery rate control [93.1040521878626]
  This paper designs methods for decentralized multiple hypothesis testing on graphs equipped with provable guarantees on the false discovery rate (FDR)<n>We consider the setting where distinct agents reside on the nodes of an undirected graph, and each agent possesses p-values corresponding to one or more hypotheses local to its node.<n>Each agent must individually decide whether to reject one or more of its local hypotheses by only communicating with its neighbors, with the joint aim that the global FDR over the entire graph must be controlled at a predefined level.
  arXiv  Detail & Related papers  (2022-10-09T19:48:39Z)
• Privatized Graph Federated Learning [57.14673504239551]
  We introduce graph federated learning, which consists of multiple units connected by a graph. We show how graph homomorphic perturbations can be used to ensure the algorithm is differentially private.
  arXiv  Detail & Related papers  (2022-03-14T13:48:23Z)
• Jointly Cross- and Self-Modal Graph Attention Network for Query-Based Moment Localization [77.21951145754065]
  We propose a novel Cross- and Self-Modal Graph Attention Network (CSMGAN) that recasts this task as a process of iterative messages passing over a joint graph. Our CSMGAN is able to effectively capture high-order interactions between two modalities, thus enabling a further precise localization.
  arXiv  Detail & Related papers  (2020-08-04T08:25:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.