About 33 Bits
This is a blog about my research on privacy and anonymity. The title refers to the fact that there are only 6.6 billion people in the world, so you only need 33 bits (more precisely, 32.6 bits) of information about a person to determine who they are.
This fact has two related consequences. First, a lot of traditional thinking about anonymous data relied on the fact that you can hide in a crowd that’s too big to search through. That notion completely breaks down given today’s computing power: as long as the bad guy has enough information about his target, he can simply examine every possible entry in the database and select the best match.
The second consequence is that 33 bits is not really a lot. If your hometown has 100,000 people, then knowing your hometown gives me 16 bits of entropy about you, and only 17 bits remain. But the real danger is that information about a person’s behavior, which was traditionally not considered personally identifying, can be used to cause serious privacy breaches in a variety of different contexts.
This blog will announce, explain and elaborate on my research as it relates to the above theme. I will also use it as an outlet for my opinions on the broader technical, policy, business and social issues related to my work.
15 Comments Add your own
Leave a comment
Trackback this post | Subscribe to the comments via RSS Feed
33 Bits of Entropy 
1.
T | November 29, 2008 at 4:10 am
Hello!
Landed up here through a very strange series of steps (one of them being the fact that your name is the same as another friend of mine who’s doing a PhD).
You say “Part of the reason why I started this blog is in the hope of accelerating this process by reaching out to people outside the computer science community.” but I’m afraid I didn’t understand anything much beyond your about page…
Is there any reading you might recommend otherwise for those outside the community?
Thanks. :)
2.
Arvind | November 29, 2008 at 4:22 am
Hi T,
If you understood the About page, that’s already a step up from normal academic discourse :-)
But yeah, I realize that my posts thus far are a bit heavy on the jargon. I have a few posts of a less technical nature coming soon, I promise!
Meanwhile, there have been a few articles in the press about our work that you should be able to make sense of (example). And here is an article about the AOL search log incident.
3.
Dianne Bltistein Solomon | March 27, 2009 at 6:03 pm
Hi.. I’m a doctoral student at Nova Southeastern Universtiy working on privacy and ecommerce. Just found your blog. What’s the math behind the 32.6 bits?
4.
Arvind | March 27, 2009 at 6:19 pm
It’s the logarithm of the world human population. Please see the definition of entropy. A quantity that has N possible values has an entropy of at most log_2(N) bits, by definition.
5.
george | May 21, 2009 at 9:20 am
I can’t believe that a doctoral student just asked about “the math” behind this. You don’t even need to know about log2 in order to figure this out.
1 bit can hold two values
2 bits can hold four values
how many bits do you need to hold 6 billion values?
One can just start entering powers of 2 in his calculator until his reaches that sum!.
I`m sorry if I come across as bashing but I’m genuinely freaked out.
6.
Arvind | May 24, 2009 at 1:24 am
Relax, she didn’t say she was a computer scientist. It is perfectly reasonable for a non-CS/math/physics person not to be able to figure out entropy without any explanation.
7.
John | August 9, 2009 at 9:32 pm
Great work, very interesting Arvind.
Somewhat unrelated, but I’m hoping someone comes up with a “password meter” that shows actual bits of entropy.
As you are no doubt aware, many folks choose, um, poorly.
http://www.webresourcesdepot.com/10-password-strength-meter-scripts-for-a-better-registration-interface/ has varying levels; some are graphically great, but some call back to servers for parts of their functionality.
I question the algorithms that are used to determine effectiveness; I’m imagining things like the old Pgp versions that used to show a calculated entropy in bits (now you know how I found your site!) in real time, as you typed what you hoped was a good pass phrase.
Thanks, John
8.
Arvind | August 9, 2009 at 9:44 pm
Thanks for your comment. This thread is too getting deep, I’ve replied to you below.
9.
Arvind | August 9, 2009 at 9:43 pm
John,
It would indeed be good to have such a script; at the same time, I think limiting the rate at which an attacker can guess passwords has a far greater effect on password security than making the user choose stronger passwords.
The entropy of a password is only vaguely defined. It can only be measured relative to the algorithm that the attacker is going to use, which of course is unknown. I have a paper on password cracking, which might help explain what I’m talking about.
10.
Lars | November 23, 2009 at 9:37 am
You probably should mention that it is 32.6 distinguished bytes of data. Although this should be clear to anybody ever having heard the term ‘entropy’ in the computer science context, comments above show that this is not the case for all of your readers.
The actual truth is, that you need only 33 bits to encode an unique identity for every person. Needing only 33 bits to identify everyone sounds freakish alarming (considering that my name above in ASCII already takes up 32 bits. But it could be a little more clear, that you need very special 33 bits.
Having said that, I envy you for having had the idea for that title, instead of me that is.
11.
Rob Miles (@robertskmiles) | March 1, 2012 at 9:30 am
33 bits is the mathematical hard limit for the minimum number of bits of data you need to uniquely identify a person. Any amount of *data* that uniquely identifies a single person out of 6.6 billion equiprobable people, transfers 32.6 bits of *information*.
The distinction between ‘data’ and ‘information’ is very important. I could send you a unique identification number in 33 bits of data, or I could send you a full name, date of birth and address in maybe 400 bits of data, and both of those messages would contain 32.6 bits of information for identifying the person.
You can only fit 33 bits of information into 33 bits of data if every single bit eliminates exactly half of the possibilities.
12.
anonymouscat | February 12, 2010 at 3:32 am
Arvind Sahib,
when you say that you only require 33 bits of information and that my hometown contributes 16 or so bits, you are implying that getting more of the relevant bits is as easy as finding my hometown. Also there might only be 6billion humans on this earth but it doesn’t mean we can’t have 6000billion identities, right?
13.
Arvind | February 12, 2010 at 5:15 am
No, I’m not implying that. Entropy is simply a mathematical construct that describes how much information there is to be gained from a piece of data. It says nothing about how easy it is to find data about a person. The fact that is is easy to find auxiliary sources of data in order to determine someone’s identity is an empirical observation.
“Also there might only be 6billion humans on this earth but it doesn’t mean we can’t have 6000billion identities, right?”
That is true; however –
1. unless you make sure your behavior under each identity is completely independent of the others, your various identities can still be tied to each other.
2. the effort needed to create even a single believable alternate virtual identity is too high for most people to bother with.
3. going from 6 billion to 6000 billion identities only increases the entropy requirement from 33 to 43 bits, which is a negligible increase!
14.
Scotto | March 1, 2012 at 3:18 pm
Your 33 bits research is very well illustrated by the following blog post:
Death Note: L, Anonymity & Eluding Entropy
http://www.gwern.net/Death%20Note%20Anonymity
Describes how in the movie Death Note the super detective is able to narrow down the killer from the worlds population to one individual.
PS: Death Note is an interesting Japanese movie.
15.
dsr | March 2, 2012 at 8:00 am
Just to give a bit of information theory background for readers who don’t have much exposure to computer science or mathematics, when we say a “bit” we mean a binary digit–a piece of information that can have one of two values (which we express in binary–the base 2 number system–as 1 or 0). Depending on the context, we often name those value pairs true/false, yes/no, on/off, or high/low, but they can represent any single choice between two options. We can then encode data by representing the choices it took to describe that data.
For example, let’s say we want to represent different types of people using binary. We want to encode whether they are male or female, an American citizen or not, and a native speaker of English or not. I know some people don’t identify as either male or female, but let’s assume for simplicity that the above three parameters all are binary choices. We now want to find out the number of distinct people we can categorize with these three parameters. Since there are two options for each choice, each new choice doubles the number of people we can categorize. So one choice lets us encode 2 people (either male or female). Two choices let us encode 2*2=4 people (either male American, female American, male non-American, or female non-American). Three choices let us encode 2*2*2=8 people (two sets of the above four people, with one set speaking English natively and the other not). We can represent this using exponents as 2^n where n is the number of choices. So when there are three choices we can differentiate between 2^3=8 different people. To see this easily, we can assign each type of person a three-digit binary number, where the first digit represents their gender (0 is male and 1 is female), the second represents if they are American (0) or not (1), and the third represents if they speak English natively (0) or not (1). So we have 000, 001, 010, 011, 100, 101, 110, and 111. These work out to be the binary representations of the base ten numbers 0 through 7, which is a range of eight distinct values. So we know the math worked out. To summarize so far, three binary digits can represent eight different values because three yes/no choices can distinguish between eight different people. In math terms, 2^3=8. Likewise, 2^4=16, so four binary digits can represent 16 different values–the numbers from 0 to 15 or just sixteen different people.
So how did the author of the article know that we would need 33 bits to differentiate between the 6.6 billion people (I think it’s over 7 billion now, but we’ll stick to the data in the article) in the world? Put another way, how many choices between two options must we make to differentiate between 6.6 billion people? Using the math above, we can translate this into the equation 2^x = 6.6 billion, where x is the number of choices or binary digits or bits of information. To solve for x, mathematicians take what’s called the logarithm–the inverse of an exponent. Computer scientists represent the base 2 logarithm with the notation lg. So to use our above examples, to solve for x in 2^x=8, we can say x = lg(8) = 3. In English, that’s “the base 2 logarithm of 8 is 3” or “the number of bits required to represent eight distinct things is 3.” Likewise, lg(16) = 4 and lg(32) = 5.
So getting back to the equation 2^x = 6.6 billion, we can rewrite it as x = lg(6.6 billion), which my calculator gives me as 32.61981887845735. So we’d need 33 bits to represent up to 2^33 = 8,589,934,592 distinct people. Hope that makes this blog accessible to laypeople!