Superstring-Based Sequence Obfuscation to Thwart Pattern Matching Attacks
This addresses user privacy concerns against deterministic attacks, offering a novel, data-independent approach that is incremental in its application to specific privacy threats.
The paper tackles the problem of deterministic user identification via pattern matching in data traces by applying small artificial distortions to ensure each identifying pattern is shared by many users, achieving provable guarantees and demonstrating utility on synthetic and real-world datasets.
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.