Symmetric Private Information Retrieval at the Private Information Retrieval Rate

Abstract

We consider the problem of symmetric private information retrieval (SPIR) with user-side common randomness. In SPIR, a user retrieves a message out of K messages from N non-colluding and replicated databases in such a way that no single database knows the retrieved message index (user privacy), and the user gets to know nothing further than the retrieved message (database privacy), i.e., the privacy constraint between the user and the databases is symmetric. SPIR has the following three properties: its capacity is smaller than the capacity of PIR which requires only user privacy; it is infeasible in the case of a single database; and it requires presence of shared common randomness among the databases. We introduce a new variant of SPIR where the user is provided with a random subset of the shared database common randomness, which is unknown to the databases. We determine the exact capacity region of the triple (d,ρS,ρU), where d is the download cost, ρS is the amount of shared database (server) common randomness, and ρU is the amount of available user-side common randomness. We show that with a suitable amount of ρU, this new SPIR achieves the capacity of the conventional PIR. As a corollary, single-database SPIR becomes feasible. Further, the presence of user-side ρU reduces the amount of required server-side ρS.