# Anonymization of dataset preserving unique identities

The $k$-anonymization paradigm (and its refinements) means to create datasets where every tuple is identical with $k-1$ others.

However I'm in a situation where people are in the dataset many times. And I want to follow their progress through the health care system, so I need to know who is who. If I give each person a unique ID, which is necessary in this situation, a linking attack from within the table is possible!

Does anyone know of any relevant theory or have attempted to deal with similar problems?

I'm inclined to think it is impossible to give any good guarantee of anonymity in this situation.

This will possibly be used for my MSc thesis topic.

• Welcome! Using material from Stack Exchange for academic work is certainly fine. You should cite answers you use just like you would cite a paper, though (check "share" and then "cite" on a post on Theoretical Computer Science for how to cite SE posts). – Raphael Sep 19 '12 at 10:46
• Might this be a more fitting question for "cs-theory" as it deals with topics that are likely not discussed in any literature? I am unsure. – The Unfun Cat Sep 19 '12 at 11:35
• @TheUnfunCat I'm not sure about Theoretical Computer Science. Some of the mods from there frequent this site, if they think this question would get better answers on CSTheory we can migrate it. Privacy is a delicate topic, where as far as I know there's a huge gap between theory and practice. I would suggest that you engage with folks on the practical side. These folks frequent Information Security, which has an active chatroom. – Gilles 'SO- stop being evil' Sep 19 '12 at 12:08
• Thanks for all your help mods. Looking at the ITSecurity page I suspect it would get more answers there. What do I need to do to suggest to move it? – The Unfun Cat Sep 19 '12 at 14:58
• Unfortunately, I think k-anonymity is rarely met in practice. So at least in theory this is the right site for it, though you might end up with better answers elsewhere. – Xodarap Sep 19 '12 at 15:16

## 1 Answer

The point of k-anonymity is that you can't uniquely identify your patients. So I will rephrase your question:

Given two anonymized tuples $x$ and $y$, can we tell if they are anonymizations of the same person?

Let's suppose for purposes of contradiction that we could. Then this means there is a "meta-tuple" which uniquely identifies a patient. But this violates anonymity (unless $k=1$). So it is impossible.

• You are right, however I want to know if there are known methods of making the data as anonymous as possible or existing theory related to the problem. Still, UV. – The Unfun Cat Sep 19 '12 at 15:01
• @TheUnfunCat: Are you interested in general methods with k-anon data sets, or are you specifically interested in the problem of de-duplicating a k-anonymous list? If it's the latter, try searching for "anonymous identification" – Xodarap Sep 19 '12 at 15:08
• De-duplication and record linkage seem like promising search terms, thanks! Never seen them once in the literature. I see that my mentioning of k-anonymity in the beginning was more confusing than helpful. I was trying to point out that meeting those requirements was impossible in my case and I needed pointers to new theory. – The Unfun Cat Sep 19 '12 at 15:19