New Technology Combines GPS Benefits with Privacy Protection

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

This new tool for developers can help preserve app users' privacy

Citation: New Technology Combines GPS Benefits with Privacy Protection (2007, December 11) retrieved 18 October 2019 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Feedback to editors

User comments

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