<p>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.</p>

<p>Read the paper.  Carefully.  The whole paper.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2013-12-26T22:35:31.493Z
2013-12-26T22:35:31.493Z
D.W.
<p>I'm reading <a href="http://www.cs.utexas.edu/~shmat/shmat_oak08netflix.pdf" rel="nofollow">this article</a> about how personal information that was anonymaized can usually be re identified. In the article at Theorem 3 the writers talk about <code>entropic deanonymization</code>. I couldn't figure out what that is. So this is basically my question: What is entropic deanonymization?</p>

<h2>Some context and background</h2>

<p>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 <code>m</code> 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 <code>entropic deanonymization</code> 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.</p>

<h2>Edit</h2>

<p>Just for clarity: The author didn't use the phrase <code>entropic deanonymization</code>. 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?</p>

CC BY-SA 3.0
2013-12-26T22:09:34.450Z
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.
CC BY-SA 3.0
2013-12-26T22:16:52.637Z
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
CC BY-SA 3.0
2013-12-26T22:30:59.133Z
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.
CC BY-SA 3.0
2013-12-27T09:07:25.230Z
@D.W. I edited the question. Hopefully it's better now.
Ramzi Kahil
CC BY-SA 3.0
2013-12-27T09:13:43.933Z
could you please write "entropic deanonymization". the phrase is ungrammatical as you write it
Sasho Nikolov
<ir.information-retrieval><privacy>
What's the connection between entropy and deanonymization?
Ramzi Kahil
# What's the connection between entropy and deanonymization?

(Asked by: username_0 on 2013-12-26)

I'm reading [this article](http://www.cs.utexas.edu/~shmat/shmat_oak08netflix.pdf) 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?

**Tags:** ir.information-retrieval, privacy
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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?  
> **username_0**: @D.W. I edited the question. Hopefully it's better now.  
> **username_2**: could you please write "entropic deanonymization". the phrase is ungrammatical as you write it  

---

## 1 answers

### Answer by username_1 on 2013-12-26. Score: 5

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.


---

