All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD4-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.