Differential privacy for symbolic systems with application to Markov chains

DOI10.1016/J.AUTOMATICA.2023.110908arXiv2202.03325MaRDI QIDQ6160739FDOQ6160739

Authors: Bo Chen, Kevin Leahy, Austin H. Jones, Matthew Hale 

Publication date: 26 June 2023

Published in: Automatica (Search for Journal in Brave)

Abstract: Data-driven systems are gathering increasing amounts of data from users, and sensitive user data requires privacy protections. In some cases, the data gathered is non-numerical or symbolic, and conventional approaches to privacy, e.g., adding noise, do not apply, though such systems still require privacy protections. Accordingly, we present a novel differential privacy framework for protecting trajectories generated by symbolic systems. These trajectories can be represented as words or strings over a finite alphabet. We develop new differential privacy mechanisms that approximate a sensitive word using a random word that is likely to be near it. An offline mechanism is implemented efficiently using a Modified Hamming Distance Automaton to generate whole privatized output words over a finite time horizon. Then, an online mechanism is implemented by taking in a sensitive symbol and generating a randomized output symbol at each timestep. This work is extended to Markov chains to generate differentially private state sequences that a given Markov chain could have produced. Statistical accuracy bounds are developed to quantify the accuracy of these mechanisms, and numerical results validate the accuracy of these techniques for strings of English words.

Full work available at URL: https://arxiv.org/abs/2202.03325

zbMATH Keywords

Markov chainsdifferential privacysymbolic systems

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Data structures (68P05)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Differential Privacy: A Survey of Results
• Title not available (Why is that?)
• Differentially Private Filtering
• Current-State Opacity Formulations in Probabilistic Finite Automata
• Jamming Attacks on Remote State Estimation in Cyber-Physical Systems: A Game-Theoretic Approach
• The algorithmic foundations of differential privacy
• Privately solving linear programs
• A Better Bound on the Variance
• Fast string correction with Levenshtein automata
• Differentially Private Distributed Constrained Optimization
• Differentially Private Distributed Convex Optimization via Functional Perturbation
• On Approximate Opacity of Cyber-Physical Systems
• Design of Privacy-Preserving Dynamic Controllers
• Differentially Private MIMO Filtering for Event Streams
• Differential Privacy in Linear Distributed Control Systems: Entropy Minimizing Mechanisms and Performance Tradeoffs
• Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraints

Cited In (3)

• A survey on privacy-preserving control and filtering of networked control systems
• Verifying Pufferfish privacy in hidden Markov models
• Coupled relational symbolic execution for differential privacy

This page was built for publication: Differential privacy for symbolic systems with application to Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6160739)