  User privacy can be compromised by matching user data traces to records of
their previous behavior. The matching of the statistical characteristics of
traces to prior user behavior has been widely studied. However, an adversary
can also identify a user deterministically by searching data traces for a
pattern that is unique to that user. Our goal is to thwart such an adversary by
applying small artificial distortions to data traces such that each potentially
identifying pattern is shared by a large number of users. Importantly, in
contrast to statistical approaches, we develop data-independent algorithms that
require no assumptions on the model by which the traces are generated. By
relating the problem to a set of combinatorial questions on sequence
construction, we are able to provide provable guarantees for our proposed
constructions. We also introduce data-dependent approaches for the same
problem. The algorithms are evaluated on synthetic data traces and on the
Reality Mining Dataset to demonstrate their utility.
