k-Unlinkability: A privacy protection model for distributed data

In the past, data holders protected the privacy of their constituents by issuing separate disclosures of sensitive (e.g., DNA) and identifying data (e.g., names). However, individuals visit many places and their location-visit patterns, or “trails”, can re-identify seemingly anonymous data. In this paper, we introduce a formal model of privacy protection, called k-unlinkability, to prevent trail re-identification in distributed data. The model guarantees that sensitive data trails are linkable to no less than k identities. We develop a graph-based model and illustrate how k-unlinkability is a more appropriate solution to this privacy problem compared to alternative privacy protection models.