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

Computer Science > Cryptography and Security [Submitted on 30 Mar 2026] Differential Privacy for Symbolic Trajectories via the Permute-and-Flip Mechanism Alexander Benvenuti, Huaiyuan Rao, Matthew Hale 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. Comments: 9 Pages, 5 Figures Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2603.28903 [cs.CR]   (or arXiv:2603.28903v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2603.28903 Focus to learn more Submission history From: Alexander Benvenuti [view email] [v1] Mon, 30 Mar 2026 18:30:06 UTC (338 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-03 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)