by Andreas Konstantinidis, Georgios Chatzimilioudis and Demetrios Zeinalipour-Yazti (University of Cyprus)
Internet-based Indoor Navigation (IIN) services have recently received considerable attention, mainly because GPS technology is unavailable in indoor spaces and consumes considerable energy. On the other hand, predominant Smartphone OS localisation subsystems currently rely on server-side localisation processes, allowing the service provider to know the location of a user at all times. We have devised an innovative algorithm for protecting users from location tracking by the localisation service, without hindering the provision of fine-grained location updates on a continuous basis. Our proposed Temporal Vector Map (TVM) algorithm allows a user to accurately localise by exploiting a k-Anonymity Bloom (kAB) filter and a bestNeighbors generator of camouflaged localisation requests, both of which are shown to be resilient to a variety of privacy attacks.
People spend 80-90% of their time in indoor environments, including shopping malls, libraries, airports and university campuses. The omni-present availability of sensor-rich mobiles has boosted interest in a variety of indoor location-based services, such as in-building navigation, inventory management, marketing, and elderly support through ambient and assisted living. To enable such indoor applications in an energy-efficient manner and without expensive additional hardware, modern smartphones rely on cloud-based Internet-based Indoor Navigation (IIN), which provide the accurate location (position) of a user upon request [1]. There are numerous IIN, including Skyhook, Google, Indoo.rs, Wifarer, Navizon, IndoorAtlas, ByteLight and our open-source in-house Anyplace (http://anyplace.cs.ucy.ac.cy/) service. These systems rely on geolocation databases (DB) containing wireless, magnetic and light signals, upon which users can localise.
At the University of Cyprus, we appreciate the benefit of indoor location based services (LBS) and our goal is to facilitate their wide acceptance [2]. At the same time, we feel that location tracking by IIN poses a serious imminent privacy threat, which will have an even greater impact than other existing forms of location tracking (i.e., outdoor GPS tracking or browser-based location tracking). This holds as IIN can track users at very fine granularity over an extended period of time.
We are developing hybrid techniques that on the one hand exploit the IIN utility, but on the other hand also offer controllable location privacy to the user. Particularly, we tackle the technical challenge of providing continuous localization to a mobile user u that can measure the signal intensity of its surrounding Access Points, with minimum energy consumption on u, such that a static cloud-based server s cannot identify u’s location with a probability higher than a user-defined preference pu. We devise the Temporal Vector Map (TVM) algorithm [3], where a user u camouflages its location from s, by requesting a subset of k entries from s, where k is a user-defined constant. To understand the operation of TVM at a high level, consider Figure 1. An arbitrary user u moves inside building A, using the TVM smartphone application shown in Figure 2. While u requests reference locations from s pertinent to building A, it also requests reference locations related to arbitrary other buildings B and C. Particularly, u uses a hashing scheme that makes sure that for a given user-preference k = 3, s will not be able to distinguish u’s request from requests made by k−1 arbitrary other users u′ and u′′. Under reasonable assumptions about the scope of IIN, we show that s can know u’s location only within pu, even while u is moving. Particularly, the TVM algorithm operates in two phases as outlined below.
Figure 1: Indoor localisation of user u using the cloud-based IIN s. During the localisation, u requests k−1 camouflaged locations using the TVM algorithm, such that s can know the location of u only with probability 1/k
Figure 2: Our TVM prototype implemented in Android OS.
In Phase 1 of TVM, u computes a k-Anonymity Bloom (kAB) filter structure, which provides location privacy for snapshot localization tasks. When u needs continuous localisation (e.g., as u moves), the kAB of Phase 1 itself is not adequate to preserve the privacy of u, since by issuing k independent requests, s can realise by exclusion that there are k − 1 invalid requests (as one of the requests will always relate to the real building A). This allows s to deterministically derive u’s real location.
To circumvent the above problem, in Phase 2 of TVM, u uses the bestNeighbors algorithm to issue a set of camouflaged localisation requests that follow a similar natural movement pattern to that of u (i.e., dotted circles in Figure 1). This provides the illusion to s that there are k other possible users moving in space, thus camouflaging u among k other users. Since our TVM algorithm transfers only a partial state of the database from s to u, it requires less network traffic and smartphone-side energy than current privacy-aware approaches that transfer the complete database to u prior the localisation task.
TVM is resilient to the (i) linking attack: the only uniquely identifying attribute is the fingerprint of a user’s location. In fact, this is also the only attribute sent by the user to the server, therefore there are no other attributes that could link to the user’s fingerprint value; and (ii) the homogeneity attack: there is an inherent diversity in the resulting k-anonymous set of TVM, since it uses hashing to generate a set of unique access point MAC values that has a uniform distribution over all values, and therefore, no information can leak due to lack of diversity in the sensitive attributes.
Links:
http://tvm.cs.ucy.ac.cy/
http://dmsl.cs.ucy.ac.cy/
References:
[1] Zeinalipour-Yazti, et. al.: “Internet-based Indoor Navigation Services”, IEEE Internet Computing, 2016.
[2] G. Chatzimiloudis, et. al.: “Crowdsourcing with Smartphones”, IEEE Internet Computing, Volume 16, 2012.
[3] A. Konstantinidis et. al.: “Privacy-Preserving Indoor Localization on Smartphones”, IEEE TKDE, Volume 27, Pages: 3042-3055, 2015.
Please contact:
Demetrios Zeinalipour-Yazti
University of Cyprus
+357 22 892755
