Communication Cost of Two-Database Symmetric Private Information Retrieval: A Conditional Disclosure of Multiple Secrets Perspective
This work addresses communication efficiency in private data retrieval for users and databases, presenting an incremental improvement through a novel equivalence and scheme design.
The paper tackles the problem of minimizing total communication cost in two-database symmetric private information retrieval (SPIR) by relating it to conditional disclosure of secrets (CDS) and introducing conditional disclosure of multiple secrets (CDMS). It determines the exact minimum total communication cost for SPIR with 2 databases and 3 messages, achieving a specific numerical result.
We consider the total (upload plus download) communication cost of two-database symmetric private information retrieval (SPIR) through its relationship to conditional disclosure of secrets (CDS). In SPIR, a user wishes to retrieve a message out of $K$ messages from $N$ non-colluding and replicated databases without learning anything beyond the retrieved message, while no individual database learns the retrieved message index. In CDS, two parties each holding an individual input and sharing a common secret wish to disclose this secret to an external party in an efficient manner if and only if their inputs satisfy a public deterministic function. As a natural extension of CDS, we introduce conditional disclosure of multiple secrets (CDMS) where two parties share multiple i.i.d.~common secrets rather than a single common secret as in CDS. We show that a special configuration of CDMS is equivalent to two-database SPIR. Inspired by this equivalence, we design download cost efficient SPIR schemes using bipartite graph representation of CDS and CDMS, and determine the exact minimum total communication cost of $N=2$ database SPIR for $K=3$ messages.