In the literature of data privacy, differential privacy is the most popular model. An algorithm is differentially private if its outputs with and without any individual's data are indistinguishable. In this paper, we focus on data generated from a Markov chain and argue that Bayesian differential privacy (BDP) offers more meaningful guarantees in this context. Our main theoretical contribution is providing a mechanism for achieving BDP when data is drawn from a binary Markov chain. We improve on the state-of-the-art BDP mechanism and show that our mechanism provides the optimal noise-privacy tradeoffs for any local mechanism up to negligible factors. We also briefly discuss a non-local mechanism which adds correlated noise. Lastly, we perform experiments on synthetic data that detail when DP is insufficient, and experiments on real data to show that our privacy guarantees are robust to underlying distributions that are not simple Markov chains.
翻译:在数据隐私的文献中,差异隐私是最受欢迎的模式。 如果一种算法的输出与任何个人的数据不相容,那么这种算法就具有差异性。在本文中,我们侧重于从Markov链条中产生的数据,并辩称Bayesian差异隐私在这方面提供了更有意义的保障。我们的主要理论贡献是在从二进制Markov链中提取数据时为实现BDP提供一种机制。我们改进了最先进的BDP机制,并表明我们的机制为任何本地机制提供了最佳的噪音-隐私交换,直至可忽略不计的因素。我们还简要讨论了增加相关噪音的非本地机制。最后,我们在DP不足时对合成数据进行实验,并试验实际数据,以表明我们的隐私保障对于并非简单的Markov链条的基本分布是强大的。