PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Filtering

Jerome Le Ny, George J. Pappas

arXiv:1207.4305v2math.OCcs.CR

TL;DR

The paper addresses how systems such as smart grids can release filtered user signals without exposing private data streams. It applies differential privacy to dynamic multi-participant systems, Kalman filtering, and stable filters for single event streams, designing approximations that minimize privacy-induced distortion. The paper reports accurate publication for systems with small incremental gains and discusses mechanisms and empirical comparisons including ZFE and MMSE filtering.

  • Problem

    Continuous data release in monitoring and control systems can expose users’ private signals, while anonymization does not guarantee privacy against public side information.

  • Method

    The paper introduces differential privacy for filtered outputs of dynamic systems and develops approximations for multi-participant inputs, Kalman filters, and single event streams.

  • Results

    Accurate results can be published for systems with small incremental gains with respect to individual input channels.

  • Takeaways & Limitations

    Differentially private mechanisms can protect time-varying user signals while releasing sanitized filtered outputs from centralized or decentralized system settings.

Abstract

from arXiv · show

Emerging systems such as smart grids or intelligent transportation systems often require end-user applications to continuously send information to external data aggregators performing monitoring or control tasks. This can result in an undesirable loss of privacy for the users in exchange of the benefits provided by the application. Motivated by this trend, this paper introduces privacy concerns in a system theoretic context, and addresses the problem of releasing filtered signals that respect the privacy of the user data streams. Our approach relies on a formal notion of privacy from the database literature, called differential privacy, which provides strong privacy guarantees against adversaries with arbitrary side information. Methods are developed to approximate a given filter by a differentially private version, so that the distortion introduced by the privacy mechanism is minimized. Two specific scenarios are considered. First, the notion of differential privacy is extended to dynamic systems with many participants contributing independent input signals. Kalman filtering is also discussed in this context, when a released output signal must preserve differential privacy for the measured signals or state trajectories of the individual participants. Second, differentially private mechanisms are described to approximate stable filters when participants contribute to a single event stream, extending previous work on differential privacy under continual observation.

I. INTRODUCTION

The paper introduces differential privacy into systems theory to release useful filtered signals while protecting users’ dynamic data streams. It develops mechanisms for multi-participant systems, Kalman filtering, and single event streams, targeting low distortion.

  • Motivation: Anonymization may not protect individual signals because public side information can enable inference about private data.Differential privacy instead controls leakage against adversaries with arbitrary side information.
  • Motivation: The paper frames privacy as a systems-theoretic concern for applications that continuously collect user signals for monitoring, control, or decision-making.Examples include smart grids, traffic monitoring, population health monitoring, recommendation systems, and industrial control.
  • Contributions: The paper formulates release of dynamical-system outputs while preserving differential privacy for inputs contributed independently by multiple participants.The approach seeks accurate publication when systems have small incremental gains with respect to individual input channels.
  • Contributions: The authors extend the dynamic-systems results to differentially private Kalman filtering, allowing additional process information to support more accurate releases.The protected quantities may include measured signals or individual participants’ state trajectories.
  • Contributions: For a single integer-valued event stream, the paper proposes differentially private approximations of stable filters that minimize mean squared error from the privacy mechanism.This setting extends prior work on differential privacy under continual observation.

A. Definition

This section defines differential privacy for randomized mechanisms over adjacent datasets and develops equivalent characterizations and a post-processing property. The guarantee limits how much an individual’s participation changes output distributions, even against side information.

  • Definition: A dataset mechanism maps a dataset and randomness to an output, while a query maps datasets to numerical answers that a mechanism can perturb.The section treats mechanisms as probabilistic algorithms for answering queries.
  • Definition: Two datasets are adjacent when they differ in the data of a single individual, establishing the privacy comparison used by the definition.The adjacency relation is symmetric.
  • Definition: Differential privacy requires output probabilities for adjacent datasets to remain close under parameters ϵ and δ.When δ = 0, the mechanism is called ϵ-differentially private.
  • Characterizations: The paper gives equivalent measure-theoretic characterizations of differential privacy, including bounds involving a δ-bounded positive measure.The authors state that the lemma’s technical characterization appears to be new.
  • Post-processing: Post-processing preserves the same differential-privacy parameters when the released output is transformed through a dataset-independent probability kernel.This permits accuracy-improving post-processing without weakening privacy.

B. Basic Differentially Private Mechanisms

Differentially private query mechanisms trade utility for privacy by perturbing numerical answers according to query sensitivity. The Laplace mechanism provides a basic construction whose noise scale depends on sensitivity and privacy requirements.

  • Basic mechanisms: Answering a useful query privately requires a trade-off between privacy and utility because discarding all dataset information is private but uninformative.The section focuses on numerical queries with finite-dimensional outputs.
  • Sensitivity: Query sensitivity measures the largest output change between adjacent datasets and guides the design of differentially private mechanisms.For vector-valued queries, sensitivity is defined using the selected output norm.
  • Laplace mechanism: The Laplace mechanism releases q(d) + w, adding independent zero-mean Laplace noise with scale determined by sensitivity and the privacy parameter ϵ.For δ = 0, the construction uses noise scale b = ∆1q/ϵ.
  • Laplace mechanism: For repeated scalar queries, sensitivity grows linearly with the number of coordinates, while the resulting noise variance grows quadratically.This prevents an adversary from averaging away the noise across coordinates.

2) The Gaussian Mechanism:

The Gaussian mechanism adds Gaussian noise calibrated to query sensitivity to provide (ϵ, δ)-differential privacy. The paper extends this reasoning to causal dynamic systems and finite-time privacy criteria.

  • 2) The Gaussian Mechanism:: For ϵ = ln 2 and δ = 0.05, the required Gaussian-noise standard deviation is about 2.65 times q’s ℓ2-sensitivity.
  • 2) The Gaussian Mechanism:: The privacy calibration factor κ(δ, ϵ) can be bounded by O(ln(1/δ))^1/2/ϵ.
  • 2) The Gaussian Mechanism:: For dynamic systems, causal mechanisms are evaluated through finite-time truncations, and finite-dimensional privacy criteria are equivalent to signal-space differential privacy.Causality ensures future inputs do not affect outputs released up to time T.

B. Basic Dynamic Mechanisms

The paper develops Laplace and Gaussian mechanisms for causal dynamic systems with multiple participant input signals. The resulting privacy noise is calibrated to the system’s induced sensitivity.

  • B. Basic Dynamic Mechanisms: Theorem 4 generalizes Laplace and Gaussian privacy mechanisms to causal dynamic systems.
  • B. Basic Dynamic Mechanisms: For linear systems with ri = 2, Gaussian output noise with σ ≥ κ(δ, ϵ) max1≤i≤n{∥Gi∥∞bi} guarantees (ϵ, δ)-differential privacy.

C. Filter Approximation Set-ups for Differential Privacy

The paper compares input and output perturbation architectures for releasing private dynamic-system signals. It then applies these mechanisms to Kalman filtering with privacy defined over measurements or state trajectories.

  • C. Filter Approximation Set-ups for Differential Privacy: Output perturbation adds a single noise source after the system, with error determined by the system’s maximum participant sensitivity.
  • C. Filter Approximation Set-ups for Differential Privacy: Input perturbation adds independent white Gaussian noise to each participant’s input before the signals pass through the system.
  • C. Filter Approximation Set-ups for Differential Privacy: The two error bounds depend on the system and participant count, so neither perturbation scheme dominates in every circumstance.When n is small or participant transfer-function bandwidths do not overlap, input perturbation can have the smaller bound.
  • C. Filter Approximation Set-ups for Differential Privacy: For averaging over l periods, κ(δ, ϵ)^2Bn/l is the input-perturbation MSE, while κ(δ, ϵ)^2B is the output-perturbation MSE.
  • C. Filter Approximation Set-ups for Differential Privacy: The Kalman-filtering setup guarantees differential privacy for individual state trajectories and supports privacy-preserving released estimates.The paper also applies the mechanisms to traffic monitoring.

B. Filter Redesign for Stable Systems

For stable systems, the paper redesigns filters to reduce the distortion caused by output perturbation while preserving differential privacy. The design uses sensitivity bounds and convex sufficient conditions.

  • B. Filter Redesign for Stable Systems: Output perturbation can improve MSE, motivating filter redesign relative to the Kalman filter.
  • B. Filter Redesign for Stable Systems: The redesigned filters are stable full-order filters whose outputs estimate linear combinations of individual system states.
  • B. Filter Redesign for Stable Systems: The H∞ norm of the filter’s transfer function measures ℓ2-sensitivity to changes in an individual state trajectory.
  • B. Filter Redesign for Stable Systems: The output-perturbation MSE is minimized through an optimization problem over admissible filter matrices.
  • B. Filter Redesign for Stable Systems: Theorem 6 supplies convex sufficient Linear Matrix Inequality conditions for filter matrices satisfying the stability and sensitivity constraints.

V GCS

The filter-design constraints are transformed into LMIs through congruence and change-of-variable transformations. The resulting optimization trades estimation error against ℓ2-sensitivity while noting numerical conditioning concerns.

  • Congruence transformations and the mapping between filter variables produce the theorem’s LMI constraints.The transformations recover the original constraints when the auxiliary conditions are satisfied.
  • The transformed variables allow admissible filter matrices to be recovered from the LMI solution.The construction uses positive-definite and nonsingular auxiliary matrices.
  • The design minimizes estimation error together with filter ℓ2-sensitivity to reduce overall MSE.The variables μ_i and λ can be minimized subject to the theorem’s LMI constraints.
  • Including certain variables directly can cause ill-conditioning when matrices U_i and V_i are inverted.The text points to a recommended fix for this numerical issue.

C. Unstable Systems

This section develops privacy-preserving filter design for unstable-system settings and motivates it with traffic monitoring. The formulation balances estimation accuracy with sensitivity while exposing stability and modeling limitations.

  • C. Unstable Systems: If the dynamics are unstable, the presented linear filter-design approach does not directly apply.The discussion therefore restricts the filter class and imposes stability requirements on the error dynamics.
  • C. Unstable Systems: The restricted filter class includes the one-step delayed Kalman filter and uses G_i as the remaining design variable.Setting F_i = A_i − G_iC_i makes the error dynamics independent of x_i.
  • C. Unstable Systems: Minimizing MSE under differential-privacy constraints becomes an optimization problem that can be checked through LMIs and solved by semidefinite programming.The design variables include λ_i, μ_i, and G_i.
  • V. A TRAFFIC MONITORING EXAMPLE: Traffic monitoring estimates average vehicle velocity while protecting individual trajectories that may reveal driving behavior and frequently visited locations.The service releases an estimate of the participating vehicles’ average velocity at each sampling period.
  • V. A TRAFFIC MONITORING EXAMPLE: Temporal aggregation may fail to protect individual trajectories when adversaries exploit relationships between measurements over time.The passage identifies this as a limitation of temporal cloaking.

1) Numerical Example:

The numerical example evaluates privacy-preserving Kalman filtering for traffic velocity and then examines private approximations of stable filters for event streams. Results show substantial utility differences across mechanisms and a trade-off between steady-state error and convergence speed.

  • 1) Numerical Example:: Almost 26 km/h RMSE makes unmodified input-noise injection essentially unusable in the traffic example.The example uses n = 200 participants and privacy parameters ϵ = ln 3 and δ = 0.05.
  • 1) Numerical Example:: 0.31 km/h RMSE is achieved by the additional-measurement-noise scheme, while output noise injection with Kalman filter K yields 2.41 km/h.For K, the reported H∞ norm is 0.57.
  • 1) Numerical Example:: The better steady-state RMSE of input noise injection comes with convergence exceeding 1 min because of the larger privacy-preserving noise.This can be impractical when the system must respond quickly to abrupt velocity changes.
  • VI. FILTERING EVENT STREAMS: For event streams, the paper approximates a general linear stable filter while preserving event-level differential privacy.The event-level relation hides the presence or absence of an individual event at a particular time.
  • VI. FILTERING EVENT STREAMS: For integer-valued inputs, a filter’s ℓp sensitivity equals the ℓp norm of its impulse response; for p = 2, this is the H2 norm.This sensitivity relation supports calibration of input- and output-noise mechanisms.
  • VI. FILTERING EVENT STREAMS: The ZFE mechanism uses a stable minimum-phase filter and its inverse, with Gaussian noise scaled by κ(δ, ϵ)∥G1∥2.Its MSE depends on ∥G1∥2^2 and the equalized filter norm.
  • VI. FILTERING EVENT STREAMS: The ZFE lower bound is attained when |G1(e^jω)|^2 = λ|G(e^jω)|, and it can be approached with stable rational minimum-phase filters.The corresponding filters optimize the approximation within the stated class.

A. Exploiting Additional Public Knowledge

The paper uses publicly known input statistics to design a second filter that improves approximation utility after a private signal has been released. Privacy remains guaranteed because the second filter processes only that already private signal.

  • A. Exploiting Additional Public Knowledge: The MMSE mechanism designs G2 using publicly known second-order statistics of the input and intermediate signals.The input is assumed wide-sense stationary, with known mean and autocorrelation.
  • A. Exploiting Additional Public Knowledge: With G2 restricted to a finite-impulse-response filter, its coefficients are obtained from a Yule-Walker system.The filter order is N and the coefficient vector is h = [h0, ..., hN]^T.
  • A. Exploiting Additional Public Knowledge: Applying G2 after the private signal preserves differential privacy even when the input’s statistical assumptions are violated.Violating those assumptions affects performance but not the privacy guarantee.
  • A. Exploiting Additional Public Knowledge: For the example input, the MMSE mechanism achieves empirical MSE 4.6 versus 5.8 for ZFE.The comparison illustrates utility gains from exploiting additional input knowledge.

B. Related Work

The paper situates its filtering mechanisms among approaches using binary trees, alternate-basis perturbations, and state-space realizations, while identifying practical limitations and future research needs.

  • Related approaches: Binary-tree methods track intermediate calculations or system states to reduce privacy noise, but their usefulness for practical stable filters can be limited by large MSE.These approaches include unstable accumulators, filters with monotonic slowly decaying impulse responses, and general linear systems.
  • Related approaches: Alternate-basis perturbation can exploit sparse signal representations, but such methods are typically noncausal and nonrecursive, with processing that grows over time.Examples include perturbing Fourier or wavelet-basis coefficients, including the largest Discrete Fourier Transform coefficients.
  • Paper contribution: The paper discusses mechanisms that preserve individual users’ differential privacy when time-varying signals are sent to a trusted server for sanitized filtered-output release.This establishes the paper’s central setting for privacy-preserving filtering of user data streams.
  • Paper contribution: Decentralized versions of the Section III mechanism can operate without a trusted server through cryptographic techniques.The passage identifies cryptographic implementation as the route to removing the trusted-server requirement.
  • Open directions: Future dynamical-systems research includes better filtering mechanisms and understanding privacy-or-security versus performance trade-offs in large-scale control systems.The conclusion presents these as open directions rather than resolved results.
Loading 1207.4305v2…