| Paper ID | D4-S6-T4.1 |
| Paper Title |
On the Capacity of Latent Variable Private Information Retrieval |
| Authors |
Islam Samy, Mohamed Attia, Ravi Tandon, Loukas Lazos, University of Arizona, United States |
| Session |
D4-S6-T4: Private Information Retreival II |
| Chaired Session: |
Thursday, 15 July, 23:40 - 00:00 |
| Engagement Session: |
Friday, 16 July, 00:00 - 00:20 |
| Abstract |
In latent-variable private information retrieval (LV-PIR), a user wishes to retrieve one out of $K$ messages (indexed by $\theta$) without revealing any information about a sensitive \textit{latent} attribute (modeled by a latent variable $S$ correlated with $\theta$). While conventional PIR protocols, which keep $\theta$ private, also suffice for hiding $S$, they can be too costly in terms of the download overhead. In this paper, we characterize the capacity (equivalently, the optimal download cost) of LV-PIR as a function of the distribution $P_{S|\theta}$. We present a converse proof that yields a lower bound on the optimal download cost, and a matching achievable scheme. The optimal scheme, however, involves an exhaustive search over subset queries and over all messages, which can be computationally prohibitive. We further present two low-complexity, albeit sub-optimal, schemes that also outperform the conventional PIR solution.
|
