5
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$
    – Raphael ♦
    Sep 19, 2012 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – The Unfun Cat
    Sep 19, 2012 at 11:35
  • $\begingroup$ @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. $\endgroup$
    – Gilles 'SO- stop being evil'
    Sep 19, 2012 at 12:08
  • $\begingroup$ 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? $\endgroup$
    – The Unfun Cat
    Sep 19, 2012 at 14:58
  • $\begingroup$ 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. $\endgroup$
    – Xodarap
    Sep 19, 2012 at 15:16

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – The Unfun Cat
    Sep 19, 2012 at 15:01
  • 1
    $\begingroup$ @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" $\endgroup$
    – Xodarap
    Sep 19, 2012 at 15:08
  • $\begingroup$ 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. $\endgroup$
    – The Unfun Cat
    Sep 19, 2012 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.