• Computer Science > Information Theory [Submitted on 18 Feb 2026] Title:The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems View PDF HTML (experimental)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.
Article Summaries:
- Researchers have analyzed symmetric private information retrieval (SPIR) on graph‑replicated database systems, where each message is stored on exactly two servers linked by an edge. Two common‑randomness models are examined: (i) graph‑replicated randomness, assigning independent randomness to each server pair sharing a message, and (ii) fully‑replicated randomness, giving all servers the same random variables. For the first model, the authors derive a general lower bound on SPIR capacity and prove it tight for path and regular graphs, also showing the minimum common‑randomness size equals the message size. In the second model, capacity improves; lower bounds are provided for a class of graphs by converting PIR schemes to SPIR.
Sources: