论文标题
在存在相关性的情况下开发隐私
ON-OFF Privacy in the Presence of Correlation
论文作者
论文摘要
我们制定并研究了on-Off隐私问题。 On-Off隐私算法使用户能够在打开和关闭之间连续切换其隐私。一个明显的例子是Internet浏览器中的隐身模式。但是，除了互联网浏览之外，在大多数在线应用程序中，On-Off隐私可能是所需的功能。面临的挑战是，随着用户在线行为的时间，统计相关性可能会导致信息泄漏。 我们考虑用户有兴趣检索一个n个来源生成的最新消息的设置。随着时间的推移，用户的隐私状态可以在打开和关闭之间发生变化。当隐私在于用户时，想要隐藏他的请求。此外，由于用户的请求取决于个人属性，例如年龄，性别和政治观点，因此它们通常会随着时间的流逝而相关。结果，当隐私范围内，用户不能简单地忽略隐私。我们通过N个州Markov链对用户请求之间的相关性进行建模。目的是设计以最佳下载速率设计查询方案，以在On-Off隐私设置中保留隐私。在本文中，我们介绍了N来源可实现的下载率的内在和外部界限。我们还设计了一种有效的算法来构建实现内部界限并在情况下n = 2来源的最佳性。对于n> 2，找到可以实现它们的启用隐私计划的更严格的外部界限和有效的结构仍然是一个悬而未决的问题。
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.
