We introduce an automata model for describing interesting classes of differential privacy mechanisms/algorithms that include known mechanisms from the literature. These automata can model algorithms whose inputs can be an unbounded sequence of real-valued query answers. We consider the problem of checking whether there exists a constant $d$ such that the algorithm described by these automata are $d\epsilon$-differentially private for all positive values of the privacy budget parameter $\epsilon$. We show that this problem can be decided in time linear in the automaton's size by identifying a necessary and sufficient condition on the underlying graph of the automaton. This paper's results are the first decidability results known for algorithms with an unbounded number of query answers taking values from the set of reals.
翻译:我们引入了一种自动模型, 描述不同隐私机制/ 不同隐私机制/ 单数的有趣类别, 其中包括文献中已知的机制。 这些自动模型可以模拟算法, 其输入可以是无限制的真值查询解答序列。 我们考虑的问题是, 是否存在一个恒定美元, 使得这些自动模型描述的算法对于隐私预算参数的所有正值 $\ epsilon$- displon- differentive financial 。 我们显示, 这个问题可以通过在自动图的底图上确定一个必要和充分的条件, 来在自动图的大小中以时间线性来决定 。 本文的结果是第一个已知的解算结果, 这些算法中包含一系列无限制的查询解答, 从真实值中找到数值 。