Differential Privacy for Symbolic Trajectories via the Permute-and-Flip Mechanism

• URL: http://arxiv.org/abs/2603.28903v1
• Date: Mon, 30 Mar 2026 18:30:06 GMT
• Title: Differential Privacy for Symbolic Trajectories via the Permute-and-Flip Mechanism
• Abstract summary: We develop a new mechanism for privatizing state trajectories of symbolic systems that may be represented as words over a finite alphabet.<n>The accuracy of our mechanism is never worse than the prior state of the art, and we empirically show on a real traffic dataset that it introduces up to $55%$ less error.
• Score: 42.73108425701334
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Privacy techniques have been developed for data-driven systems, but systems with non-numeric data cannot use typical noise-adding techniques. Therefore, we develop a new mechanism for privatizing state trajectories of symbolic systems that may be represented as words over a finite alphabet. Such systems include Markov chains, Markov decision processes, and finite-state automata, and we protect their symbolic trajectories with differential privacy. The mechanism we develop randomly selects a private approximation to be released in place of the original sensitive word, with a bias towards low-error private words. This work is based on the permute-and-flip mechanism for differential privacy, which can be applied to non-numeric data. However, a naïve implementation would have to enumerate an exponentially large list of words to generate a private word. As a result, we develop a new mechanism that generates private words without ever needing to enumerate such a list. We prove that the accuracy of our mechanism is never worse than the prior state of the art, and we empirically show on a real traffic dataset that it introduces up to $55\%$ less error than the prior state of the art under a conventional privacy implementation.

Related papers

• Phantoms and Disclosures: a Causal Framework for Auditing Synthetic Data [56.86147283213652]
  We present a customizable empirical auditing framework designed to detect and explain data disclosures.<n>Our framework introduces a mechanism to distinguish between "true disclosures"-where the system directly reproduces a user's information-and "phantom disclosures"-where the system incidentally generates a user's data.
  arXiv  Detail & Related papers  (2026-06-15T16:54:02Z)
• Differentially Private Random Feature Model [47.35176457481132]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Private prediction for large-scale synthetic text generation [28.488459921169905]
  We present an approach for generating differentially private synthetic text using large language models (LLMs) In the private prediction framework, we only require the output synthetic data to satisfy differential privacy guarantees.
  arXiv  Detail & Related papers  (2024-07-16T18:28:40Z)
• Privacy-Aware Randomized Quantization via Linear Programming [13.002534825666219]
  We propose a family of quantization mechanisms that is unbiased and differentially private. Our proposed mechanism can attain a better privacy-accuracy trade-off compared to baselines.
  arXiv  Detail & Related papers  (2024-06-01T18:40:08Z)
• Adaptive Privacy Composition for Accuracy-first Mechanisms [55.53725113597539]
  Noise reduction mechanisms produce increasingly accurate answers. Analysts only pay the privacy cost of the least noisy or most accurate answer released. There has yet to be any study on how ex-post private mechanisms compose. We develop privacy filters that allow an analyst to adaptively switch between differentially private and ex-post private mechanisms.
  arXiv  Detail & Related papers  (2023-06-24T00:33:34Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Uncertainty-Autoencoder-Based Privacy and Utility Preserving Data Type Conscious Transformation [3.7315964084413173]
  We propose an adversarial learning framework that deals with the privacy-utility tradeoff problem under two conditions. Under data-type ignorant conditions, the privacy mechanism provides a one-hot encoding of categorical features, representing exactly one class. Under data-type aware conditions, the categorical variables are represented by a collection of scores, one for each class.
  arXiv  Detail & Related papers  (2022-05-04T08:40:15Z)
• On a Utilitarian Approach to Privacy Preserving Text Generation [5.123298347655088]
  We propose a class of differentially private mechanisms that parameterizes the nearest neighbor selection criterion in traditional mechanisms. Motivated by Vickrey auction, where only the second highest price is revealed and the highest price is kept private, we balance the choice between the first and the second nearest neighbors. Experiments on real text classification datasets show up to 50% improvement in utility compared to the existing state-of-the-art with the same empirical privacy guarantee.
  arXiv  Detail & Related papers  (2021-04-23T23:13:43Z)
• N-grams Bayesian Differential Privacy [1.3443690690260939]
  We propose a differential privacy mechanism that uses public data as a prior in a Bayesian setup to provide tighter bounds on the privacy loss metric epsilon. It achieves up to 85% reduction in KL divergence compared to previously known mechanisms at epsilon equals 0.1. We compare our mechanism to k-anonymity in a n-gram language modelling task and show that it offers competitive performance at large vocabulary sizes.
  arXiv  Detail & Related papers  (2021-01-29T18:48:49Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.