# 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 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

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.