New Technology Combines GPS Benefits with Privacy Protection

December 11, 2007 By Lisa Zyga feature
New Technology Combines GPS Benefits with Privacy Protection
This spatial layout shows how four messages relate to each other, with messages 1, 2, and 4 included in the same cloaking box (solid rectangle) in order to blur the identities of the users. Credit: Bugra Gedik and Ling Liu. ©2007 IEEE.

As GPS and other wireless location-based technologies are becoming prevalent on cell phones and other everyday devices, two researchers are thinking about the social reaction to constant surveillance. As George Orwell envisioned, a world in which everyone is being watched opens the doors for privacy abuse and totalitarian control.

Computer scientists Bugra Gedik and Ling Liu explain that, while an Orwellian society is not right around the corner, location-based technologies have already raised major personal privacy issues. One case in point is DARPA’s LifeLog project, “a massive electronic database of every activity and relationship a person engages in,” which was recently scrapped due to privacy concerns.

Gedik, a researcher at the IBM T.J. Watson Research Center, and Liu, an associate professor at the Georgia Institute of Technology, have recently developed a new technology that could protect cell phone and mobile device users from privacy abuse, while still enabling them to enjoy the benefits that location-based technologies have to offer.

“We need to devise a location anonymization architecture that is both scalable in terms of achieving high anonymization success rate and high accuracy, and robust in terms of protecting users from vulnerabilities and threats of misuse and abuse of their location information,” Liu told, explaining one of the major challenges of developing a location privacy protection system.

While previous attempts at location privacy applications have been made, Gedik and Liu’s system is the first to enable individuals to choose the level of anonymity for different applications, while still providing nearly optimal performance. For example, a cell phone user could send a request for a local gas station offering the most inexpensive gas to a “location-based services” (LBS) provider, and receive an accurate answer even without the provider knowing exactly where the user is located.

Without knowing a user’s location, it would also be impossible for an LBS provider to determine with certainty a user’s identity when using the protective system. This protection is important since, using only location information, curious or malicious providers could conceivably determine information such as a user’s political affiliations, alternative lifestyles, medical problems or the private businesses of an organization such as new business initiatives and partnerships, the researchers explained.

The new system uses an anonymity-based approach called “location k-anonymity.” A user is considered to be location k-anonymous if their location information sent to the LBS provider is indistinguishable from the location information of at least k – 1 other users. In tests, the researchers experimented with k values from 2 to 12, with higher values meaning increased privacy, but also longer search times. In real life, different users could choose different k values for different applications based on their personalized privacy requirements, but the researchers predicted that even the most privacy-conscious users would be satisfied with a k value of 5.

“Most of the privacy-preserving algorithms today work with a system-defined fixed k for all users, and we argue that ‘one-size-fits-all’ k-anonymization approaches are not efficient,” Gedik explained. “Our system is the first one to develop a personalized location anonymization model for a wide range of users with context-sensitive privacy requirements, while maintaining high accuracy through optimal location anonymization.”

Whenever the system receives a message, an algorithm searches for other messages coming from the same general area, and then groups together k or more messages in a geographical rectangle encompassing all the messages. For tuning the system level parameters to obtain close-to-optimal accuracy in practice, the system uses a “trace generator,” which simulates cars moving on roads based on real-world road data.

After the messages are anonymized in this way, the system forwards them to the external LBS providers. In tests, the system processed 50% of messages in less than five seconds, and 75% in less than 10 seconds. Further, the personalized location k-anonymity model had a high success rate, with only about 10% of messages being dropped due to algorithm shortcomings, such as the inability to find other messages sent within the same location.

The scientists will continue working on improving the algorithm, and also studying the quality of location-based services when used under the privacy algorithm in real-world situations.

“Our location privacy project is progressing along three dimensions,” Liu explained. “First, we are working on ways to combine policy-based privacy specification and enforcement with anonymous usage of location information for protecting the location privacy of users and organizations. Second, we are interested in developing a privacy-conscious mobile community for different classes of applications. Third, we are interested in studying different location anonymization techniques in terms of both their ability to balance the level of privacy guarantees and the quality of service, and their resilience to various location-based inference attacks.“

This location privacy project is currently funded by the NSF Cybertrust program.

More information: Gedik, Bugra, and Liu, Ling. “Protecting Location Privacy with Personalized k-Anonymity: Architecture and Algorithms. IEEE Transactions on Mobile Computing, Vol. 7, No. 1, January 2008.

Copyright 2007
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of

Explore further: To Improve smartphone privacy, control access to third-party libraries

Related Stories

Nobody reads privacy policies – here's how to fix that

October 10, 2017

Have you ever actually read an app's privacy policy before clicking to accept the terms? What about reading the privacy policy for the website you visit most often? Have you ever read or even noticed the privacy policy posted ...

Privacy streams helps developers create privacy friendly apps

September 13, 2017

A smartphone app that uses the raw feed from the device's microphone or accesses its contact list can raise red flags for a user concerned about privacy. In many cases, however, the app doesn't need all the details that users ...

Deterring drones from ballparks and botanical gardens

October 13, 2017

To study how an outdoor public space might shoo away unwanted drone aircraft, researchers from Duke University are teaming up with the Durham Bulls and the Sarah P. Duke Gardens to develop a set of affordable and aesthetic ...

Recommended for you

Volvo to supply Uber with self-driving cars (Update)

November 20, 2017

Swedish carmaker Volvo Cars said Monday it has signed an agreement to supply "tens of thousands" of self-driving cars to Uber, as the ride-sharing company battles a number of different controversies.

1 comment

Adjust slider to filter visible comments by rank

Display comments: newest first

2.3 / 5 (4) Dec 11, 2007
The first line of the article claiming that we are all being watched simply isn't true. That's like walking through Times Square and thinking someone is watching you. They aren't.

These guys are using manipulative scare tactics to market their product. Oh, and I'll bet they'll find a market all right. If they are allowed to.

Where in the constitution is our right to locational privacy in a public medium and/or network mentioned? I don't have locational privacy online as I make this post. Is big brother watching me now? I would be a paranoiac if I thought he even existed, much less was watching me.

When I walk down a city street or drive on the highway my locational privacy is available to anyone looking. Perhaps we should invent a device so that people can walk around invisible.

Who is the mythical entity that is going to violate our locational privacy? My network provider? Why not leave it to the individual to dump providers who violate their privacy? I wouldn't stay with my ISP if they sold my information. Free market should be able to handle gross abuses. And if it can't, then it's simple to legislate.

I know its tempting and poplulist to add a new privacy right to the long list we already enjoy, but consider the challenge that already face free democratic societies in dealing with threats from insanely bloody-minded individuals and fanatical groups. Do we really wish to hand out mobile network cloaking devices to those that would destroy the rights and freedoms we have long enjoyed. You know the right not to have bombs to go off on cities buses and the right to get on an airplane and not worry that it might be borrowed to fly into a building.

Who would a locational cloaking algorithm really help? Not you or me or any other non-criminal citizen.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.