PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantifying Differential Privacy in Continuous Data Release under Temporal Correlations

Yang Cao, Masatoshi Yoshikawa, Yonghui Xiao, Li Xiong

arXiv:1711.11436v3cs.DB

TL;DR

Continuous-release DP often assumes independence across time or no adversarial knowledge of temporal correlations, although such correlations can change event-level privacy loss. This paper analyzes and quantifies that loss under Markov models, and reports that event-level privacy loss may rise over time while user-level privacy behaves as expected.

  • Problem

    Many continuous-release DP studies assume temporal independence or that adversaries lack correlation knowledge, leaving privacy loss under known temporal correlations insufficiently characterized.

    Source: §1 · p. 1

  • Method

    The paper models temporal correlations with Markov chains, analyzes privacy loss against informed adversaries, and develops fast algorithms and budget-allocation mechanisms for TPL.

    Source: §8 · p. 14

  • Results

    Event-level privacy loss may increase over time under temporal correlations, while user-level privacy behaves as expected.

    Source: §8 · p. 14

  • Takeaways & Limitations

    The proposed fast TPL-quantification algorithms enable private data release in real time.

    Source: §8 · p. 14

    The analysis assumes adversarial knowledge of temporal correlations modeled by a Markov chain; if that model is not ground truth, TPL may not be appropriately protected.

    Source: §3.5 · p. 6

Abstract

from arXiv · show

Differential Privacy (DP) has received increasing attention as a rigorous privacy framework. Many existing studies employ traditional DP mechanisms (e.g., the Laplace mechanism) as primitives to continuously release private data for protecting privacy at each time point (i.e., event-level privacy), which assume that the data at different time points are independent, or that adversaries do not have knowledge of correlation between data. However, continuously generated data tend to be temporally correlated, and such correlations can be acquired by adversaries. In this paper, we investigate the potential privacy loss of a traditional DP mechanism under temporal correlations. First, we analyze the privacy leakage of a DP mechanism under temporal correlation that can be modeled using Markov Chain. Our analysis reveals that, the event-level privacy loss of a DP mechanism may \textit{increase over time}. We call the unexpected privacy loss \textit{temporal privacy leakage} (TPL). Although TPL may increase over time, we find that its supremum may exist in some cases. Second, we design efficient algorithms for calculating TPL. Third, we propose data releasing mechanisms that convert any existing DP mechanism into one against TPL. Experiments confirm that our approach is efficient and effective.

1 INTRODUCTION

Continuous release can make event-level privacy weaker when an adversary knows temporal correlations: a change affecting two counts without correlation may affect four in the correlated example. The paper defines and analyzes temporal privacy leakage (TPL), develops efficient calculation algorithms, and proposes budget-allocation mechanisms to bound it.

1 INTRODUCTION

  • Prior work often assumes independence across time or an adversary without correlation knowledge; existing correlation-aware approaches were not suited to continuous release, leaving its changing privacy guarantee unreported.The paper identifies group-DP amplification as potentially over-perturbing probabilistic correlations and describes prior approaches as focused on user-user correlation or one-shot release.Source: §1 · pp. 1–2
  • With the stated location correlation, changing one data cell may affect four released counts instead of two, so Lap(2/ϵ) noise provides 2ϵ-DP rather than ϵ-DP.The example contrasts this with the uncorrelated case, where the global sensitivity is 2.Source: §1 · p. 1

1.1 Contributions

  • The paper models temporal correlations with a Markov chain and defines TPL as a mechanism’s privacy loss against an adversary who knows that model and observes continuous releases.The introduction says privacy loss may increase with previous and even future releases.Source: §1.1 · p. 2
  • TPL comprises backward and forward leakage, and the paper defines α-DP_T and proves a sequential composition theorem connecting it with event-level DP, w-event DP, and user-level DP.Backward leakage reflects previous releases; forward leakage reflects future releases.Source: §1.1 · p. 2
  • The proposed algorithms calculate TPL through linear-fractional programming structure and outperform CPLEX by several orders of magnitude with the same optimal answer.The paper also proposes calibrated privacy-budget schemes: one bounds TPL by a supremum but can over-perturb short releases, while another achieves α-DP_T at each time point.Source: §1.1 · p. 2
  • Experiments confirm the efficiency and effectiveness of the quantification algorithms and release mechanisms, and demonstrate how correlation strength affects privacy leakage.Source: §1.1 · p. 2

2 PRELIMINARIES

The preliminaries define differential privacy and privacy leakage, then establish a continual-release setting in which adversaries observe multiple outputs and may know temporal correlations.

2.1 Differential Privacy

  • ϵ-DP requires neighboring databases to produce output distributions satisfying a bounded likelihood ratio, and the Laplace mechanism achieves it by adding noise scaled to query sensitivity divided by ϵ.Source: §2.1 · pp. 2–3

2.2 Privacy Leakage

  • Privacy leakage is defined for an adversary targeting one user’s value while knowing the other data; the mechanism’s privacy budget can be treated as a bound on its maximum leakage.A mechanism satisfying ϵ′-DP also satisfies ϵ-DP when ϵ′ < ϵ.Source: §2.2 · p. 3

2.3 Problem Setting

  • The setting releases outputs continuously over time, with mechanisms operating independently at each time point and privacy budgets allowed to vary; the study examines event-level privacy and user-level composition under temporal correlations.Each user contributes one data point per time point, and the release horizon need not be known exactly.Source: §2.3 · p. 3

3 ANALYZING TEMPORAL PRIVACY LEAKAGE

This section analyzes how Markov temporal correlations affect event-level privacy leakage across continuous releases, including its accumulation and relationship to ordinary differential privacy through α-DPT. It also examines personalized leakage, the limits of assuming a known correlation model, and the distinction between event-level leakage and composition over a user’s timeline.

3.1 Adversay with Knowledge of Temporal Correlations

  • An informed adversary knows other users’ data and backward and/or forward transition correlations, which may be learned from trajectories or derived by Bayesian inference.The framework assumes this correlation knowledge is available to the attacker.Source: §3.1 · pp. 3–4

3.2 Temporal Privacy Leakage

  • Temporal privacy leakage (TPL) decomposes into backward privacy leakage (BPL) and forward privacy leakage (FPL), capturing disclosure from releases before and after the target time.The decomposition subtracts the single-output leakage shared by BPL and FPL.Source: §3.2 · p. 4
  • BPL is recursive and may accumulate over time; with maximal backward correlation it increases linearly, while without known backward correlation it equals single-release leakage.The backward temporal privacy loss function satisfies 0 ≤ LB(x) ≤ x.Source: §3.2 · pp. 4–5
  • FPL is recursive and may increase as future releases arrive; backward correlation affects only BPL, forward correlation only FPL, and knowing both exposes both.The forward temporal privacy loss function satisfies 0 ≤ LF(x) ≤ x; unlike BPL, FPL at earlier times can be updated by later releases.Source: §3.2 · p. 5

3.3 α-DPT and Its Composability

  • α-DPT guarantees that a mechanism’s TPL is at most α; temporally independent data make ε-DP imply ε-DPT, while correlations can add quantifiable leakage.The section also states that it proves sequential composition and discusses connections to event-level, user-level, and w-event privacy.Source: §3.3 · p. 5
  • For a combined mechanism protecting a user’s full timeline, temporal privacy leakage is the sum of the mechanisms’ privacy budgets, so temporal correlations do not affect user-level privacy.This is consistent with treating all correlated data in a user’s timeline as a protected bundle.Source: §3.3 · p. 6
  • Under strong temporal correlation, event-level leakage can reach Tϵ; with moderate correlation it exceeds ϵ but remains below Tϵ, blurring event- and user-level privacy.Across correlation strengths, the reported range is ϵ to Tϵ.Source: §3.3 · p. 6

3.4 Connection with Pufferfish Framework

  • Unlike the one-shot Markov Quilt setting, this analysis concerns continuous release, where previous and future releases may affect a release’s privacy guarantee.The paper identifies these effects as backward and forward privacy leakage.Source: §3.4 · p. 6

3.5 Discussion

  • Leakage is personalized to users’ temporal patterns; taking the maximum across users makes α-DPT compatible with traditional ϵ-DP mechanisms, while personalized budgets can bound leakage per user.The paper also connects α-DPT to the Pufferfish framework, which accommodates data-evolution scenarios such as temporal correlations.Source: §3.5 · p. 6, §3.4 · p. 6
  • The analysis assumes adversarial knowledge of Markov-chain correlations; if that model is not ground truth, protection may be inappropriate, and choosing a likely-encompassing set of possible correlations remains open.Given possible transition matrices, the maximum TPL can be calculated, but identifying a suitable set depends on the application scenario.Source: §3.5 · pp. 6–7

4 CALCULATING TEMPORAL PRIVACY LEAKAGE

Section 4 presents efficient methods for calculating backward and forward temporal privacy leakage, including a recursive construction of the piecewise privacy-loss function L(α) for answering leakage queries at arbitrary correlation levels. The methods use polynomial-time computation and precomputation in place of costly direct optimization.

4.1 Problem formulation

  • The direct formulation is a linear-fractional program, convertible to a sequence of linear programs solved by simplex in O(2^n) time; overall simplex complexity is O(n^2 2^n).Source: §4.1 · p. 7

4.2 Polynomial Algorithm

  • Theorem 5 conditions enable an O(n^2) solution for each row-pair problem, and Algorithm 1 computes BPL or FPL across all pairs in O(n^4) time.The algorithm uses sufficient optimality conditions and a necessary condition to identify candidate coefficients before checking the constraints.Source: §4.2 · pp. 7–8
  • Identical transition-matrix rows yield L(·) = 0, while rows with qi = 1 and di = 0 at some index yield L(x) = x.Source: §4.2 · p. 8

4.3 Quasi-quadratic Algorithm

  • For each row pair, only a finite set of candidate solutions occurs as α varies, with solutions changing monotonically across ranges and forming a piecewise function.Precomputation takes O(n^3) time offline; each subsequent time-point calculation takes O(n^2 log n).Source: §4.3 · pp. 8–9

4.4 Sub-linear Algorithm

  • The sub-linear method constructs L(α) as the maximum of row-pair piecewise functions, using endpoint comparisons to identify the top function over an interval.The endpoint rule avoids missing intersections between transition points; Algorithm 4 recursively identifies the sub-functions and their domains.Source: §4.4 · pp. 9–10
  • Algorithm 4 recursively splits the domain at an interior intersection of candidate functions, while endpoint comparisons identify intervals where one function is topmost.It stores the resulting coefficients and subdomains to construct L(α).Source: §4.4 · p. 10
  • O(log n) time suffices to calculate BPL or FPL at one time point by binary-searching the sorted subdomains of L(α).The subdomains are stored in sorted array aArr.Source: §4.4 · p. 10
  • Generating L(·) takes O(n^3 + m log m) time overall; its parameters qM, dM, and aM are calculated by Algorithm 2, which requires O(n^3) time.Source: §4.4 · p. 10

5 BOUNDING TEMPORAL PRIVACY LEAKAGE

The section characterizes when backward and forward privacy leakage have a supremum, then presents two privacy-budget allocation strategies for guaranteeing α-DPT. One strategy bounds leakage conservatively; the other adjusts endpoint budgets to reduce that conservatism for short sequences.

Supremum of BPL and FPL

  • Theorem 11 analyzes four cases for the supremum of BPL or FPL, with cases distinguished by q, d, and ε.The theorem's cases include conditions involving d = 0, q = 1, and ε relative to log(1/q).Source: §5 · p. 10

Supremum of BPL

  • In Figure 5, the BPL supremum does not exist in (a) and (b), while Theorem 11 calculates it in (c) and (d); these results agree with step-by-step computation.The examples consider different ε values and transition matrices.Source: §5 · p. 10

Budget allocation strategies

  • The first allocation strategy uses Theorem 11 to choose privacy budgets so the supremum of TPL does not exceed the desired level α, except under the strongest temporal correlation.It uses the sum of the BPL and FPL suprema, subtracting ε_t, to set the bound.Source: §5 · pp. 10–11
  • The second strategy assigns larger budgets at times 1 and T and a constant budget at intermediate times, making BPL and FPL equal across their respective time ranges.It is designed to address the first strategy's conservatism when T is short, when leakage may not reach its supremum.Source: §5 · p. 11

6 EXPERIMENTAL EVALUATION

The experiments assess the quantification algorithms’ runtime and correctness, the effect of temporal correlations on leakage, and the utility of the proposed release mechanisms. They report that stronger correlations increase leakage, while Algorithm 8 has better utility in the reported release comparisons.

6 EXPERIMENTAL EVALUATION

  • The three quantification algorithms matched CPLEX on 100 random transition matrices of dimension 30; the experiments used 30 runtime runs per algorithm and one CPLEX run.The evaluation also compares precomputation procedures and describes the experimental machine and software setup.Source: §6.1 · p. 11, §6 · p. 11

6.1 Runtime of Privacy Quantification Algorithms

  • The proposed Algorithms 1, 3, and 5 significantly outperform CPLEX; precomputation runtimes increase with n, and Algorithm 4 is more susceptible to am, with larger am yielding higher runtime.Algorithm 4’s higher runtime with larger am results from its binary search over [0, am].Source: §6.1 · pp. 11–12
  • Precomputation Algorithms 2 and 4 have complexities O(n^3) and O(n^2 log n + m log m), respectively, and can be time-consuming for large n or am because they solve n*(n−1) LFP problems.The authors identify parallel computing as a possible improvement because those problems are independent and precomputation is done once before release.Source: §6.1 · p. 12
  • Algorithm 1 is fastest for small T, Algorithm 3 is preferable for T in [5, 300], and Algorithm 5 with precomputation is fastest for T > 300, with runtime nearly constant as T increases.The authors conclude that the choice can be adapted to the known T; there is no single most efficient algorithm without it.Source: §6.1 · p. 12

6.2 Impact of Temporal Correlations on TPL

  • With stronger temporal correlations (smaller s), privacy leakage grows more steeply and remains on the rise longer, ultimately reaching a higher level.Under the tested settings, leakage first rises sharply and then stabilizes as it approaches its supremum.Source: §6.2 · p. 12
  • At s = 0.005, noticeable leakage growth lasts about 8 timestamps for ε = 1 and about 80 for ε = 0.1, but eventually the latter is not substantially lower under stronger correlations.The passage attributes this convergence to adversaries eventually learning sufficient information from continuous releases.Source: §6.2 · p. 12
  • For the same s, TPL is smaller when the transition-matrix dimension n is larger.Source: §6.2 · p. 12

6.3 Evaluation of Data Releasing Algorithms

  • For 1-DPT, Algorithm 8 has better data utility because it exactly achieves the desired privacy level; for 2-DPT, it outperforms Algorithm 7 when T is short, while strong correlation reduces utility.The 2-DPT comparison measures absolute Laplace noise, with higher noise indicating lower utility.Source: §6.3 · p. 13

7 RELATED WORK

Prior work studies continual-observation DP and correlated-data privacy, but the paper distinguishes its focus on temporal correlations in continuous aggregate release. It also relates this setting to debates about what privacy event-level guarantees provide for an individual’s full data stream.

7 RELATED WORK

  • Earlier continual-observation studies addressed settings including high-dimensional data, infinite sequences, and real-time publishing, while the authors report no prior study of temporal-correlation risk for continuous aggregate release.They distinguish their focus from, which considers Markov-chain correlation knowledge for private-location release.Source: §7 · p. 13
  • Correlated-data privacy work includes PufferFish, Markov Quilt, and sensitivity-based frameworks, mostly for user-user correlations in one-shot release rather than one user’s temporal data in continuous release.The passage cites PufferFish, Markov Quilt, and related approaches.Source: §7 · p. 13
  • The authors connect their finding that event-level privacy loss may increase over time to the Personal Data Principle, while stating that user-level privacy behaves as expected.For infinite streams or unknown release end times, they note that event-level or w-event privacy may be used.Source: §7 · p. 13

8 CONCLUSIONS

The paper formalizes and analyzes privacy loss against adversaries who know temporal correlations, finding that event-level privacy loss may increase over time while user-level privacy behaves as expected. It also presents fast quantification algorithms and identifies further research on other correlation models and adapting prior continuous-release studies.

8 CONCLUSIONS

  • The analysis finds that event-level privacy loss may increase over time under temporal correlations, while user-level privacy guarantees behave as expected.Source: §8 · p. 14
  • The paper formalizes, analyzes, and calculates privacy loss against adversaries with knowledge of temporal correlations, and designs fast algorithms for quantifying TPL.The conclusion says the algorithms enable private data release in real time.Source: §8 · p. 14
  • Future directions include studying other correlation models and using the methods to enhance earlier continuous-release studies that neglected temporal correlations.Source: §8 · p. 14

APPENDIX A PROOF OF THEOREM 2

The proof derives the theorem by relating conditional output probabilities across time points. It uses conditional independence of outputs given the underlying data and the same mechanism with a shared output domain.

APPENDIX A PROOF OF THEOREM 2

  • Conditional independence of outputs given D_t lets the proof derive Equation (30) from Equation (29) and Equation (32) from Equation (31).Source: Appendix A · p. 15
  • The step from Equation (30) to Equation (31) uses the same DP mechanism at each time and identical output domains, allowing a maximizing output choice to apply across terms.The proof then derives Equation (31) from Equation (30) and concludes the theorem.Source: Appendix A · p. 15

APPENDIX B PROOF OF THEOREM 3

The proof derives overall privacy leakage for consecutive mechanisms and extends the argument to sequences of mechanisms. It notes that Equation (31) may be only an upper bound under varying mechanisms or query sensitivities.

APPENDIX B PROOF OF THEOREM 3

  • The leakage expressions compare output probabilities conditioned on the affected data points with probabilities conditioned on their alternatives.The proof fragments show log probabilities for outputs conditioned on D_t, D_{t+1}, and their primed alternatives.Source: Appendix B · p. 15
  • The proof treats the overall privacy leakage of mechanisms M_t through M_{t+j} in terms of DPT, with separate arguments for j = 1 and j ≥ 2.The passage states that the j = 1 case follows before introducing the sequence formulation, and that the theorem follows for j ≥ 2.Source: Appendix B · p. 15
  • When mechanisms or query sensitivities differ across times, Equation (31) may be an upper bound rather than the supremum of TPL.The passage specifically qualifies Equation (31) under these conditions.Source: Appendix B · p. 15

APPENDIX C PROOF OF THEOREM 5

The proof establishes an optimal solution for the linear-fractional problem using Dinkelbach’s Theorem and Lemma 1. It derives the solution by selecting variable values according to coefficient signs.

APPENDIX C PROOF OF THEOREM 5

  • For the maximization step, variables with positive coefficients take the upper bound e^(αB_t−1)m, while variables with nonpositive coefficients take m.The proof uses this sign-based assignment to construct an optimal solution under the stated constraints.Source: Appendix C · p. 15
  • The proof reduces the optimization to maximizing a linear expression under the transformed bounds 1 ≤ y_j ≤ e^(αB_t−1).Replacing x_j with y_j and setting x_n = m yields an equivalent objective.Source: Appendix C · p. 15
  • The proof applies Dinkelbach’s Theorem to establish that the proposed x* is optimal for the linear-fractional problem.It rewrites the objective using Q(x) = qx and D(x) = dx, then uses Lemma 1 to establish optimality.Source: Appendix C · pp. 15–16

APPENDIX D PROOF OF COROLLARY 2

The proof rules out both q = d and q < d, concluding that q > d under the stated inequalities.

APPENDIX D PROOF OF COROLLARY 2

  • The proof excludes q = d and q < d by contradiction, so q > d.The q = d case contradicts Inequality (22), while q < d contradicts Inequality (23).Source: Appendix D · p. 16

APPENDIX E PROOF OF COROLLARY 3

The appendix proves Corollary 3 from Equation (24) and proves Theorem 6’s zero-leakage case when transition-matrix rows are identical.

APPENDIX E PROOF OF COROLLARY 3

  • Corollary 3 follows directly from Equation (24).The appendix states this as the reason the corollary holds.Source: Appendix E · p. 16

APPENDIX F PROOF OF THEOREM 6

  • When the transition-matrix rows are identical, Algorithm 1 removes all bits from q+ and d+, yielding q = d = 0 and L(·) = 0.The proof says the flag update continues until both sets are empty.Source: Appendix F · p. 16

APPENDIX G PROOF OF THEOREM 7

These appendices prove properties of the optimization cases and leakage functions, including piecewise behavior and conditions for a finite supremum.

APPENDIX G PROOF OF THEOREM 7

  • The proof derives a maximum solution α and concludes that L(x) = x.For rows with q_i = 1 and d_i = 0, Algorithm 1 leaves q = 1 and d = 0 and sets the flag update to false.Source: Appendix G · p. 16

APPENDIX H PROOF OF THEOREM 8

  • The proof reduces the possibilities to k cases and checks each case using Inequalities (22) and (23).In case k, q_1d_1 > q_(e^α)+1d_(e^α)+1.Source: Appendix H · p. 16

APPENDIX I PROOF OF THEOREM 9

  • As α increases, q and d move through cases at transition points, making f_q,d(α) a piecewise function.The proof identifies transition points by solving for successive case boundaries; after the final transition, q and d fall into case k.Source: Appendix I · p. 16

APPENDIX J PROOF OF THEOREM 10

  • For α > 0, the functions f and f′ have at most one intersection.If their endpoint values satisfy the stated ordering on an interval, the proof concludes f(α) remains larger than f′(α) within it.Source: Appendix J · p. 17

APPENDIX K PROOF OF THEOREM 11

  • When d = 0 and q = 1, BPL and FPL increase linearly without limit; for d = 0 and q ≠ 1, a supremum exists only if ϵ < log(1/q).For d ≠ 0, the proof says the positive solution always exists and is greater than 1.Source: Appendix K · p. 17
Loading 1711.11436v3…