"Anonymous" Location Data Problems - Computerphile

Key Takeaways

i think that everybody has been asked at least once to share their data with a company under the promise that the data is anonymous so the problem is that the data that is collected is very rarely truly anonymous and this is what i'm gonna explain today first of all the intuition of why this is true is that data that is supposedly anonymous can often be re-identified and a very good example of this was given by an article of the new york times which was published i think about one year ago where the journalists could get their hands on a big data set a big location data set about 12 billion and 12 million americans uh so the way this uh data set looks like is basically that uh there are different users so like let's say bob alice carlos and so on and for each of these users there is a series of location and data points so for example for bob we have t1 and l1 so time one and location one and so on teach you and so on and the same for alice and carlos and all the users and of course like we can represent this on a map as a trajectory so we have the first point for bob which would be t1 l1 and i don't i don't know like maybe this could be that you know bob was at madison square garden like you know yesterday at 8pm something like that then bob goes to t2 l2 and we have a record for that and so on and we have of course all of this for all the users in the data set now actually the data set that the new york times journalists could get access to did not have the names in it it was what we say is pseudonymous we can consider this like kind of anonymous but however uh the uh the journalists nevertheless could reidentify some people in this data set and follow their movements and actually some of the people who were reidentified were some collaborators of the u.s president so now the question is uh how did they do it how was it possible for them to identify this data set even though the names were not in it and the intuition of how you could do this is to use some background information about the person that you are trying to identify and use it to match it against the records and the trajectories in the data set so this is precisely the idea behind a study that was published in 2013 by some researchers which studied this fact from a more formal point of view so what the researchers did was to define a metric unicity which we call epsilon p which is defined as the fraction of users in the data set that are unique given p points so at this point we're using this metric they took a data set a location data set very similar to the one of the the new york times so a location data set about uh one and a half million people uh observed over a period of i think 15 months or something like that and they computed the unicity values on this data set and what they found was that epsilon 4 was 95 this means that 95 of the times only four points are necessary to uniquely identify an individual in the data set so in other words if you know you know like where i live where i work uh where i had dinner yesterday and uh maybe where i go to train in the in the weekend then most of the times these are enough to uniquely identify my trajectory in the data set and once you can find my trajectory you can see all the other places that i've been visiting for the past 15 months this study uses a pretty simple attack setting right so basically the adversary is assumed to have access to four points about the the target the victim and uses these four points directly to match them against the data in the data set so okay this is a this is a a potential a potential setting and but you could think of um more complex attack settings for example you could you could assume that the the background information that is available to the adversary uh is actually referred to a period which is different previous to the one of the data set that you are trying to reidentify we can suppose that we have two data sets one from 2018 this data set also contains the names so you know that this one is bob this one is alice the third one is carlos and so on so you have the location trajectories plus the names then you have another data set from 2020 which has again you know all the uh trajectories of all the users and so on but in this case you do not have the names you just have some pseudonyms so for example this is user one user two user three and so on now for simplicity we can also assume that the two data sets contain the same users so we can write this but we do not know which users correspond to which ones right so it might be for example that bob is u3 and alice is u1 and carlos is u2 so the attacker doesn't know this but the the aim of the attacker is precisely to find out the correct maxim between the users in the 2018 data set and the users in the 2020 data set in this case we cannot uh use the the method that we we used before right because if we try to match the points in in the data set on the left with the points in the data set of the right we find no matchings because the time periods that uh this refers to are exactly there is no overlap exactly so we need to find something more more clever and one possible way to approach to approach this problem is to proceed with two steps the first step is to find a similarity score between all the users and the second step is to use all these this scores that we have computed in order to find a good global matching between all the users on the left and all the users on the right so we have here matching so i will go now a little bit more in detail for these two steps i will assume for simplicity that there are only three users in each data set of course this is a an oversimplified setting right but it's just to to make things clearer the first step is to find similarity scores between users what you do would be to take alice's record and you once record and you compute the similarity score between these two and you maybe you find you know like that this is a 26 percent then you do the same between alice and u2 and you find that this is i don't know 35 then ali send you three and you find 87 so you know like in this case it looks quite likely that uh alice and u3 actually are the same the same person but it's not always so easy you know like because the problem is that now you have to do the same also for bob and u1 two and three and carlos and you want u2 and your three and sometimes it's quite clear which one is the right match but sometimes it's not that clear so now the main question for this step is how do we compute the similarity between two trajectories so there are a lot of ways to do this one simple one for example here for alice we compute the set of preferred locations so the locations that alice visits the most often and we do the same for u1 and then we compare them and the idea is that uh if the two sets of preferred location kind of overlap then probably this is a good match and of course like this might not always work right i mean maybe alice changed the workplace or maybe that italian restaurant that she used to love had to close down because of brexit whatever but the idea is that on average if the overlapping is good enough then probably the the matches is a correct okay so and so this this is the first step the second step is the matching so now we have all the scores between the users but we need to find what is the correct matching so here the idea is to select the matching that maximizes the overall similarity between users what you can do is to try all possible matchings and compute the similarity scores for that so for example we can start from this very simple matching in the same order we compute the similarity score for this one and we proceed with the next matching so maybe we can do this one we do this this and this and we compute the similarity matrix so this would be like similarity one similarity score two of course this is the similarity again for all the uh like the sum of all the similarities score for for all the the users and we proceed like this for all the matchings now the problem is that uh this strategy works uh in theory but it doesn't work in practice if the data set is uh too big and actually it doesn't have to be all that big because you know for those of you who love combinatorics you can see that the number of all possible matchings that you have to try is n factorial where n is the number of users in the data set if n is just three users then three factorial is just six so this is totally doable but if the number of users is one thousand for example then one thousand factorial is a huge number it takes i think 2 500 digits just to be written down so basically you know computing the global similarity for 1000 users in this way would be would take forever it would take like you know millions and millions of years so we cannot do that um fortunately at least for the attacker there is uh there is a there are well-known algorithms that do precisely this so they compute a maximum weight maximum matching in in an efficient way so one such algorithm is the hungarian algorithm i will not go into the details of this algorithm because you know like it's quite complex uh but you can find some very good uh videos online if you're if you're interested so basically once you once you have this similarities course you use the hungarian algorithm to find the the maximal matching the the most most likely matching and you use that matching as a guess for uh the identification of the the users in the in the 2020 data set and this attack uh works pretty pretty well at least when the data set is not too big so a few thousand users uh but there are you know like other solutions that are more robust and like you know work also for for uh bigger data sets so uh i hope i gave an idea of why you know anonymous data can often be re-identified so i talked about location data but actually these kind of attacks work for most types of um of a behavioral data so all social networks and so on credit card data so now one when you when you see this these attacks you could think that it's really impossible to to share data to analyze data without compromising uh privacy and this is actually a problem because you know sometimes you do want to uh give the possibility to analyze data so for example you know uh you might want to to be able to share uh health data for medical research but actually i mean there are there are a lot of examples of how to how one can use data for uh for good um so the good news is that uh some i mean many researchers and cryptographers are you know developing technologies that allow precisely to analyze data without compromising the privacy of the individuals who who contribute with their data but this is for another video and then down here for each of the value as i'm writing it out i go round in a loop around the amount of stretches i want and i basically add in new data so if i'm going from this point to this point any device which is keeping track of time in that way we'll get really confused and we basically get