Search papers, labs, and topics across Lattice.
This paper investigates symmetric private information retrieval (SPIR) on graph-replicated database systems, where messages are replicated across pairs of servers represented as nodes in a graph. The authors analyze the SPIR capacity (retrieved message symbols per downloaded symbol) and the minimum common randomness needed for database privacy under two common randomness distribution schemes: graph-replicated and fully-replicated. They derive a general lower bound on SPIR capacity for graph-replicated common randomness, proving its tightness for path and regular graphs, and demonstrate capacity improvements with fully-replicated common randomness via PIR scheme constructions.
Sharing randomness across all servers in a graph-based database system boosts private information retrieval capacity, outperforming schemes where randomness is tied to individual message replicas.
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.
