On Linear Time Decidability of Differential Privacy for Programs with Unbounded Inputs
On Linear Time Decidability of Differential Privacy for Programs with Unbounded Inputs
复制标题
DOI：
10.1109/lics52264.2021.9470708
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Rohit Chadha;A. Sistla;Mahesh Viswanathan
中科院分区：
文献类型：
--
作者：
Rohit Chadha;A. Sistla;Mahesh Viswanathan
我们介绍了一个自动机模型，以描述包括文献中的已知机制的差异隐私机制/算法的有趣类别。存在一个常数d，以至于这些自动机描述的算法是d的，对于隐私预算参数的所有正值ϵ ϵ的所有正值。我们表明，可以在自动机的大小中及时确定此问题，通过在自动机的基础图上识别必要的足够条件，这是本文的结果是算法的第一个决策结果。从真实的集合。
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ϵ-differentially private for all positive values of the privacy budget parameter ϵ. 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.