Towards Differential Privacy for Symbolic Systems
This work addresses privacy concerns for symbolic systems, such as in control or language processing, but is incremental as it adapts existing differential privacy methods to a new domain.
The paper tackled the problem of applying differential privacy to symbolic control systems, which generate non-numerical sequences, by developing an exponential mechanism based on Levenshtein distance and implementing it with a Levenshtein automaton, demonstrating privacy with reasonable accuracy in tests on English words and deterministic transition systems.
In this paper, we develop a privacy implementation for symbolic control systems. Such systems generate sequences of non-numerical data, and these sequences can be represented by words or strings over a finite alphabet. This work uses the framework of differential privacy, which is a statistical notion of privacy that makes it unlikely that privatized data will reveal anything meaningful about underlying sensitive data. To bring differential privacy to symbolic control systems, we develop an exponential mechanism that approximates a sensitive word using a randomly chosen word that is likely to be near it. The notion of "near" is given by the Levenshtein distance, which counts the number of operations required to change one string into another. We then develop a Levenshtein automaton implementation of our exponential mechanism that efficiently generates privatized output words. This automaton has letters as its states, and this work develops transition probabilities among these states that give overall output words obeying the distribution required by the exponential mechanism. Numerical results are provided to demonstrate this technique for both strings of English words and runs of a deterministic transition system, demonstrating in both cases that privacy can be provided in this setting while maintaining a reasonable degree of accuracy.