 |
VOOZH | about |
|
VOOZH | about |
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.
1.
👁 T's avatar
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. :)
3.
👁 Dianne Bltistein Solomon's avatar
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?
Reply5.
👁 george's avatar
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.
Reply10.
👁 Lars's avatar
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.
Reply11.
👁 Rob Miles (@robertskmiles)'s avatar
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.
Reply12.
👁 anonymouscat's avatar
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?
14.
👁 Scotto's avatar
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.
Reply15.
👁 dsr's avatar
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!
ReplyTrackback this post | Subscribe to the comments via RSS Feed
Leave a comment Cancel reply