Intermittent Private Information Retrieval with Application to Location Privacy

We study the problem of intermittent private information retrieval with multiple servers, in which a user consecutively requests one of K messages from N replicated databases such that part of requests need to be protected while others do not need privacy. Because of the correlation between requests, the user cannot simply ignore the privacy for the non-private requests. We start by studying a basic two-requests system where one request is private and the other is non-private. We propose a scheme for any correlation structure between two requests, which concatenates an obfuscation scheme and a standard PIR scheme to prevent leakage when retrieving information for the non-private request. The general problem beyond two-requests would require a specification of the correlation structure. Motivated by the location privacy application, we study the Markov model as the correlation structure. To be concrete, we study the problem in the context of location privacy and we apply the basic two-requests intermittent private information retrieval scheme as a building block to design a location privacy protection mechanism that preserves privacy for locations in the trace level.