2021/04/29 by Rohit Chadha, A. Prasad Sistla, Chadha, Rohit +3 · 1 citation
Computer Science · Social Sciences · #Access Control and Trust #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Privacy-Preserving Technologies in Data #Programming Languages (cs.PL)
paper · pdf · doi:10.48550/arxiv.2104.14519
openalex publication_date 2021/04/29 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We introduce an automata model for describing interesting classes of\ndifferential privacy mechanisms/algorithms that include known mechanisms from\nthe literature. These automata can model algorithms whose inputs can be an\nunbounded sequence of real-valued query answers. We consider the problem of\nchecking whether there exists a constant d such that the algorithm described\nby these automata are d\ε-differentially private for all positive\nvalues of the privacy budget parameter \ε. We show that this problem\ncan be decided in time linear in the automaton's size by identifying a\nnecessary and sufficient condition on the underlying graph of the automaton.\nThis paper's results are the first decidability results known for algorithms\nwith an unbounded number of query answers taking values from the set of reals.\n