“I wasn't there”-Deniable, privacy-aware scheme for decentralized Location-based Services

The use of Location Based Services (LBS) allow mobile users to interact with the environment and query for the location of persons, objects and services. Such applications can be used to get directions to the nearest gas station or point of interest, locate a friend on a map, receive an alert while approaching a traffic accident, get informed about an upcoming social event, and so on. However, the proliferation of LBS systems may undermine user privacy since the frequent collection of location data may reveal considerable information about an individual's daily habits and profile. The challenge therefore is to develop effective security schemes that allow the use of these services in a way that mimics face-to-face private encounters where users can deny what have been said in the meeting. The question then becomes: can we offer a similar service in the LBS setting where users can deny their whereabouts? In this work, we present a decentralized Deniable LBS scheme which gives users the ability to deny being in a particular location even if this location has been monitored by an internal or external party. We discuss the deniability and security properties offered by our solution and perform an evaluation of the system in realistic deployment settings. To the best of our knowledge this is the first work that applies deniability in the LBS setting.