Personal data are the new oil. Vast amounts of spatiotemporal data generated by individuals have been collected and analyzed, such as check-in data, trajectories, web browsing data and timestamped medical records. These personal data are a valuable resource for businesses and also have the potential to provide significant social benefits through sharing and reuse. However, privacy concerns hinder the wider use of these personal data. To this end, dozens of privacy protection models have been proposed for privacy-preserving data publishing (PPDP). -differential privacy has emerged as a de facto privacy model for PPDP because of its rigorous theoretical guarantees, but it has also been criticized as impractical in many scenarios. We attempt to design rigorous and flexible privacy models that able to bridge the gap between theoretical limitations and practical needs. In this article, we first motivate the importance of rigorousness and flexibility for privacy models and then present two privacy models that extend differential privacy in a practical manner.
New opportunities are arising to enrich our understanding of the physical world by utilizing personal big data. Such data generated by individuals that possess spatial and temporal properties are called personal spatiotemporal data and include information such as people’s movements, search logs, shopping records, social activities and medical histories. Companies such as Google, Amazon and Facebook have created enormous wealth by using such personal data. These data also have the potential to support significant initiatives for the public good, such as innovative services, traffic monitoring, disease surveillance and health promotion. Therefore, it is important to enable the sharing and reuse of personal spatiotemporal data.
However, several well-known cases of privacy leakage have arisen in attempts to provide privacy-preserving data publishing (PPDP) [1]. One of the most famous privacy leakage cases occurred with regard to the Massachusetts Group Insurance Commission (GIC) medical dataset, which contains anonymized medical records and was first made available in 1996 for medical research and public health purposes. Latanya Sweeney [2] linked the anonymized GIC database (which retained the birthday, sex, and ZIP code of each patient) with voter registration records to identify the medical records of the governor of Massachusetts. In 2006, AOL Inc. released more than 650 thousand users’ anonymized search logs for research purposes, but researchers [3] found it is possible to de-anonymize some users by mining these timestamped records. A recent privacy leakage case was related to the datasets released for the Netflix Prize competition for recommender algorithms. Researchers [4] verified that the datasets could be de-anonymized by linking them with the IMDB dataset; as a result, Netflix became the target of a lawsuit and was obliged to terminate this well-known competition in 2010. In Japan, the East Japan Railway Company (JR) faced a scandal in 2013 because of the selling of customer data collected through the use of SUICA cards. These privacy leakage cases illustrate the conflict between increasing public concerns about data privacy and the need for personal data publishing. Therefore, privacy issues have become a critical problem in the big data era.
Personal spatiotemporal data are highly sensitive even if they are anonymized. Studies [5] [6] have shown that only four spatiotemporal data points from anonymized mobile datasets and credit card records (with purchase times and locations) are sufficient to uniquely identify 90% of individuals. Another study [7] has demonstrated that it is possible to track smart phone locations simply by monitoring battery consumption data (timestamps and remaining battery life), which do not require the users’ permission to be shared. Therefore, because of the unique and rich patterns that are present in personal spatiotemporal data, a rigorous privacy model is needed to utilize personal spatiotemporal data in a privacy-preserving manner.
At the same time, privacy models should be flexible for the following two reasons. First, because privacy protection implies the hiding or perturbing of sensitive information1, the privacy level should be tunable (to an appropriate level) for different applications to achieve a suitable trade-off between privacy and utility. Second, privacy as a complex social concept should be modifiable in accordance with different social contexts. For example, different users might have different 1Although some cryptographic approaches (e.g., homomorphic encryption) can be used for PPDP, because they limit the possible data recipients, we here discuss primarily perturbation-based approaches that enable a wider sharing of data. preferences regarding privacy; for a single user, the desired protection levels might also be different at different times and places.
In the following, we briefly review the background for this research in Section 2 and then present two proposed privacy models in Section 3 and Section 4. 2.1
Previous studies have considered two major families of privacy models: k-anonymity [2] and -differential privacy [8]. k-anonymity [2] was proposed in 2002 and was the first privacy model to be widely accepted by practitioners. However, Machanavajjhala [9] identified a serious flaw of k -anonymity by demonstrating the possibility of homogeneity attacks and background knowledge attacks and, to resolve this flaw, proposed an improved privacy model based on k -anonymity named `-diversity. However, `-diversity had its own shortcomings, which motivated further improvement to yield subsequent new privacy models, such as t-closeness [10] and M invariance [11]. Researchers have realized that the essential defect of the k-anonymity family is that the privacy guarantee depends on the background knowledge possessed by adversaries. In 2006, Dwork et al. proposed -differential privacy [8], which has received increasing attention because it is guaranteed to be rigorous and mathematically provable. Differential privacy ensures protection against adversaries with arbitrary background knowledge. 2.2
Intuitively, differential privacy guarantees that any single user’s data in the database have only a “slight” (bounded by ) impact on changes to the outputs. The parameter that is used to control the privacy level is defined as a real positive number. A lower value of corresponds to a lower likelihood of privacy leakage. In the case of a suitably small , an adversary cannot associate any piece of information with a specific individual by mining the answers to queries. Definition 1 (Neighboring Database [8]). If D is a database and D0 is nearly identical to D but differs by one record, then we say that D and D0 are two neighboring databases. Definition 2 ( -Differential Privacy, -DP [8]). Let be a randomized algorithm, and let R represent all possible outputs of . The algorithm satisfies -DP if the following holds for any r 2 R and any two neighboring databases D and D0.
P r[ (D) = r] exp( ) P r[ (D0) = r]
(
In the inequality expressed in (
Two widely used methods of achieving differential privacy are the Laplace mechanism [12], which adds random noise to the real data to prevent the disclosure of sensitive information, and the Exponential mechanism [13], which randomly returns the desired item with some calibrated probability. (b) Trajectory data.
(c) Aggregate data.
Below, we summarize two crucial weaknesses of differential privacy that hinder its extensive use in data publishing.
One size fits all. -differential privacy uses a single parameter to represent the protection level for all users in a database rather than providing a personalized privacy protection level.
Data independence assumption. Differential privacy assumes that the tuples in a database are independent; however, real-world data tend to be temporally or spatially correlated. 2.3
Here, we describe a scenario of the publishing of aggregate spatiotemporal data. We consider a scenario in which a trusted server collects spatiotemporal data points from users and continuously stores them in database Di at each timestamp i 2 [1; t]. Let t denote the current timestamp. Each data point huID; time; loci is a row in Di (Fig. 1(a)). Suppose that locs is the set of all locations in which we are interested (POIs); then, the server wishes to publish a vector ri at each timestamp i that consists of the counts of loc 2 locs that appear in Di (Fig.1(c)), i.e., the answer to the count query Qc : Di ! Rjlocsj. Without loss of generality, we assume that each user appears at only one location at most at each timestamp. We need to transform the aggregate data depicted in Figure 1(c) into a secure form for publishing because they are computed directly from the sensitive raw data. The most straightforward method is to employ the Laplace mechanism [12] (add random Laplace noise) to achieve DP. In accordance with the limitations of DP discussed above, two problems are encountered when applying DP in practice, as follows:
How can personalized differential privacy be achieved? How can differential privacy be guaranteed even if the data are temporally or spatially correlated?
We present two privacy models, `-trajectory privacy (Section 3) and spatiotemporal privacy (Section 4), to solve the above problems.
In a previous work [14], we defined a new privacy model that we called `-trajectory privacy to guarantee that any `length trajectories for each user are protected under differential privacy. We formalized our privacy definition, proved its feasibility, and designed efficient mechanisms to implement it. This privacy model is personalized, i.e., different users can specify different lengths of `-trajectories (` successive data points) depending on their privacy requirements, as illustrated in Figure 2(b). A closely related privacy model called w-event privacy [15] protects the data within sliding windows (all data points in w with successive timestamps), as shown in Figure 2(a). In the following, we present the definition of the `-trajectory privacy model and related experimental results.
We first define the neighboring databases in our setting. Definition 3 (`-Trajectory Neighboring Stream Prefixes). Let St0 be a near copy of the trajectory stream prefixes St that differs in ` neighboring databases Di0. St and St0 are neighboring `-trajectory stream prefixes if one can be obtained from the other by modifying single or multiple locs in any one `-trajectory `u;k (recall that an `-trajectory is a set of ` spatiotemporal data points). We say that St and St0 are neighboring with respect to `u;k.
Intuitively, `-trajectory privacy attempts to ensure that any `-trajectory for any single user has a only “slight” (bounded by ) impact on the outputs.
Definition 4 (`-Trajectory -Differential Privacy). Let be an algorithm that takes prefixes of trajectory streams St = fD1; ; Dtg as inputs. Let Nt = fn1; ; ntg be a possible perturbed output stream of . If the following holds for any `-trajectory neighboring St and St0,
P r [ (St) = Nt] e
P r (St0) = Nt (2) then we say that satisfies `-trajectory -differential privacy (or `-trajectory privacy for brevity).
The following theorem provides insight regarding the implementation of `-trajectory privacy.
Theorem 1. Let be an integrated algorithm that takes stream prefixes St = fDi; i 2 [1; t]g as inputs and produces Nt = fni; i 2 [1; t]g as outputs. consists of a series of sub-algorithms fAi; i 2 [1; t]g, each of which takes Di as its input and outputs noisy data ni with independent randomness. Presume that Ai ensures "i-DP, and let u;k be the set of timestamps dominated by an arbitrary trajectory `u;k; then, satisfies `-trajectory privacy if 8u; 8k; X "i (3) i2 u;k
Based on the above theorem, we designed an algorithmic framework for publishing differentially private aggregates that satisfy `-trajectory privacy. The experimental results show that our approach is effective and efficient compared with previous works [16] and [15]. More details can be found in our paper [14].
ST -DIFFERENTIAL PRIVACY
In existing studies, traditional DP mechanisms (e.g., the Laplace mechanism) are employed as primitives. These mechanisms assume that the data are independent or that adversaries do not have knowledge of the data correlations. However, data collected from the real world tend to be temporally or spatially correlated, and such correlations could be acquired by adversaries. In this study, we introduce a new class of adversaries named realistic adversaries who have t1 t2 t3 t4 t5 …
t1 t2 t3 t4 t5 … u1 mhoe u2
bar u3 mhoe ocfefi gmy bar … mhoe … bar … u1 mhoe u2
bar u3 mhoe ocfefi gmy bar … mhoe … bar … (a) w-event privacy (w=3).
(b) l-trajectory privacy (l=3). loc4 (a) Road Network colleague u2
couple u1
u3 (b) Social Ties tempfoorrsainlgcloerurseelartion spatfoiarlucseorr-ruesleartion
D1 D2 D3 … r1 r2 r3 … uuuu4321 7lllloooo:0cccc04223 llll8oooo:0cccc05411 llll9oooo:0cccc03511 …………… llllloooooccccc54321 7:1012000 8:1100200 9:1010200 ............
(c) Spatiotemporal Data (d) Raw Aggregates Figure 3: The vulnerability of differential privacy to correlated spatiotemporal data. a varying degree of knowledge of the spatiotemporal correlations of the data of interest. We demonstrate that the risk of a DP mechanism may increase over time given the existence of such adversaries. To prevent such privacy leakage, we propose a new privacy definition, ST -differential privacy, and present novel mechanisms to satisfy this privacy definition. In the following, we first demonstrate the problem by means of a motivating example, present the definition of realistic adversaries, and briefly describe measures for protecting against such adversaries. This work has been submitted to an international conference. 4.1
The following example (illustrated in Figure 3) shows that the existence of adversaries with knowledge of the spatiotemporal correlations of the data may degrade the expected privacy guarantee of DP.
Example 1. Consider the scenario of spatiotemporal data
publishing illustrated in Figure 3. A trusted server
continuously collects users’ locations at each time point. Our goal is
to publish the aggregates shown in Table (d) while protecting
against adversaries who may have some knowledge regarding
membership in the database. We assume that each user
appears at only one location at most at each time point. Then,
according to the Laplace mechanism [12], adding Lap(1= )
noise2 to perturb the data can achieve -DP. However, from
auxiliary information such as road network constraints, an
attacker may know the mobility patterns of a targeted
victim; for example, the adversary may know that the victim
“always arrives at loc5 after visiting loc4,” as illustrated in
Figure 3(a), which leads to the patterns indicated by the solid
lines in Figure 3(c) and (d). Consequently, because of the
composability of DP, adding Lap(1= ) noise guarantees only
2 -DP against this attacker. We refer to the transition
pattern of a single user as temporal correlation. By contrast,
when an attacker has the following knowledge (illustrated in
Figure 3(b)), privacy leakage will also occur: (
To formalize realistic adversaries (RAs) and their impact on privacy leakage, we first study commonly used models for describing temporal and spatial correlations as means of expressing the prior knowledge of RAs. We then define a new privacy model, ST -Differential Privacy ( ST -DP), to account for RAs.
Definition 5 (Temporal Correlations). The temporal correlation of user i is described by a transition matrix Pi 2 Rjlocj jlocj, which represents Pr(lit 1jlit), where lit is the location of user i at time t.
Definition 6 (Spatial Correlations). Let xi denote Gaussian random variables that represent the possible locations of each user i 2 [1; n]. GMRF G, which we call the correlation graph, describes the spatial correlations among x1; : : : ; xn.
We define realistic adversaries in a comprehensive and flexible manner such that various scenarios can be represented.
Definition 7 (Realistic Adversaries). The adversaries
targeting user i who possess various levels of prior knowledge,
denoted by Ri(Pi; Gi; m), are called the realistic adversaries
of that user. There are three basic types of realistic
adversaries: (
Attack by realistic adversaries is Bayesian in nature [17]. Let DKt Dt represent the prior knowledge of such adversaries, and let DUt be the unknown tuples, i.e., Dt = DKt [ DUt [ flitg. The adversaries attempt to infer the location of user i at time t. To this end, they first infer Dt U based on DKt and a guessed value of lit (or lit0, to represent a different guess) and then attempt to distinguish the difference between the two neighboring databases Dt and Dt0, where Dt0 = DKt [ DUt [ flit0g.
Definition 8 ( -DPST ). At each time t, a DP mechanism Mt takes Dt as input and produces rt as output. The privacy leakage of Mt against Ri(Pi; Gi; m) is defined as follows.
P L(Ri; Mt) =de=f 8jDsKtupj=m log PPrr((rr11;;::::::;;rrttjjllitit0;;DDKtKt))
PDt Pr(r1; : : : ; rtjDt) Pr(DUt jlit; Dt ) = 8jDsKtupj=m log PDUtUPr(r1; : : : ; rtjDt0) Pr(DUt jlit0; DKKt) (4) Mt satisfies -DPST (i.e., DP under spatiotemporal correlations) if, for all Ri; i 2 [1; n], it holds that P L(Ri; Mt) .
The primary challenge of protecting against realistic
adversaries is to finely quantify the privacy leakage, i.e.,
Equation (4). Because of space limitation, we briefly describe
a concept for how this can be achieved and present a
preliminary result. We analytically divide Equation (4) into
two parts, namely, the privacy leakages w.r.t. adversaries
of type (
The result reveals that the privacy leakage of a DP mechanism w.r.t. realistic adversaries may increase over time, as shown in Example 2.
Example 2. According to the Laplace mechanism, traditionally, adding Lap(1=0:1) noise to published counts can (a) Strong temporal corr. (b) Moderate temporal corr. (c) No temporal corr. 0.181 0.247 0.302 0.349 0.388 0.422 0.45 0.475 0.496