Research On Location Privacy Issues Using Information Theory

With the ubiquitous deployment of wireless networks,and the advances in sensing and positioning technology,Location-based Service(LBS)has become an indispensable and important way to improving people's daily life and making our lives more convenient than ever.However,the openness of wireless networks and the fact that the service provider may be untrusted could bring serious privacy threat to people and thus lead to privacy leakage.Therefore,Location Privacy Protection Mechanisms(LPPMs)have become research hotspots.Even though the existing LPPMs can be used to protect location privacy for certain scenarios,there lack a formal framework and privacy metrics to quantify the location privacy leakage.Since privacy metrics are extremely important for telling people how much information leakage will occur when they are using LBS,they have to to be well studied in the field of location privacy.Mutual information and conditional mutual information in information theory naturally come into our mind.In principle,privacy metrics based on mutual information and conditional mutual information could be leveraged to measure the information leakage of location privacy.Specifically,there are three important types of location data,i.e.,location trace,aggregated location data and sporadic location data.In this thesis,we endeavor to propose privacy metrics for these three types of location data respectively using information-theoretic approaches,and formulate the optimal location release problems that minimize location privacy leakage given utility constraints,then we implement algorithms to derive efficient solutions(i.e.,LPPMs)by modifying Blahut-Arimoto algorithm in rate-distortion theory.The main contributions of the thesis can be summarized as the following:Firstly,we study the problem of protecting individual user's location privacy at the tracelevel and study the privacy-utility trade-off.Existing works on location privacy protection mechanisms have mainly focused on protecting single location,without taking into account the temporal correlations among locations within the trace,which can lead to higher privacy leakage when considering the whole trace.However,to date,there lacks a formal framework to quantify the trace-level location privacy leakage,and a practical mechanism to release location traces in an optimal and online manner.In this thesis,we endeavor to solve this problem using an information-theoretic approach.We first propose a location trace privacy metric based on the mutual information between the original and released trace in an offline setting,and formulate the optimal location trace release problem that minimizes trace-level privacy leakage given a utility constraint.We also propose a privacy metric to capture trace-level privacy leakage in an online setting.We address a practical challenge encountered when solving the optimization problem in online setting.As directly computing these metrics incur exponential complexity w.r.t.the trace length,we obtain upper and lower bounds on the trace-level privacy leakage by exploiting the Markov structure of the temporal location correlations,which are efficiently computable.Secondly,we derive efficient online LPPMs which can achieve the minimum information leakage based on the upper bounds proposed in the previous section.Specifically,we design and implement algorithms to derive efficient LPPMs by modifying Blahut-Arimoto algorithm,since the objective functions in the upper bounds are in the form of conditional mutual information instead of mutual information in the original Blahut-Arimoto algorithm.In particular,our LPPM can be pre-computed in advance and then used for online location release with very high efficiency.Then we validate the proposed upper and lower bounds and the actual leakage of our LPPM through extensive experiments over both synthetic and realworld location datasets.Our results show the superiority of our LPPM over existing LPPMs in terms of tracelevel privacy-utility tradeoff,which is more conspicuous when the location trace is more correlated.We also show the efficiency of our LPPM,where the offline pre-computation requires a reasonable time,and the online release is very fast.Thirdly,we propose privacy metrics to quantify the information leakage when releasing aggregated location data to the public.We particularly study the privacy leakage on individual users and also the original aggregated location data caused by releasing the distorted aggregated location,and formulate these two privacy-utility tradeoffs as optimization problems.We prove the relation between these two privacy-utility tradeoffs,which is individual leakage is upper bounded by aggregated leakage under the same utility constraint.Due to the exponential complexity when solving the optimization problems,we propose an upper bound on the aggregated privacy-utility tradeoff and then implement an algorithm to generate an Aggregated Location Privacy Preserving Mechanism(ALPPM)for releasing aggregated location data.Moreover,considering of the limitation of a computer's memory,we derive a maximal number of users and the corresponding maximal number of locations in the aggregation process.Our experimental results demonstrate that releasing distorted aggregated location data do leak information about individual users and the original aggregated location.More importantly,the proposed ALPPM ensures that the more skewed users' priors are,the better protection it can provide to the original location aggregates.Moreover,its advantage over SCM in terms of privacy-utility tradeoff becomes even greater when there are more users with highly skewed priors.Finally,we consider the scenario that a location data owner trusts different data users at different levels,therefore,the data owner will publish the distorted location data to each user according to her trust level.However,there lacks a privacy metric to measure this type of privacy leakage and a privacy protection mechanism based on this privacy metric.In addition,when an attacker could obtain multiple released location data(e.g.,via intercepting)which are distorted at different levels,he will be able to infer the private information about data owner's true location with higher accuracy compared with the case when he only has the distorted location data corresponding to his own trust level.In this thesis,we propose privacy metrics to quantify the privacy leakage in these two scenarios,and a location release mechanism providing multi-level location privacy protection.Experimental results show the advantage of our LPPM over the LPPM based on differential privacy in terms of privacy-utility tradeoff,which is greater when there exist highly popular locations.