Technical Program

Paper Detail

Paper Title Single-Server Single-Message Online Private Information Retrieval with Side Information
Paper IdentifierMO3.R3.1
Authors Fatemeh Kazemi, Esmaeil Karimi, Anoosheh Heidarzadeh, Alex Sprintson, Texas A&M University, United States
Session Private Information Retrieval I
Location Monge, Level 3
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 14:30 - 14:50
Manuscript  Click here to download the manuscript
Abstract In many practical settings, the user needs to retrieve information from a server in a periodic manner, over multiple rounds of communication. In this paper, we discuss the setting in which this information needs to be retrieved privately, such that the identity of all the information retrieved until the current round is protected. This setting can occur in practical situations in which the user needs to retrieve items from the server on a periodic basis, such that the privacy needs to be guaranteed for all the items that have been retrieved until the current round. We refer to this setting as \emph{online private information retrieval} in that the user does not know the identities of the future items that need to be retrieved from the server. Following the previous line of work by Kadhe \emph{et al.}~we assume that the user knows a subset of $M$ messages in the database as side information. The identities of these $M$ messages are initially unknown to the server. Focusing on scalar-linear settings, we characterize the \emph{per-round capacity}, i.e., the maximum achievable download rate at each round. In particular, we show that for the setting with $K$ messages stored at the server, the per-round capacity of the scalar-linear setting is ${C_1= ({M+1})/{K}}$ for round $i=1$ and ${C_i= {(2^{i-1}(M+1))}/{KM}}$ for round $i\geq2$, provided that ${K}/({M+1})$ is a power of $2$. The key idea of our achievability scheme is to {combine} the data downloaded during the current {and previous} rounds with the original side information {and use the resulting data as} side information for subsequent rounds.