  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.
