一句话：提出自动机模型，并证明无界实数查询答案输入程序的差分隐私可在线性时间内判定。
本文针对具有无界输入的差分隐私程序，提出一种自动机模型，用以描述包括文献中已知机制在内的一类差分隐私机制/算法。该模型可处理输入为无界实数查询答案序列的算法。作者研究判定问题：是否存在常数 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.
@inproceedings{paperbot6184,
title = {On Linear Time Decidability of Differential Privacy for Programs with Unbounded Inputs},
author = {Rohit Chadha and A. Prasad Sistla and Mahesh Viswanathan},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470708}
}