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!

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.

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.

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!

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.

Thanks for your comment. This thread is too getting deep, I’ve replied to you below.

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.

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

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.

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.

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.