Optimized Secure Position Sharing with Non-trusted Servers
Pavel Skvortsov Björn Schembera Frank Dürr Kurt Rothermel





 


Institute of Parallel & Distributed Systems (IPVS), Universität Stuttgart 

Universitätsstrasse 38, 70569 Stuttgart, Germany 
 Tel.: +4971168565802; Fax: +4971168565832
skvortsov@hlrs.de, schembera@hlrs.de, frank.duerr@ipvs.uni-stuttgart.de, kurt.rothermel@ipvs.uni-stuttgart.de



Today, location-based applications and services such as friend finders and geo-social networks are very popular.


However, storing private position information
on third-party location servers leads to privacy problems. 
In our previous work, we proposed a position sharing approach for secure management of positions on non-trusted
servers <cit.>, which distributes 
position shares of limited precision among servers of several providers. 


In this paper, we propose two novel contributions to improve the original approach.
First, we optimize the placement of shares among servers by taking
their trustworthiness into account. 

Second, we optimize the location update protocols to minimize the number of messages
between mobile device and location servers. 




















Location-based service location privacy obfuscation position sharing map-awareness
location update placement






§ INTRODUCTION


Driven by the availability of positioning systems such as GPS, powerful smartphones such as the iPhone or Google
Android phones, and cheap flat rates for mobile devices, location-based services enjoy growing popularity.
Advanced location-based applications (LBAs) such as friend finders or geo-social networks
are typically based on location server (LS) infrastructures that store mobile user positions to ensure scalability
by enabling the sharing of user positions between multiple applications. This principle relieves the mobile device
from sending position information to each LBA individually. Instead, the mobile device updates the position
at the LS, and LBAs query the LS for the positions of mobile objects.

Although certainly useful from a technical point of view, storing data on LSs raises privacy concerns if
the LSs are non-trusted. Multiple incidents in the past have shown that
even if the provider of the LS is not misusing the data, private information can be
revealed due to attacks, leaking, or loss of data <cit.>.
Therefore, the assumption of a trusted LS is questionable, and technical concepts are needed
to ensure location privacy without requiring a trusted third party (TTP). 

Various location privacy approaches have been proposed in the literature. Many approaches such as k-anonymity
(e.g., <cit.>), rely on a TTP and are, therefore, not applicable to non-trusted environments. Approaches without
the need for a TTP mainly rely on the concept of spatial obfuscation, i.e., they reduce the precision of
position information stored on the LS. However, this severely impacts the quality of service of LBAs
since they can only be provided with coarse-grained positions, depending on the degree of obfuscation. 

To solve this conflict between privacy and quality of service, we have proposed the concept of position sharing in our
previous work <cit.>. 
The basic idea of this concept is to split up the precise user position into position shares of limited precision.
These shares are distributed among multiple LSs such that each LS has a limited, coarse-grained
view onto the user position. LBAs are provided with access rights to a certain number of shares on different LSs. By using share
fusion algorithms, a position of higher precision can be calculated. Therefore, LBAs can be provided with different,
individual precision levels (privacy levels) although each LS only manage less precise information. This approach does
not require a TTP. Furthermore, it provides graceful degradation of privacy, where no LS is a single point
of failure with regard to privacy. Instead, the precision of positions revealed to an attacker increases with
the number of compromised LSs.



The concept of position sharing can be applied to various settings and use cases.
For instance, it can be used to implement a secure personal data vault for location information
of individual users over a non-trusted server infrastructure. The concept of a personal data vault has been
first proposed in <cit.>. A data vault is a data repository controlled by the user for storing personal
data and controlling the accessed to data from different services. With the advent of cloud computing, it seems
to be attractive to implement data vaults atop cloud computing infrastructures, relieving the user from operating
her own dedicated servers. However, the providers of these cloud infrastructures might be non-trusted. Position
sharing offers the possibility to avoid storing all location data of the data vault at a single provider.
Instead, the data vault can be distributed among servers of different cloud providers, where each provider
only has a well-defined limited view onto the personal location information.

As another use case for position sharing, consider a startup company that wants to provide location-based
services to its customers. However, as typical for many startups, the startup company does not own a dedicated
server infrastructure but instead utilizes an infrastructure as a service (IaaS) of a third-party IaaS provider.
Assume that the customer trusts the startup company to handle his private location information securely. However,
although the customer trusts the startup company, this does not imply that the startup company trusts the IaaS
provider operating the physical servers. Position sharing enables the startup company to distribute its valuable
private customer data to several third-party IaaS providers to avoid a single point of failure and provide a
trustworthy virtual service to its customers over non-trusted IaaS infrastructures. 


In this work, we present two novel contributions to extend the original position sharing approach:
(1) an algorithm for optimizing the placement of position shares on location servers of different
trustworthiness; (2) optimized share update protocols that significantly reduce the communication
overhead of the original approach.

In our previous approach, we made the simplified assumption that every LS provider is
equally trustworthy, i.e., each LS has the same risk of being compromised.
However, a user might trust certain providers such as big companies with good reputation more
than others. Therefore, it seems reasonable that LSs of providers of higher
trust levels should store more precise information, i.e.,
either position shares of higher precision or more shares.


For instance, in the examples above IaaS providers operated by companies like Google, Microsoft
or Amazon might be considered more trustworthy than servers of a cheaper but not so well-known
IaaS providers. Still it might be reasonable to utilize such cheaper providers for
monetary reasons. With our extended position sharing approach, we can balance the risk
of revealing data by considering the individual trustworthiness of providers.

Therefore, the first contribution of this paper is an improved position sharing approach that takes individual trust levels
of LS providers into account. To this end, we optimize the placement of shares on LSs
to increase the protection of privacy. We propose a suitable privacy metric and scalable share placement
algorithms that (a) flexibly select n of LSs, and (b) balance the risk
among providers such that the risk of disclosing private information stays
below a user-defined threshold. Moreover, we aim to meet the user-defined privacy requirements with a
minimum number of LSs to minimize the overhead of updating and querying several LSs.


Moreover, in our previous work we did not consider 
how multiple position updates affect the communication overhead. 
This factor can negatively affect the scalability of our approach, since each update includes n messages (where n
is the number of LSs). Therefore, as the second contribution
of this paper, we propose a position update algorithm which improves scalability by minimizing the number of transmitted messages
and does not change the user's desired location privacy levels. This improvement is achieved by omitting updates of shares
that can remain unchanged after the given position change.



Our evaluations show that the proposed method can save up to 60% of messages 
compared to the previous version of this approach.

The rest of this paper is structured as follows: In Section 2, we give an overview of the related work. In Section 3,
we describe our system model and privacy metric. In Section 4, we present the basic position sharing approach including the share fusion and
share generation algorithms. In Section 5, we propose a share placement algorithm which distributes position shares among LSs
depending on their individual trustworthiness. Then in Section 6, we present position update algorithm which optimizes
the communication overhead caused by multiple position updates. Finally, in Section 7, we conclude this paper with a summary.



§ RELATED WORK


In this section, we will discuss existing approaches for location privacy. For a more in-depth analysis
and classification of location privacy techniques, we refer to our survey paper <cit.>.

A classic solution employed to preserve location privacy is cryptography.
However, if user positions stored on servers are encrypted, server-side query
processing of advanced queries such as range queries over the encrypted
data becomes impossible, or it is possible only at higher cost <cit.>. 





Another example of a cryptography-based approach for location privacy was proposed by
Mascetti et al. <cit.> to implement proximity services for geo-social networks. The authors assume
that service providers are non-trusted and consider the scenario where mobile users want
to notify their friends called buddies in their proximity. The main idea is that the secret keys
are shared with the selected buddies in a distributed fashion and remain unknown to the
service providers. The authors use a precision metric which is defined through the union of
multiple discrete space cells called granules. A drawback of this approach is that it requires a
complex implementation of the encryption functionalities. Similarly to the work of Zhong et al. <cit.>,
this approach only considers specific friend-finder and proximity calculation scenarios.




Another method to preserve location privacy is to send dummy positions to LBAs together with the actual user position <cit.>.
The problem with this approach is, however, that dummy positions can be easily distinguished 
if the attacker has some background information such as database of real user movements <cit.>.

The idea of mix zones <cit.> is to select privacy-sensitive areas called mix zones in which users
do not send position updates while they are visible outside the mix zones. Some extensions try to avoid the threat of
analyzing possible user trajectories based on the known entry and exit points on the borders of a mix zone <cit.>.
The mix zones approach lacks flexibility since it needs a pre-defined division of space
into zones, and does not allow for various privacy levels in different zones.

Many existing location privacy approaches are based on k-anonymity, e.g., <cit.>. The main idea
is to send a set of k different positions of real mobile users (k-set) to the LBA, such that the actual user position
is indistinguishable from k-1 other positions.
Many extensions of k-anonymity aim to make the k-set more robust to various attacks—mostly
against attacks based on the analysis of user attributes, e.g., <cit.>.
However, in order to select a k-set, a trusted anonymizer with global
view is needed, which requires trust to a TTP, introducing a single point of failure.

Obfuscation approaches such as <cit.> deliberately decrease the precision of user positions stored on servers.
A TTP is not required in this case since the cloaked region can be generated by the user independently,
but the queries over obfuscated locations can result in imprecise or probabilistic answers.
Our approach is also based on spatial obfuscation, but it gracefully degrades position precision depending on
the number of missing position shares, and it supports multiple obfuscation levels (i.e., privacy levels).


Marias et al. <cit.> propose to apply the concept of secret sharing <cit.> to position
information to distribute the information about single positions among several servers.
Their secret sharing approach relies on cryptographic techniques, which means that all shares are required in order to retrieve a position.


In order to overcome this drawback, we proposed the position sharing approach based on spatial
obfuscation <cit.>, map-aware spatial obfuscation <cit.>,
and cryptographic multi-secret sharing techniques (PShare) <cit.>.
However, in all these works, LSs are assumed to be equally trustworthy, and, therefore, each LS stores one
position share of equal precision. In this paper, we will show that optimized share placement
based on the individual trust levels of providers significantly increases privacy if providers
are of different trustworthiness and opens up the possibility to minimize the number
of required LSs. Moreover, we will extend our previous work by introducing an optimized location
update algorithm, which reduces the number of transmitted messages to the LSs.



§ SYSTEM MODEL AND PRIVACY METRIC



This section introduces our conceptual system model, operational system model and privacy metrics of the position sharing approach.



 §.§ System Model


Our system model is shown in Figure <ref>. It consists of four components:
mobile objects, location servers, location-based applications, and a trust database.



The user is represented by the mobile object (MO), 
which knows its precise position π, for instance, determined through GPS. 

A position of certain precision is defined by a circular area which we call obfuscation area,
where radius r of this circular area defines the
precision prec(π) = ϕ = r of position π. A smaller radius corresponds to a higher precision:
if r_1 = prec(π_1), r_2 = prec(π_2) and r_1 < r_2,
then the precision of π_1 is higher than the precision of π_2.

The MO executes a local component to perform the generation of position shares on the mobile device.
We assume that this component can be implemented in a trustworthy way, e.g., by using a Trusted Computing Platform <cit.>.
The MO generates one master share s_0 with the minimal acceptable precision ϕ_min
chosen such that there are no problems with regard to privacy, and a set of n refinement shares S = {s_1,…,s_n}:

    generate(π, n, ϕ_min) = {s_0, S}

Given a subset S' ⊆ S of refinement shares, its fusion with s_0 (which is known to everyone) results
in a position π' of a certain well-defined precision:

    fuse(s_0, S') = π',


    with prec(π) < prec(π') ,  i.e.,  ϕ≤ϕ'

The fusion of s_0 with the set S of all
refinement shares obtained from the LSs provides the exact position π of precision ϕ_max.












We say that shares are heterogeneous if 


each share s_i increases the position precision by an individual amount Δ^ϕ_i.
Typically, for heterogeneous shares, share fusion has to be performed in a certain fixed order,
in contrast to homogeneous shares that can be fused in any order.
If a share generation algorithm produces homogeneous shares, only the number of different
shares defines the resulting precision level ϕ_k. 
In this case, the precision increase is equal for
each share: Δ^ϕ_1 = Δ^ϕ_2 = … = Δ^ϕ_n = ϕ_max/n. 



A location server (LS) stores and delivers location data of users to LBAs. Each LS
has a standard authentication mechanism, which allows to specify access rights
for the LBAs (given by a user) to access shares stored by this LS. The maximal allowed precision
of a user position is defined individually depending on the concrete LBA by specifying
a certain set of LSs accessible for each LBA.




We assume that each provider operates one LS. Internally, this LS can be implemented
by a number of physical servers, e.g., running in a data center.
Also, an LS can be implemented based on the “virtual provider” model on top of an Infrastructure-as-a-Service (IaaS).
For instance, to implement a cloud-based personal Data Vault storing and filtering locations of individual users as already
motivated in Section 1, each LS could be implemented atop a virtual machine operated by an individual IaaS provider as depicted
in Figure <ref>a. The set of LS then implements the distributed personal Data Vault offering a well-defined interface to LBAs.
The LBAs need to be aware of the interface of the distributed Data Vault in order to query data from the Data Vault,
which is a typical assumption of the Data Vault concept.

Another operational model is the implementation of a virtual LBA offered by a startup company (LBA provider)
not owning a dedicated server infrastructure as motivated in Section 1. Here, we assume that the customer actually
trusts the LBA provider, however, the LBA provider does not trust the IaaS providers operating the virtual machines
running the LS as depicted in Figure <ref>b. Although in this setting there is only a single LBA which is trustworthy from
the point of view of the mobile object (customer) and thus can be provided with position information of maximum
precision, the position sharing concept is still useful since it allows the trusted LBA provider to implement
its service atop a non-trusted IaaS infrastructure to manage positions of the whole population of all customers.
The LBA logic is implemented by a trusted app running on the mobile device, so the non-trusted IaaS
providers cannot influence how data is distributed among LS.

Since the Data Vault scenario is the more general case with several non-trusted LBAs, which should be
provided with location information of different precision, we will further on focus on this scenario only.    








Each LS is non-trusted and can be compromised with probability p_i. 
Risk value p_i represents the probability of LS_i to behave maliciously, i.e., to misuse
the user's private position information, or to be compromised by an external attacker.
The concrete 
concepts for calculating p_i are beyond the scope of this paper. For instance, we can use
the generic probabilistic trust model described in <cit.>.
This model is generic in the sense that it allows mapping of various representations of trust values to the probabilistic interval [0;1].
Different LSs might have different risks depending, for instance, on the reputation of their
provider. Moreover, different users might have individual trust in the same LS (and/or its provider).



The trust database manages the trust in different LSs by providing the
probabilities p_i that LS_i can be compromised.



Based on the obtained risk values, the user can determine the number and set
of LSs needed to satisfy his security requirements, as we will show in the following sections. 
We assume that the trust database is given, and it
is filled with data, for example, by analyzing the feedback of other users through a
reputation system <cit.>.

Location-based applications (LBAs) query or track MO's position
and obtain multiple shares from different LSs depending on the access rights given by user.
Then, the LBA fuses the obtained shares by using
function fuse(...) (Equation <ref>) in order to get the user position with a certain level of precision.



 §.§ Privacy Metric


The user's privacy levels are primarily defined through precision levels ϕ_k,
which are pre-defined by the user for each 0 ≤ k ≤ n as radii r_k of a circular obfuscation areas.
Additionally, we use a probabilistic privacy metric since the precision of a position obtained by an attacker depends on the
probabilities of compromising LSs as well as on the ability of an attacker to derive higher position
precisions by analyzing the obtained shares (as shown in <cit.>).
The following distribution P_k,attack defines the probability of an attacker obtaining a position
π_k,attack of a certain precision
ϕ_k,attack = prec(π_k,attack)
depending on the number k of compromised LSs: 

    P_k,attack(ϕ_k) = Pr[ϕ_k,attack≤ϕ_k]

This metric can be used by the MO to define the acceptable probabilistic guarantees represented
as a set of probability thresholds P_k(ϕ_k) corresponding to various precision levels ϕ_k.
For example, an MO can specify that an attacker must not be able to 
obtain a position of precision ϕ_1 ≤ 1 km with probability P_1,attack > 0.2,
and ϕ_2 ≤ 2 km with P_2,attack > 0.1, etc.



§ BASIC POSITION SHARING APPROACH


In this section, we will present the basic principle and two basic versions of the position sharing approach: (a) for
open space models (with no map knowledge) and (b) for spatial constrains (taking into account map knowledge
as explained later). Each of them includes an algorithm for LBAs to fuse position shares,
and an algorithm for MOs to generate the shares.





 §.§ Position Sharing: Basic Principle





In general, our position sharing approach is based on geometric transformations, where
imprecise geometric positions are defined by circular areas c_i with radii r_i <cit.>. Each share is a vector
shifting the center of the current obfuscated position represented as a circle, whose radius is decreased after
every shift. An example of precision increase through such share fusion is shown in Figure <ref>.
The share defines the precision increase Δ^ϕ_i after the corresponding ith
shift of the center of the circle and the radius decrease. 

After generating the shares, the MO distributes them among multiple LSs and updates them continuously.
The master share is publicly available to anyone. In order to control the access to refinement
shares, the MO defines access rights to a certain subset of shares for each individual LBA.

The concrete share generation and share fusion algorithms depend on whether we consider
the availability of map knowledge or not. Next, we first assume that no map knowledge is available
before we present an extended approach taking map knowledge into account.



 §.§ Open Space Position Sharing (OSPS)


In <cit.>, we presented the position sharing approach for open space,
referred to as OSPS (Open Space Position Sharing). The open space model 
weakens the attacker model by assuming that no map is known to an adversary. In other words,
we assume a uniform probability distribution of MO positions.



The share fusion algorithm is executed on the LBA, which knows the number of LS providers
resp. the total number of refinement shares n, the 
obtained refinement shares s⃗_⃗1⃗…s⃗_⃗k⃗ (k < n), and the master share s_0.
We define the master share as the obfuscation circle c_0 with center p_0 and
precision ϕ defined through radius r_0.

The refinement shares are shift vectors S = {s⃗_⃗1⃗…s⃗_⃗n⃗}.
The ith share defines the precision increase Δ^ϕ_i after shifting
the corresponding ith circle and decreasing its radius.

The share fusion algorithm of OSPS is shown in Algorithm <ref> (cf. Figure <ref>).
Starting from the initial obfuscation circle c_0 (lines 2,5),
step-by-step for k shares (line 3) each vector s⃗_⃗i⃗ shifts the center p_i of the current obfuscation
circle c_i (line 4) while reducing the radius r_i (line 5) of the current obfuscation circle by a pre-defined value
Δ r = r_0/n = Δ^ϕ_i (line 2). Note that in OSPS, Δ^ϕ_i has the same value Δ_ϕ for each i.
The resulting obfuscation circle is c_k (line 6).

In Figure <ref>, we show an example of share fusion for n = 4, k = 3, r_0 = 20 km, Δ r = 5 km.
As shown, the order of fusing the refinement shares can be arbitrary,
while the precision (radius) of every obfuscation circle c_k is well defined. 
Note that our algorithm is not dependent on the absolute values of r_0 and Δ r, i.e.,
it works for any selected size of r_0.












The generation of shares in OSPS is presented in Algorithm <ref>:
The input parameters are the user-defined radius r_0 of the initial obfuscation circle c_0,
the total number of shares n, and the precise user position π = p_n.
First, we determine the maximum shift length Δ r = Δ_ϕ = r_0/n (line 2).
In the second step, position p_0 of the initial circle c_0 is selected randomly according to a uniform
distribution such that π=p_n is inside c_0 (line 3). The set of the refinement shift vectors
S = {s⃗_⃗1⃗…s⃗_⃗n⃗-⃗1⃗} is generated with random direction and length (lines 4-6), starting from the center of c_0.

All shift vectors of S are concatenated such that the resulting point π = p_n 
(with r_n = 0 correspondingly) coincides with the user's position π within c_0 (line 8).

The vector lengths are selected from the interval [0; Δ r] uniformly at random. Finally, MO sends the position information to
n LSs, including the master share s_0, the radius decrease after every shift Δ r
(in OSPS, Δ r is constant for all shifts), and one share s⃗_⃗i⃗ for each LS.
The master share is stored on every LS, while each LS stores only one refinement share.



 §.§ Constrained Space Position Sharing (CSPS)


The obvious limitation of OSPS 


is that it is not applicable for constrained space models.
If an attacker has map knowledge, the attacker is able to reduce the size of the generated
obfuscation areas. By excluding areas where the user cannot be located such as water surfaces, ravines, and agriculture fields,
it is possible for the attacker to intersect an obfuscation circle c_k with

areas such as roads, squares, buildings, etc.

Since the total area of possible user locations in c_k is smaller than the total area of c_k, the target
privacy guarantees—based on the size of obfuscation circles, i.e., precision—are not preserved.

To resolve these problems, we present an improved version of the position sharing approach next, which was
first introduced in <cit.>.



In the map-aware position sharing approach for constrained space (CSPS), we introduce
the binary map representation M_u (cf. Figure <ref>a; M_u shown in yellow). Each location is marked by “true” if the MO
can be possibly located there, or “false” if it is impossible that MO is located in this area.
We define the obfuscation area A_k for k shares of precision ϕ_k through the intersection of k circles
c_1 … c_k, and M_u:

    A_k = area(M_u ∩ c_0 ∩ c_1∩…∩ c_k) = π∗ r_k^2

Before share generation, the user has to select a map representation M_u, which defines the map regions
where the user can possibly be located. M_u is individual for each user,
since different users can be possibly located in different map regions. 


The share fusion algorithm of CSPS is shown in Algorithm <ref> (cf. Figure <ref>a).
It is similar to the OSPS share fusion (Algorithm <ref>). The main difference is that c_0
as well as each c_i are intersected with the map representation M_u (lines 2, 7). Note that the radii
are not pre-defined as in OSPS, but each obfuscation has its individual radius defined by the
map-aware share generation algorithm.






Our goal is to preserve the required privacy level by providing
an obfuscation area of a given size. To this end, we adapt the radius such that the intersection
area of M_u and obfuscation circles c_0 … c_k is not smaller than this size.

Algorithm <ref> shows the CSPS share generation algorithm with map knowledge (cf. Figure <ref>b).
In Algorithm <ref>, the radius r_k is increased until the area of
M_u ∩ (c_0 ∩ c_1 ∩…∩ c_k) is equal or greater than
the value of the non-intersected area of c_k.
By applying this condition, we ensure that the precision difference between areas A-k and A_k+1
corresponds to the required Δϕ.

In lines 4-6, the radius r_0 of the initial circle c_0 is increased considering the map
representation M_u, in order to adjust the size of A_0 = M_u ∩ c_0.
Also, to adjust the radii of shares s⃗_⃗1⃗…s⃗_⃗n⃗-⃗1⃗, M_u is included
in the condition, which defines the target area size (lines 11-13). The remaining steps of the share generation algorithm for CSPS are similar
to Algorithm <ref>.



If we used a deterministic algorithm for the area adjustment (lines 5, 12), an attacker could
calculate the inverse function to decrease the size of the obfuscation area.



Therefore, the resulting
center of circle c_i must be randomly shifted together with the radius increase,
so that its original center c^'_i cannot be determined (cf. Figure <ref>a).



Algorithm <ref> shows the increase(...) function for increasing r_i together with
shifting the center p_i (cf. Figure <ref>b).
First, for the given p_i we increase the radius r_i until its value provides the required size of the obfuscation area (lines 4-6).

Then p_i is randomly shifted, such that the shift is not greater than
r_i - r^'_i (lines 7-9). Next, we check again whether the current radius r_i still
provides the required size of intersection area (line 10). If this area is
not large enough, we call the function increase(r_i,…)
recursively (line 11). If the intersection area now exceeds the target value A_i,
we decrease the current radius r_i until the intersection area hits its limit (lines 12-16).



In Figure <ref>b, we show that after the adjustment of p_i, the target position π can
be located anywhere within c_i; it is not restricted to the obfuscation area which corresponds to the smaller radius r^'_i.
Thus, it is not possible for an attacker to reduce the obfuscation area A_i
knowing the share generation algorithm and r^'_i.





§ OPTIMIZATION OF SHARE PLACEMENT



So far, we assumed that all servers are equally trustworthy. Now, we consider the case when servers have various trust levels.
Since each LS has an individual trust 
value, the user's position privacy highly depends on the number of selected LSs and the placement of shares on different LSs.
In our previous work <cit.>, we used an equal share placement strategy, i.e., each LS stored shares of the same
precision increase Δ_ϕ = Δ^ϕ_i. Now, we want to make sure that an LS with a higher trust 
level can store more precise position information than an LS that has a higher risk of being compromised.













 §.§ Problem Statement: Share Placement under Individual Trust Levels



The problem of share placement on LSs with individual trust levels can be defined as a constrained optimization problem.
The constraint is that an attacker cannot derive a position
π_k,attack = fuse(s_0,S_k) of precision
prec(π_k,attack) > ϕ_k with a probability higher than P_k(ϕ_k),
where S_k denotes the set of compromised refinement shares.
That is, the user defines probabilistic guarantees P_k for different precision levels ϕ_k.

The optimization goal is to provide the specified privacy levels and their probabilistic guarantees
by minimizing the number of LSs. 
By minimizing the number of required LSs, we limit the induced overhead of updating (communicating)
and storing shares at multiple servers.







We assume the following values to be given:

	
  * master share s_0,
	
	
  * set S of n refinement shares {s_1,…,s_n} to provide the precision (privacy) levels ϕ_k for the LBAs,

	
  * candidate set L of m_0 available LSs, which can store shares L = {LS_1, …, LS_m0},

	
	
	
  * set of risk values {p_1,…,p_m0} providing the probabilities for each LS_i of L to be compromised (p_i ∈ [0; 1]),

	
  * probability distribution P_k(ϕ_k) specifying the required probabilistic guarantees P_k for each precision (privacy) level ϕ_k.


Problem: Find 
a share placement place(…) of n shares to a set L' ≤ L of LSs:

    place({s_1,…,s_n},L): S → L' ⊆ L,

such that | L' | is minimal, and the user's security requirements are fulfilled:

    ∀ ϕ_k,attack : P_k(ϕ_k) > Pr[ϕ_k,attack≤ϕ_k]




 §.§ General Selection & Placement Algorithm


In our work, we made two assumptions. The first assumption is that increasing the number m of LSs leads
to higher security with regard to probabilistic guarantees of privacy levels.
At the same time, a large m is not desired, since it would increase storage and communication overhead.
Therefore, it is beneficial to incrementally increase m only until
the security requirements are fulfilled. The second assumption is that we can increase security by optimizing
the distribution of shares for a given m. For the validation of both assumptions, we refer to our work <cit.>.

The algorithm for optimal share placement (Algorithm <ref>) consists of two major steps: (a) selection of a minimum number
m=|L'| of location servers L'= LS_1, LS_2, ..., LS_m required to fulfill the given privacy
constraint; (b) optimization of the placement n shares among these m LSs.













The basic idea is to start with the smallest set of LSs and incrementally increase m (lines 2 and 7) until the security
constraints (Equation <ref>) are fulfilled. In each step, we greedily add the next most trusted LS to set L',
since the subset of the most trusted LSs provides the highest security.
Therefore, the available LSs must be initially sorted by ascending risks p_i (line 3).

For each number of LSs, we first check whether a uniform placement (line 8) where each LS stores an equal number
of shares, independent of its individual risk value, fulfills the user-defined probabilistic guarantees of privacy levels (lines 9-11).


If the non-optimized solution (i.e., uniform placement)
already represents a solution with regard to the constraint, we skip the optimization algorithm
to save energy resources of the mobile device, which executes this algorithm.









If the uniform (non-optimized) share placement on LSs does not satisfy the user's privacy requirements, we
optimize the placement by relocating shares from less trusted to more trusted LSs (line 12). 


The share placement algorithm invoked in line 12 in the major contribution of this section, and will be presented
in detail in Section <ref>.








If m reaches the total number of available LSs m_0, but no solution has been found,
the given security requirements are too hard. Therefore, 

the user should relax the constraints (probabilistic guarantees of privacy levels)
given in Equation <ref> step by step, 
and execute the algorithm again.

In lines 9 and 13 of Algorithm <ref>, we determine the probabilistic guarantees of privacy levels of a placement.
We calculate P_k,attack for different
numbers k_attack of compromised LSs for a given placement as follows:

    P_k,attack=∑_k=k_attack^m∑_i=0^m  kp_i,incl· p_i,excl,


    p_i,incl = ∏_j=0^m p_j, ∀ p_j ∈ P_k,i


    p_i,excl = ∏_j=0^m ( 1 - p_j ), ∀ p_j ∉ P_k,i,

where P_k,i is the set of risks of the ith k-combination out of m LS risks.

There are m  k combinations of LS to compromise exactly k LSs. Each
combination has the probability defined by multiplying the risks p_j of (included) k LSs and the
inverse risks 1 - p_j of the rest (excluded) m-k LSs. To get a
probability of exactly k compromised LSs, we have to sum up the probability of each k-combination.
Finally, to get a probability of at least k compromised LSs, we sum up the probabilities
corresponding to {k, k+1, ..., m} compromised LSs.



 §.§ Optimized Share Placement Algorithm



In this section, we present an algorithm to solve the optimized share placement problem, which is called from Algorithm <ref>
through function place_optimized(…). Here, we consider the situation when a set L' of
m = | L' | LSs with lowest risks has been selected and is fixed. Thus, an optimized placement of n
shares to these LSs in L' must be found, after the uniform placement strategy did not satisfy the user's
security constraints. 
First, we show that this problem is NP-hard. Then, we propose a heuristic solution based on a genetic algorithm.

We selected a strategy that minimizes the risk of revealing the positions of high precision by applying the
principle of risk balancing. This principle is well-known from risk-based capital allocation and is commonly
applied if the risk values are available, and there are no correlations between them <cit.>,
as is the case in our system model, where we do not know any relations between different LS providers.
We call this placement problem the Balanced Risk Placement Problem (BRPP).      





Formally, a share placement S → L' ⊆ L has balanced risk if the
proportion of position precisions ϕ_i1,j and ϕ_i2,j stored by
LS_i1 and LS_i2 respectively (j = 1 … n)
is inversely proportional to the corresponding risks p_i1 and p_i2 of LS_i1 and LS_i2:

    S → L' ⊆ L : ∀ i1, i2 ∈ m, j ∈ n : ∑_j = 1^nΔϕ_i2,j/∑_j = 1^nΔϕ_i1,j = p_i1/p_i2

If the exact equality of proportions is not feasible due to the given risk values and other parameters,
the goal is to find a share placement solution which is close to the best possible solution:

    minimize max_i = 1^m∑_j = 1^np_iΔϕ_i,j - min_i = 1^m∑_j = 1^np_iΔϕ_i,j,

under the restrictions of probabilistic guarantees of precision levels given in Equation <ref>.
This problem 
defines how the function place_optimized(…) of Algorithm <ref> must be implemented.

BRPP is NP-hard, which can be shown by reducing the Agent Bottleneck General Assignment Problem (ABGAP),
which is known to be NP-hard <cit.>, to BRPP. ABGAP is defined as:

    minimize max_i = 1^m∑_j = 1^np_iΔϕ_i,j

ABGAP is equivalent to our placement problem, since one can be polynomially
transformed into another: If we simplify our problem by adding an LS with 0 risk, we can exclude the second
term from Equation <ref>. This means that in order to solve our problem, we must also solve
ABGAP. Thus, our problem is at least NP-Hard. 



The total number of possible placement combinations for distributing n shares among m LSs is O(m^n). 

Since this number grows exponentially with the number of shares, an exhaustive search is very costly for larger m and n.
Even relatively small numbers such as m = 5 and n = 15 require the analysis of more than 3 * 10^10 combinations.


To reduce the computational complexity, we implement a linear-time heuristic.
Our goal is not to find the best placement among all possible combinations, but to find a
placement which satisfies the required probabilistic guarantees.




To this end, we need a strategy that guides our search for a secure placement 
in a reasonable (linear) time.


In general, problem-specific heuristics or meta-heuristics
can be used to find heuristic solution. We applied the
meta-heuristic of genetic algorithms <cit.>. 


Genetic algorithms reproduce the process of biological evolution. They work on multiple solution candidates by
combining and mutating


them into new possible solutions. Each new solution (in our case, a share placement)
is rated according to a fitness (objective) function defined by Equation <ref>.
Then, the best placements in terms of the objective functions are selected, and the cycle can repeat
until the goal is reached or the limit of cycles is achieved.



We implemented a genetic algorithm for share placement as shown in Algorithm <ref>. 






The input parameters are the probabilities P_k(ϕ_k), the set L of size m, and the fixed set of shares S of size n.
First, we define the initial population as 10 random placements (line 3). Then, we build a population of 40 new placements
by recombining two placements with a uniform crossover (with a probability of 50%) (lines 5-10).
Afterwards, the placement is mutated by changing one assignment randomly (line 11), ensuring that theoretically all 
possible placements could be created.

Next, the 40 created placements are rated according to the objective function, and 10 best placements are selected (lines 13-14). 
This cycle is iterated 200 times or stopped if the conditions of Equation <ref> are satisfied (lines 4-17).
The value of 200 iterations is selected such that it ensures convergence. Our experiments have shown that we already achieve a near-optimal
placement solution after about 20 iterations.
If after all cycles the probabilistic guaranties are still not satisfied (line 4), we say that the solution cannot be found
for the given input parameters.



§ OPTIMIZATION OF POSITION UPDATE ALGORITHM
 

Our basic approach <cit.> described in Section <ref>,

allows for sharing user's position among multiple non-trusted LSs,
but for the price of increased communication overhead.
A complete set of shares has to be re-generated and sent to the corresponding set of LSs every time a position update event is triggered.
More precisely, an MO must send n messages
with new position shares to n different LSs, while an LBA must receive k messages from k
LSs in order to obtain the position of the kth precision level. 
This principle can produce a high communication overhead, e.g., if the update rate is high and the number of LSs is large.
However, in many cases such as sporadic movements of the MO, the re-generation and update of the whole share set causes redundancy.
Hence, our goal is to send a smaller number of messages than n after each position change.

In this section, we begin by defining the problem of message reduction. Then, we describe an optimized position
update algorithm for position sharing approach. 





 §.§ Problem Statement: Minimization of Position Update Messages


We formulate the reduction of position updates as a constrained optimization problem.

The optimization goal is to reduce the total number of position update messages being sent
from MOs to LSs (denoted as the number of messages N^MO-LS). 
The constraints are that there should be no change of position
precision ϕ_k as a result, as well as no reduction of the user's probabilistic guarantees P_k,attack(ϕ_k) of precision (privacy) levels.

We assume the following values to be given:


  * n location servers,

  * the MO's previous consecutive precise position π_i, i.e., the position before π_i+1
(the algorithm is run on the MO side, which means that the MO's own precise positions are available),

  * the MO's next consecutive precise position π_i+1, i.e., the position after π_i,

  * master share s_0 generated for π_i,

  * set S^i of n refinement shares s_1 … s_n generated for π_i,

  * probability distribution P_k(ϕ_k), which specifies the required probabilistic guarantees
for each precision level ϕ_k.


Problem: Find the set of shares S^i+1_opt
such that S^i+1_opt requires the minimal number of update messages from MOs to LSs.
In other words, S^i+1 (S^i+1=S^i+1_opt) and S^i should differ in as few shares as possible, i.e., in S^i+1
as many shares as possible should be reused from S^i.

The concatenation of all shift vectors of S^i+1_opt must point
to π_i+1: 



    S^i+1_opt = {s^i+1_0… s^i+1_n}  :  ∑^n_k=0s^i+1_k = π_i+1,


The precision ϕ_k of each imprecise position p^i+1_k derived by share fusion after obtaining
the minimized set S^i+1_opt has to be the same as
the precision of the corresponding imprecise position p^i_k derived from the original set of shares S^i:


    ∀ S^i+1_k∈ S^i+1_opt,  S^i_k∈ S^i  :  ϕ_k(p^i+1_k(S^i+1_k)) = ϕ_k(p^i_k(S^i_k))


Finally, the set of shares S^i+1_opt must also satisfy


the current user's privacy requirements, i.e., each further kth share must provide the pre-defined probability P_k(ϕ_k):


    ∀ ϕ_k,attack  :  P_k(ϕ_k) > Pr[ϕ_k,attack≤ϕ_k];






Note that we do not assume that an MO's complete trajectory is available. We consider only the neighboring consecutive position
updates. 
Hence, we cannot apply statistical analysis of the past positions and the respective parameters such as speed, and therefore we do not consider
approaches for preserving privacy of a complete trajectory.







 §.§ Optimized Position Update Algorithm


Depending on the movement scenario, different position update approaches can be beneficial.

The key factor which separates sporadic and continuous update scenarios
is the relation of the distance traveled between two consecutive updates
and the radii of obfuscation circles.

If MO moves fast or the update rate is very low, the new MO's master share can be located completely
outside the previous master share, as depicted in Figure <ref>. 

The condition of having no intersection between two consecutive master shares is: 

    distance(p_i+1^0, p_i^0) > 2*r_0






In the following, we will only consider sporadic position updates with long time intervals between updates rather
than the continuous tracking of users. Thus, we assume that the time between updates is long enough
such that there is no relation between consecutive updates, which an attacker could exploit.
An optimized position sharing approach focusing on continuous updates using, for instance,
dead-reckoning techniques, has been described by us in <cit.>.

The main idea of our optimized position update algorithm is that under the condition of Equation <ref>,
we can recalculate and update only the master share while keeping the refinement shares unchanged.

Now we can estimate the communication costs for the optimized position update approach. Since only one share has to be updated,
the number of sent messages between MO and LS is N^MO-LS_opt = 1.
In contrast, the basic position update approach requires
all shares to be re-generated and sent, i.e., N_basic = n.





The resulting reduction rate of the communication cost is:

    R′^MO-LS_opt = n - 1/n
 

Note that since N^MO-LS_opt = 1, our optimized position updated algorithm is always optimal
w.r.t. the cost of communication between MO and LSs.


The pseudocode for the optimized position update approach run by MO is presented in Algorithm <ref>.
Before sending a location update, the MO determines whether the optimized approach is applicable
by checking the condition of Equation <ref> (line 2).
If the condition of Equation <ref> is satisfied, only a new master share
has to be generated and sent (lines 3-4) to the corresponding LS.
The refinement shares s_1 … s_n will remain the same without causing any inconsistency during their fusion.
This is enabled by the fact that shares are relative shift vectors, while the absolute coordinates are only contained
in the master share s_0.
If the condition of Equation <ref> is not satisfied, the basic position update protocol is applied (lines 5-7).




 §.§ Security of Position Updates


The first privacy requirement corresponding to our
problem statement (Equation <ref>) is that the position update optimization must not
reduce the obfuscation area, i.e., it must not cause an undesired increase in position precision ϕ_k.
Regarding this condition, we can state that the proposed optimized location
update algorithm does not reduce the number of shares, i.e., it does not change the precision level available to authorized LBAs.
In other words, the smaller number of shares sent from MO to LS does not affect the number of shares provided to LBAs.
Therefore, no change of precision occurs.

The second privacy requirement corresponding to our problem statement
(Equation <ref>) is the probabilistic metric P_k(ϕ_k).
According to the optimized location update algorithm, separate location updates only update master shares s^i_0.
The remaining refinement shares s^i_1 … s^i_n and the corresponding refined obfuscation circles remain unchanged, i.e.,
the attacker does not get new knowledge.
Thus, the randomness of share generation is preserved by the unchanged share generation algorithms (Algorithm <ref>, Algorithm <ref>),
and the probabilities P_k(ϕ_k) are the same as in the basic position sharing approaches.




§ EVALUATION


Next, we present the evaluation of our share placement algorithm and the optimized position update algorithm.
We start with an evaluation of the share placement runtime performance, before we compare the probabilistic guarantees
of precision levels of our basic approach with the probabilistic guarantees resulting from optimized share placement.
Then, we evaluate the communication cost of the optimized position update algorithm.



 §.§ Runtime Performance of Placement Optimization


According to the principle of position sharing, share placement has to be calculated on the mobile
device of the user, since it is the only trusted entity in our system model. Since mobile devices
are typically restricted in terms of processing power and energy, the runtime of our share placement
algorithm is crucial. Therefore, we measured the runtime of calculating the placement of a set of shares on a state of the art
mobile device (HTC Desire with Android OS, CPU: 1 GHz Qualcomm QSD8250 Snapdragon, memory: 576 MB RAM). 

We tested the full number of cycles of the genetic algorithm, without terminating the algorithm under
the “solution found” condition (i.e., we have tested the worst case scenario, when the solution is not feasible
for the given parameters). The number of LSs was given as m = 5; 10; 20, and the number of shares n is in the interval [m; 50].



Figure <ref>a shows the average runtime for placing n shares on m LSs.
As our evaluation shows, the proposed Algorithm <ref> has linear complexity 
and is executed in less than one second even for larger input parameters (m = 20, n = 50).
Therefore, we conclude that the algorithm is suited also for resource-poor mobile devices.



 §.§ Probabilistic Guarantees of Precision Levels after Placement Optimization


Next, we compare the resulting probabilistic guarantees of precision levels of optimized share placement compared to a basic (non-optimized)
placement algorithm. We placed n = 15 shares on m = 5 LSs with heterogeneous risks. The values of risk were chosen uniform at random
from the interval [0;0.5]: p_1 = 0.4932; p_2 = 0.3292; p_3 = 0.2344; p_4 = 0.1788; p_5 = 0.0925.
The basic algorithm distributes an equal number of shares (3) to each LS, while the optimized placement
placed 1, 2, 2, 3, and 7 shares onto the given LSs.

Figure <ref>b depicts the probabilities P_k,attack for the different precision levels ϕ. Note that the precision levels ϕ_k,attack which correspond to the
probability levels P_k,attack
are calculated as the weighted average of position precisions 
of each possible k-combination.


In Figure <ref>b, we can see that for the same precision ϕ, the probabilities
P_k,attack are significantly lower for the most ϕ values.
In other words, the optimized placement of shares has shifted the peaks of disclosure probability to the left.
For example, for ϕ = 25 km, P_k,attack = 10.7% for the optimized share placement
and P_k,attack = 40.1% for the uniform share placement.





 §.§ Communication Cost after Position Update Optimization


Next, we evaluate the communication overhead of the basic and optimized location update protocol.
As performance metric we use the number of messages sent to LSs by the different update protocols. 

For this evaluation, we used the GeoLife data set <cit.>.
including real trajectories of periodic trips to work, or hiking and biking trips. From this data set,
we have selected two trips with different update intervals and distances between updates. The first trip
has shorter update intervals (up to 15 s) and distances between updates (tens of meters). The second trip has
longer update intervals (several minutes to more than one hour) and distances between updates (up to kilometers). 





Figure <ref> shows the number of update messages sent for each location update (i.e., per position change of the trip)
by the basic and optimized update protocol, respectively, for short update intervals. The number of shares is n=5.
The radius of the master share is r_0=5 m (Figure <ref>), r_0=50 m and r_0=100 m (Figures <ref>a,<ref>b).
The optimized update approach is often selected in Figure <ref> due too small radius of the master share
(generating 6 messages per update), while for a larger radius and shorter update intervals the basic approach is applied
more often (generating 20 messages per update).
For the given parameters, the basic approach generates 7280 messages in total for the given 364 position updates.
The optimized approach generates 4158 messages in total (sending 6 messages instead of 20 in 223 out of 364 position updates),
which corresponds to a reduction rate of 42.8%.

Figure <ref> shows the number of update messages per location update for the trip with long update
intervals. Again the number of shares is n=5.
In Figure <ref>a and Figure <ref>b, we set r_0=50 m and r_0=100 m, respectively.
The basic approach generates 420 messages in total, with 20 messages per each update.
The optimized position update algorithm with 6 messages per update can be selected often since the distance between the updates is large.
The non-optimized updating with 20 messages per update is selected more often with r_0=100 due to a larger number of master share intersections.
As a result, the optimized position update algorithm generates 154 for r_0=50 and 224
messages in total for r_0=100 (reduction rate of 63.3% and 46.7% respectively).


In Figure <ref>, we show the relative communication overhead of the optimized update
protocol in relation to the basic update protocol for different radii r_0.
Here, we used the trip with long update intervals.
We can see that a larger r_0 usually causes fewer updates for larger r_0.
At the same time, for smaller r_0 values (for the given mixed data set: between 0 and 300 m),
a smaller r_0 leads to fewer intersections and, therefore, to a smaller number of update messages.






§ DISCUSSION


Finally, we discuss limitations and possible extensions to our approach presented in this paper.


In this paper, we have only considered sporadic updates of positions rather than continuous updates.
This is a reasonable assumption for many systems based on user check-ins to locations. Our basic
assumption for sporadic updates is that there is no relation between two consecutive updates. In order
for this assumption to hold, there must be sufficient time between consecutive updates depending on the
distance between updates since otherwise an attacker can exclude some areas from the obfuscated area to
increase the precision of obfuscated positions.

In particular, we need to consider the so-called
Maximum Velocity Attack <cit.>.
This attack limits the obfuscation area of subsequent updates by assuming a maximum MO speed and
distance travelled since the last update.
In order not to be prone to such attacks with our approach, the time interval between consecutive updates
must be long enough such that the user could travel between both positions at least two times.
Otherwise, we need to suppress the update.
This is the well-known counter-measure against such an attack, described 
in the literature <cit.>.

It is also possible to consider a probability distribution (pdf) based on the movement correlation
instead of one based on intersection of the binary movement
boundary. However, such an approach requires analysis of the trajectory correlation pattern
and is beyond the scope of this paper. We refer to our work <cit.>,
which extends the position sharing approach by considering trajectory data, and
which estimates the resulting probabilistic privacy guarantees.









§ CONCLUSION


In this paper, we described our position sharing approach, which distributes position information of a mobile user
among multiple location servers of non-trusted providers in the form of separate position shares.
This approach has several interesting properties like no single point of failure with respect to privacy
and graceful degradation of privacy with the number of compromised location servers.

In this work, we have further improved our basic position sharing approach.

The first extension increases the user's location privacy if the available location servers have different trust levels.
Based on a probabilistic security metric, we 
proposed an approach
which improves the user security by selecting the minimal required
number of location servers and by optimizing the distribution of position shares among these servers.

Our solution has linear complexity and in practice can be executed 
on resource-poor mobile devices.
Our evaluations show that that this optimized share placement provides a
30%–40% lower probability of a user being discovered by an attacker at the same precision (privacy) levels.

The second extension of our basic approach is the optimization of the communication cost caused by
position updates. 
Our calculation of communication cost takes into account the messages sent from mobile users to location servers
as well as the messages sent from location servers to location-based applications.


We have shown that our position update approach

significantly reduces the communication cost achieving a traffic reduction of up to 60% of the non-optimized protocol version.









§ ACKNOWLEDGEMENTS

We gratefully acknowledge the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG)
for financial support of this research (PriLoc project).



§ REFERENCES



IEEEtran



