Optimal Local Bayesian Differential Privacy over Markov Chains

In this paper, we focus on data generated from a Markov chain and provide optimal mechanisms for local Bayesian differential privacy (BDP) guarantees. Our main theoretical contribution is to provide 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 perform experiments on synthetic data to show that a correlation aware adversary can launch successful attacks on data that satisfies only the vanilla differential privacy guarantees. Finally, we perform experiments on real data to show that our privacy guarantees are robust to underlying distributions that are not simple Markov chains.