  Publishing trajectory data (individual's movement information) is very
useful, but it also raises privacy concerns. To handle the privacy concern, in
this paper, we apply differential privacy, the standard technique for data
privacy, together with Markov chain model, to generate synthetic trajectories.
We notice that existing studies all use Markov chain model and thus propose a
framework to analyze the usage of the Markov chain model in this problem. Based
on the analysis, we come up with an effective algorithm PrivTrace that uses the
first-order and second-order Markov model adaptively. We evaluate PrivTrace and
existing methods on synthetic and real-world datasets to demonstrate the
superiority of our method.

Cryptography and Security