# What's the connection between entropy and deanonymization?

I'm reading this article about how personal information that was anonymaized can usually be re identified. In the article at Theorem 3 the writers talk about entropic deanonymization. I couldn't figure out what that is. So this is basically my question: What is entropic deanonymization?

## Some context and background

Companies like Google/Facebook and many more publish their users data for many reasons, and to keep the private data private, the anonymize the data (remove names, id numbers, address etc.). So then they claim that no ones privacy is harmed. This article say's mainly that it's very compicated to really anonymize the data. So the paper talks about the relation about how much data is published and how much "deanonymization power" you get, Theorem 1 makes the first binding between m the amount of data published and how good the dataset can be deanonymized. Theorem 2 talks about the same when you have a sparse dataset, like most real world datasets. Theorem 3 is talking about entropy somehow, and this is where is started wondering what entropic deanonymization is. Later they talk about what you do when only a subset is published (after anonymization) and later on they show results from the Netflix prize - a real competition where this technique was used.

## Edit

Just for clarity: The author didn't use the phrase entropic deanonymization. It's a semantic conversion I did, because it was never given a name. Sorry if that's misleading as pointed out in the comments. So my question rephrased: What entropy has to do with deanonymization?

• 1. Please give a pointer to a free version of the paper (not behind a paywall). I'm pretty sure you can find one -- but you should spend the effort finding it, not me. That will increase the chances that someone gives you a helpful answer. 2. What have you tried to understand that part of the paper on your own? Questions of the form "please explain this part of the paper to me" are often a less-than-ideal fit for this site, as this site is for research-level questions. – D.W. Dec 26 '13 at 22:09
• 1. I'm sorry - updated (Didn't notice the paywall cause from an university computer you just get the article). 2. I think that this is an expression that is used generally, not only in this article. So my question is about what is meant by entropically deanonymization not how it fits into the article. – Ramzi Kahil Dec 26 '13 at 22:16
• This question is misleading. Nowhere do the authors use the phrase "entropically deanonymization". You claim in the comments that this expression is used generally, but I've never heard anyone else use this phrase. Would you care to provide some citations for other papers that you've found that use that phrase? And have you read them? – D.W. Dec 26 '13 at 22:30
• @D.W. I edited the question. Hopefully it's better now. – Ramzi Kahil Dec 27 '13 at 9:07
• could you please write "entropic deanonymization". the phrase is ungrammatical as you write it – Sasho Nikolov Dec 27 '13 at 9:13

## 1 Answer

If you read the paper carefully, you will find a discussion about using entropy as a metric for the degree of anonymity (see Section 3). In particular, if the conditional entropy of a certain random variable is too low (conditioned on the information available to the adversary), then the adversary has narrowed down the value of the supposedly-anonymized information to a small set of plausible values -- so anonymity is poor. The paper makes this formal. For instance, see Definition 4 and the surrounding discussion.

Read the paper. Carefully. The whole paper.

And, by the way, nowhere do the authors use the phrase "entropically deanonymization". That is a phrase you have invented, not one found in the paper.