Differential privacy for symbolic systems with application to Markov chains

DOI10.1016/J.AUTOMATICA.2023.110908MaRDI QIDQ6160739zbMATH OpenFDO

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

Publication date 26 June 2023

Published in Automatica (Search for Journal in Brave)

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)

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.

Cites work

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

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)