ON-OFF Privacy in the Presence of Correlation

We formulate and study the problem of ON-OFF privacy. ON-OFF privacy algorithms enable a user to continuously switch his privacy between ON and OFF. An obvious example is the incognito mode in internet browsers. But beyond internet browsing, ON-OFF privacy can be a desired feature in most online applications. The challenge is that the statistical correlation over time of user's online behavior can lead to leakage of information. We consider the setting in which a user is interested in retrieving the latest message generated by one of N sources. The user's privacy status can change between ON and OFF over time. When privacy is ON the user wants to hide his request. Moreover, since the user's requests depend on personal attributes such as age, gender, and political views, they are typically correlated over time. As a consequence, the user cannot simply ignore privacy when privacy is OFF. We model the correlation between user's requests by an N state Markov chain. The goal is to design query schemes with optimal download rate, that preserve privacy in an ON-OFF privacy setting. In this paper, we present inner and outer bounds on the achievable download rate for N sources. We also devise an efficient algorithm to construct an ON-OFF privacy scheme achieving the inner bound and prove its optimality in the case N = 2 sources. For N > 2, finding tighter outer bounds and efficient constructions of ON-OFF privacy schemes that would achieve them remains an open question.