Location Privacy in Mobile Systems:  A Personalized Anonymization Model

Ling, Gedik
 

The paper describes a way of protecting location privacy for users of mobile
systems.   When you use a mobile system, which may include a GPS or
otherwise be trackable (via cell region), a service provider can identify
where you are, and so can "adversaries" who intercept information sent by
users.  Suppose a married man goes at 9pm to a part of town where there are
a lot of brothels and bars, and uses his cell phone to access the Internet.
The service provider may then be able to record his name and where he was at
that particular time.  Such a man may not want that information known.  The
paper describes a way to protect his privacy, providing him k-anonymity.  By
the paper's technique, the man can choose a number k, such that the service
provider 

 

To give k-anonymity, the technique lumps together k people within a space,
like a cube, and within a time period.  In this way, an adversary cannot pin
down the identity of a certain person within the group; it can only
determine that there is a group of k people, and one person from that group
is at the particular location/time.  So, if the man's wife were the
"adversary," and she wanted to know if he had visited a bar at a certain
time, she could only make inferences based on information about k people who
were around the bar at that time.   The service that's provided by the
service provider can only be tailored to the time and place of the service
requester to the extent of the size of the space/cube and the length of the
time period.  If the space has to be large to have k people in it, the
service becomes less specific to the particular place where the requester is
located.  If the temporal time slot is long to encompass k people within it,
the service may be provided to the requester at some time significantly
later than when he requested it.  This is the price paid by the requester
for the k-anonymity.  If he requests k=10 anonymity, and to find 10 people
in the area/time associated with the requester you have to increase the size
of the cube to 1 cubic mile, then the service provided cannot be more
specific than 1 cubic mile; if he requests a "nearest restaurant," the
service may give dozens of restaurants within the cubic mile region, instead
of just 2 or 3 that are on the same block where the requester is.  The
paper's technique allows the user to specify the maximum temporal and
spatial resolutions he will tolerate; if k-anonymity can't be supplied,
given those resolutions, the service informs the user that it can't provide
the service.  

 

The message perturbation engine described in the paper performs the
spatio-temporal cloaking and also removes the identity of the user.

 

I think the way this works is as follows.  Suppose a wife is trying to
identify whether her husband visits a brothel somewhere.  She knows he
regularly uses a certain LBS to check the weather, whenever he drives
anywhere.  Every night he goes out at 10pm and comes back at 12, saying he
goes to play poker with his friends on the opposite side of town from the
brothel.  She snoops somehow, between 10 and 12, on the location of people
who use the weather service.  If, one night, she found that there was just
one use of the weather LBS from the brothel parking lot (or on the route to
it from their house), and none from the route to the poker game house, she
could conclude where her husband had been.  But, if all she could determine
was that 50 people in the general area of the brothel used the service, and
49 people in the general area of the poker game used it, she couldn't
conclude anything.