The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems
2026-02-18 • Information Theory
Information TheoryCryptography and SecurityNetworking and Internet Architecture
AI summaryⓘ
The authors study a problem where someone wants to get a specific message from multiple servers without revealing which message they want and without learning anything else about the database. The messages are stored so that each one is held by exactly two servers, represented as links between nodes in a graph. They examine two ways servers share secret randomness to protect the data: one where random values are shared only between pairs of servers that hold the same message, and another where all servers share the same randomness. The authors find the best possible rates for retrieving messages privately and the minimum randomness needed, showing that the second way generally allows better performance.
Symmetric Private Information Retrieval (SPIR)Graph-replicated databaseCommon randomnessUser privacyDatabase privacySPIR capacityPath graphRegular graphPIR schemes
Authors
Shreya Meel, Sennur Ulukus
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.