PaperlayerView exact revision on arXiv

Source-linked AI summary

Age-Dependent Differential Privacy

Meng Zhang, Ermin Wei, Randall Berry, Jianwei Huang

arXiv:2209.01466v1cs.CRcs.ITcs.NIcs.PFmath.IT

TL;DR

Classical privacy frameworks largely overlook how data freshness affects privacy guarantees for time-varying databases. The paper introduces age-dependent DP, connecting it to classical DP and incorporating aging into single- and multi-query analysis. Its case studies find bounded accuracy loss for aging plus noise injection at arbitrarily small single-query privacy risk, unlike unbounded loss for noise-only mechanisms.

  • Problem

    Classical DP largely overlooks data freshness in time-varying databases, despite the possibility that outdated data reveals less about a user's current status.

    Source: A. Background · p. 2

  • Method

    The paper defines age-dependent DP using the stochastic nature of time-varying data and analyzes its connection to classical DP, composition, and privacy–utility tradeoffs with aging and noise injection.

    Source: §VII · p. 31

  • Results

    At arbitrarily small single-query privacy risk, combining aging and noise injection incurs bounded accuracy loss, whereas noise-only benchmark loss grows unbounded.

    Source: 3) Numerical Results · p. 28

  • Takeaways & Limitations

    Aging, alongside noise injection, can protect privacy in time-varying data, and the case studies show more favorable privacy–utility tradeoffs than noise-only classical mechanisms.

    Source: §VII · p. 31

Abstract

from arXiv · show

The proliferation of real-time applications has motivated extensive research on analyzing and optimizing data freshness in the context of \textit{age of information}. However, classical frameworks of privacy (e.g., differential privacy (DP)) have overlooked the impact of data freshness on privacy guarantees, which may lead to unnecessary accuracy loss when trying to achieve meaningful privacy guarantees in time-varying databases. In this work, we introduce \textit{age-dependent DP}, taking into account the underlying stochastic nature of a time-varying database. In this new framework, we establish a connection between classical DP and age-dependent DP, based on which we characterize the impact of data staleness and temporal correlation on privacy guarantees. Our characterization demonstrates that \textit{aging}, i.e., using stale data inputs and/or postponing the release of outputs, can be a new strategy to protect data privacy in addition to noise injection in the traditional DP framework. Furthermore, to generalize our results to a multi-query scenario, we present a sequential composition result for age-dependent DP under any publishing and aging policies. We then characterize the optimal tradeoffs between privacy risk and utility and show how this can be achieved. Finally, case studies show that to achieve a target of an arbitrarily small privacy risk in a single-query case, combing aging and noise injection only leads to a bounded accuracy loss, whereas using noise injection only (as in the benchmark case of DP) will lead to an unbounded accuracy loss.

I. INTRODUCTION

The paper proposes age-dependent differential privacy for time-varying data, where freshness and temporal correlation affect privacy guarantees. It combines aging with noise injection, extends privacy analysis to multiple queries, and studies privacy–utility tradeoffs.

A. Background

  • The paper frames freshness as a privacy concern because outdated data may reveal less about a user's current status, while classical DP can give a loose bound for inference accuracy.Its motivating example reports that classical DP's upper bound can be as high as 88%, even as the adversary's estimate accuracy diminishes with data age.Source: A. Background · pp. 2–3

B. Contributions

  • Age-dependent DP accounts for potentially diminishing privacy leakage from delayed data, addressing freshness effects overlooked by existing privacy frameworks.The proposed framework applies to time-varying data; time-invariant information such as genome data remains within the classical DP focus.Source: A. Background · pp. 2–3, B. Contributions · p. 5
  • Connecting classical DP to age-dependent DP enables privacy guarantees that exploit both noise injection and aging, including input and output timing.The framework also characterizes the factor governing how age-dependent privacy risk decays over time.Source: A. Background · p. 4, B. Contributions · p. 5
  • For multiple queries, age-dependent composition depends on input and output timing, and peak privacy risk can remain bounded even for infinitely many queries under a characterizable condition.Classical sequential composition results, by contrast, depend on the number of queries.Source: A. Background · p. 4, B. Contributions · p. 5
  • Combining aging and noise injection achieves bounded accuracy loss at arbitrarily small privacy risk, while noise-only loss grows unbounded in the single-query case.The paper attributes part of this difference to its focus on adversaries inferring the current database state, unlike classical DP, which assumes no data distribution or adversary type.Source: B. Contributions · p. 5

A. Age of Information

  • Prior work on age of information largely did not address privacy; related privacy work generally left data timeliness or temporal correlation uncharacterized.The cited exception studied age-minimal sensing with DP but not an age-based DP variant; considered time correlation but not timeliness or varying publishing and aging policies.Source: A. Age of Information · p. 5, B. Differential Privacy · p. 6

A. Model

  • The model considers event-level adversaries seeking the current database state, with users' privacy-sensitive data modeled as stationary finite-state processes.The analysis assumes the platform and adversary know the underlying probability models; protecting user-level history is left for future work.Source: A. Model · pp. 7–8

B. Differential Privacy

The example shows that an attacker’s success can fall as a DP-protected release ages, motivating aging as another privacy strategy alongside noise injection. Classical DP bounds how much a mechanism’s output distribution changes when one user’s data changes, with stronger protection trading off against accuracy.

B. Differential Privacy

  • Classical DP bounds output-distribution changes between neighboring databases that differ in one user’s data, with randomness taken over the mechanism’s output.The paper denotes its classical privacy risk by εC and notes that Laplace or Gaussian noise is a standard approach to achieving DP.Source: B. Differential Privacy · p. 9
  • The Laplace mechanism’s variance is 2/(ϵ2 CI2), so a smaller εC requires larger variance and greater statistical utility loss.The paper uses outcome variance to characterize L2 accuracy loss (mean square error).Source: B. Differential Privacy · pp. 9–10

C. A Motivating Example

  • 88% attack accuracy at εC = 2 falls to approximately 65%, 58%, and 53% after 3, 6, and 10 days, respectively, approaching a 50% random guess.The immediate-release accuracy is reported for the same example; the delayed values are for the same εC-DP mechanism.Source: C. A Motivating Example · p. 10
  • At six days, εC = 2 gives approximately the same attack accuracy as an immediate release with εC = 0.3, illustrating aging as an alternative to more noise.The authors motivate an age-dependent privacy framework that accounts for data timeliness.Source: C. A Motivating Example · pp. 10–11

IV. AGE-DEPENDENT DIFFERENTIAL PRIVACY: THE SINGLE-QUERY CASE

Age-dependent DP extends classical DP by evaluating a mechanism’s output against a later database state, incorporating data evolution and output age. Its privacy guarantee relates to classical DP and can improve as temporal dependence decays.

A. Definitions

  • Age-dependent DP evaluates a single-query mechanism’s output on X0 conditional on a later database state Xt, accounting for randomness in both the mechanism and the stochastic process.Classical εC-DP is the t = 0 special case; the framework is developed for single-query, time-invariant mechanisms here.Source: A. Definitions · p. 11
  • For processes with ergodicity or mixing properties, increasingly stale outputs can make the conditional probabilities indistinguishable, yielding asymptotically perfect privacy.The paper interprets t as the age of the output M(X0).Source: A. Definitions · pp. 11–12
  • An artificially aged mechanism is classically εC-DP if and only if the original mechanism is (εC, t)-age-dependent DP.This establishes a direct correspondence between the two privacy notions through aging.Source: A. Definitions · p. 12

1) Total Variation Distance:

  • The maximal total variation distance ∆(t) measures separation between users’ t-step transition distributions of the reversed process and is used to characterize privacy risk.The paper notes that many stochastic processes have a ∆(t) that diminishes over time; geometric ergodicity is one example property discussed.Source: 1) Total Variation Distance · pp. 12–13

2) Mechanism-Dependent Guarantee:

The mechanism-dependent guarantee bounds age-dependent privacy risk using classical DP risk and the process’s maximal total variation distance. Under suitable temporal structure, aging alone can also provide a guarantee with a similar convergence rate.

2) Mechanism-Dependent Guarantee:

  • For an εC-DP mechanism, the age-dependent risk is bounded by ϵ(t) = ln(1 + ∆(t) · (exp(ϵC) − 1)), linking classical risk to maximal total variation distance.The theorem applies to arbitrary underlying processes; when ∆(t) decays under mixing or geometric ergodicity, the age-dependent risk converges to zero at the same rate as (exp(ϵC)−1)∆(t).Source: 2) Mechanism-Dependent Guarantee · pp. 13–14
  • Under irreducible, aperiodic, reversible Markov-chain assumptions for each agent, aging alone can ensure an age-dependent privacy guarantee with a similar convergence rate.This guarantee does not require noise injection.Source: 2) Mechanism-Dependent Guarantee · p. 14

C. Proof of Theorem 1

  • The proof bounds privacy risk by first bounding changes in expected values under small distribution changes measured by ∆(t).The proof introduces a lemma for this expected-value bound before relating risk to εC and ∆(t).Source: C. Proof of Theorem 1 · p. 14

D. Summary

The section extends age-dependent DP to multi-query mechanisms, where privacy risk depends on both the freshness of inputs and the timing of output releases. It gives a sequential composition guarantee and characterizes how privacy risk evolves across publishing epochs.

V. AGE-DEPENDENT DIFFERENTIAL PRIVACY: SEQUENTIAL COMPOSITION

  • The prior single-query analysis motivates this extension because real-time applications frequently publish data updates, requiring privacy guarantees for sequential queries.The section also frames the analysis as a tradeoff between privacy and utility, with utility characterized by age of information.Source: D. Summary · p. 16, §V · p. 16, A. The General Definition and… · p. 17

A. The General Definition and Composition

  • Age-dependent DP for multi-query mechanisms accounts for publishing and aging policies, with each query using an aged input and publishing its output at a specified time.The mechanism tracks the history of outputs published by time t.Source: A. The General Definition and… · pp. 17–18
  • Privacy risk decreases within each epoch when Δ(t) diminishes, then spikes at the next epoch’s start, while age of information increases within an epoch.The peak privacy risk for epoch n is defined as ϵ(S_n).Source: Figure 2 · p. 18, A. The General Definition and… · p. 19
  • The composition theorem bounds multi-query privacy risk over time using each query’s classical DP guarantee and the data-timeliness term Δ(t − S_n + A_n), assuming the database process is Markovian.The risk in each epoch also depends on the prior in-epoch risk.Source: A. The General Definition and… · p. 19
  • When Δ(t − S_n + A_n) = 1, the composition bound reduces to classical basic composition for a static database.The authors note that tighter bounds may be possible by combining data timeliness with more sophisticated composition techniques; this is left for future work.Source: A. The General Definition and… · p. 19

B. Tradeoff Between Privacy and Utility

This section develops a privacy–utility optimization for multi-query mechanisms using peak privacy risk and a noise-aware peak age penalty. It establishes that an optimal mechanism can use the same aging, publishing interval, and single-query privacy parameter across epochs.

B. Tradeoff Between Privacy and Utility

  • The utility penalty f(t, ϵ_C) increases with age t and decreases with the single-query privacy parameter ϵ_C, capturing losses from staleness and injected noise.The peak age used for the simplified mechanism is A + S̄.Source: B. Tradeoff Between Privacy and Utility · p. 20
  • An optimal solution to the tradeoff problem is a simplified multi-query mechanism, so policies need not vary across epochs and optimization reduces to A, S̄, and ϵ_C.The problem seeks to minimize peak privacy risk subject to a peak age penalty constraint.Source: B. Tradeoff Between Privacy and Utility · pp. 20–21
  • For an equal-spacing policy, a finite peak privacy risk exists only when Δ(A)Δ(S̄ − A)exp(ϵ_C) < 1; otherwise, the risk diverges to infinity.Under the condition, the peak risk is the unique fixed point of the recurrence, and fixed-point iteration is a contraction.Source: B. Tradeoff Between Privacy and Utility · pp. 21–22
  • The in-epoch peak privacy risk increases across epochs toward the fixed point, reaching an approximate fixed point after five epochs in the illustration.Figure 3 illustrates privacy risk and peak privacy risk for equal-spacing policies.Source: Figure 3 · p. 21, B. Tradeoff Between Privacy and Utility · p. 22

C. Optimization Algorithms

The optimization approach focuses on geometrically decaying Δ(t) and derives a relation among aging, publishing interval, and noise when the nonnegativity constraint on aging is not binding. It relaxes integer constraints to obtain an approximate solution.

C. Optimization Algorithms

  • The analysis specializes to geometrically decaying Δ(t), motivated by processes for which that decay is shown in the appendix and Section IV.The coefficients are restricted to ρ ∈ (0, 1) and c ≥ 1.Source: C. Optimization Algorithms · p. 22
  • When A ≥ 0 is not binding, the optimum satisfies ln(ρ − 1)/S̄ = ln(2c^2) + ϵ_C.The equivalent relation is ln(ρ − 1) = S̄[ln(2c^2) + ϵ_C].Source: C. Optimization Algorithms · p. 23
  • With aging in use, decreasing ϵ_C leads to a shorter inter-publishing time S̄, meaning updates are published more often.The optimization relaxes integer constraints and rounds the resulting A and S̄ to their nearest integers for an approximate solution.Source: C. Optimization Algorithms · p. 23

Appendix E.

The appendix describes solution procedures for the privacy–utility optimization and discusses when improving one metric need not improve the other. It also presents a two-state Markov-chain case study and two utility metrics.

Appendix E.

  • When f(t, ϵ_C) is convex, the reformulated problem can be solved by standard solvers; when it is non-convex, the authors use a heuristic with complexity O(K log(1/φ)).The heuristic exhaustively searches ϵ_C and uses bisection for A.Source: Appendix E · p. 24
  • When A = 0, the heuristic searches ϵ_C exhaustively and uses bisection to choose S̄ satisfying f(S̄, ϵ_C) = f̄, with complexity O(K log(1/φ)).It selects the ϵ_C and corresponding S̄ that minimize the objective.Source: Appendix E · p. 24

D. Possibility of No Tradeoffs

  • Under the stated sufficient condition, increasing the allowed peak age penalty f̄ does not decrease the minimum objective value, so sacrificing privacy or utility need not improve the other metric.The paper says examples that satisfy and violate the condition appear in Section VI-A.Source: D. Possibility of No Tradeoffs · pp. 24–25

VI. NUMERICAL AND EXPERIMENTAL EXAMPLES

  • The case studies include a two-state Markov chain for comparing aging plus noise injection with the classical noise-only scheme, and an electricity-consumption experiment.The authors also state that the analysis extends to continuous-valued processes through an autoregressive model in Appendix I.Source: §VI · pp. 25–26

A. Two-State Markov Chain

  • The two-state example models each agent’s database as an identical discrete-time Markov chain and considers estimating the average location state across users.The example describes scenarios such as home occupancy or a user’s location on one of two roads.Source: A. Two-State Markov Chain · pp. 26–27
  • The study uses mean-square error and a failure rate as utility metrics, with the failure rate defined as a noise-aware age penalty for a binary estimate.The MSE uses the released data as the estimate when no prior information is available.Source: A. Two-State Markov Chain · p. 27

1) The single-query case:

The section derives age-dependent privacy guarantees for single- and multi-query mechanisms, then evaluates privacy–utility tradeoffs in numerical examples and London household electricity data. Across the single-query cases, combining aging with noise injection can keep accuracy loss bounded as privacy risk approaches zero, unlike noise injection alone.

1) The single-query case:

  • Any classical ϵC-DP single-query mechanism satisfying condition (41) also has an age-dependent DP guarantee parameterized by age t.This is the stated guarantee in Corollary 3.Source: 1) The single-query case · p. 27

3) Numerical Results:

  • For mean-square error, accuracy loss rises with age but converges to an upper bound, while privacy risk falls toward zero.Figure 4 presents these age-dependent results and the privacy–accuracy tradeoff.Source: Figure 4 · p. 28, 3) Numerical Results · p. 28

2) The multi-query case:

  • Any classical ϵC-DP multi-query mechanism based on (41) has an age-dependent DP guarantee with a peak privacy risk characterized by the stated bound.Corollary 4 gives the guarantee for the equal-spacing policy.Source: 2) The multi-query case · p. 28

3) Numerical Results:

  • As privacy risk approaches zero, combining aging and noise injection keeps single-query accuracy loss bounded, while the noise-only benchmark’s loss grows unbounded.The numerical studies report this pattern for the single-query case.Source: 3) Numerical Results · p. 28
  • In the failure-rate scenario, the proposed scheme can reduce accuracy loss by up to 1/3 versus the noise-only benchmark at the same privacy risk.The accuracy loss converges to 0.5 as age tends to infinity; different privacy–utility pairs require different ages and noise levels.Source: Figure 5 · p. 29, 3) Numerical Results · p. 29
  • For multi-query mechanisms, mean-square error admits a pair minimizing both peak accuracy loss and peak privacy risk, while failure rate has a tradeoff between them.Figure 6 reports both scenarios; in the failure-rate case, lower achievable peak privacy risk entails greater peak accuracy loss.Source: Figure 6 · p. 29, 3) Numerical Results · pp. 29–30

B. Electricity Consumption Forecast

  • For London household electricity data, privacy-risk bounds begin decreasing after age exceeds 18 hours, while accuracy loss levels off and remains finite as risk approaches zero.The noise-only benchmark’s accuracy loss grows unbounded as privacy risk approaches zero.Source: B. Electricity Consumption Forecast · pp. 30–31, Figure 7 · p. 31

VII. CONCLUSION

The conclusion presents age-dependent DP as a freshness-aware extension of differential privacy, with aging and noise injection as complementary privacy strategies.

VII. CONCLUSION

  • Combining aging with noise injection may significantly outperform classical noise-only mechanisms in privacy–utility tradeoffs.The conclusion also notes that aging protects privacy by using stale data.Source: §VII · p. 31
  • Age-dependent privacy risks compose for multi-query settings under any publishing and aging policies.Source: §VII · p. 31
  • The case studies find bounded accuracy loss for arbitrarily small privacy risk in a single-query case with aging and noise, versus unbounded loss with noise alone.Source: §VII · p. 31
  • The study assumes adversaries track only the most current user state and identifies historical-subset inference and adaptive composition as future directions.Source: §VII · p. 31

A. Basic Properties

  • Post-processing preserves a mechanism’s (ϵ, t)-age-dependent differential privacy guarantee under any mapping of its output.Source: A. Basic Properties · p. 34

C. Proof of Theorem 2

E. Proof of Proposition 4

These passages outline optimization and proof steps, introduce Markov-chain preliminaries, and state a convergence-rate relation for geometric ergodicity.

E. Proof of Proposition 4

  • The Proposition 4 proof drops constraint (55b) to form a Lagrangian and invokes KKT conditions, described as necessary for local optima.Source: E. Proof of Proposition 4 · p. 37

F. Preliminaries: Mixing, Ergodicity, and Markov Chains

1) Geometric Ergodicity:

G. Proof of Theorem 4

  • The proof of Theorem 4 proceeds by establishing monotonicity of ϵ(Sn), then showing an optimal solution exists.Source: G. Proof of Theorem 4 · p. 38
  • The recurrence for ϵn+1 is strictly increasing in ϵ and ϵC,n when the other listed policy variables are fixed.Source: G. Proof of Theorem 4 · p. 38

H. Proof of Corollary 2

The proof constructs a transformed feasible solution that preserves the objective while improving the peak age penalty and maintaining the same peak privacy guarantee.

H. Proof of Corollary 2

  • A transformed feasible solution can retain the same objective value while satisfying the constraint with a lower peak age penalty and the same peak privacy guarantee.The proof gives the new peak age penalty as ln(ρ−1) + S̄ − ϵC ln(ρ−1).Source: H. Proof of Corollary 2 · p. 40

I. Autoregressive Model

For a continuous-state autoregressive database, the analysis specializes to an AR(1) model and connects classical DP mechanisms to age-dependent DP. Numerical results show that combining aging with noise keeps accuracy loss bounded as privacy risk approaches zero, unlike a Laplace-noise-only benchmark.

I. Autoregressive Model

  • The continuous-state autoregressive model uses past states with coefficients ρ1, ρ2, … and i.i.d. normal noise N(0, σ2).The analysis then focuses on AR(1), where only ρ1 is nonzero.Source: §I · pp. 40–41
  • With i.i.d. normal innovations, the autoregressive process is time reversible.Source: §I · pp. 40–41
  • The analysis relates total variation distance to Kullback–Leibler divergence and gives an O(ρ^t) convergence rate for Δ(t).Source: §I · pp. 41–42
  • As privacy risk approaches zero, aging plus noise has bounded accuracy loss, while the Laplace-noise-only benchmark's loss grows unbounded.For fixed ϵC, accuracy loss increases with age t but converges to an upper bound as t → ∞.Source: Figure 8 · p. 42, §I · p. 42
  • Any ϵC-DP mechanism is also (ϵ(t), t)-age-dependent DP under the stated theorem.Source: §I · p. 42
Loading 2209.01466v1…