@inproceedings{2badf2a084ae4d5d9c0e7fb2f0e6890f,
title = "Deciding Differential Privacy of Online Algorithms with Multiple Variables",
abstract = "We consider the problem of checking the differential privacy of online randomized algorithms that process a stream of inputs and produce outputs corresponding to each input. This paper generalizes an automaton model called DiP automata [10] to describe such algorithms by allowing multiple real-valued storage variables. A DiP automaton is a parametric automaton whose behavior depends on the privacy budget ϵ. An automaton A will be said to be differentially private if, for some D, the automaton is Dϵ-differentially private for all values of ϵ > 0. We identify a precise characterization of the class of all differentially private DiP automata. We show that the problem of determining if a given DiP automaton belongs to this class is PSPACE-complete. Our PSPACE algorithm also computes a value for D when the given automaton is differentially private. The algorithm has been implemented, and experiments demonstrating its effectiveness are presented.",
keywords = "Automata, Decision procedure, Differential Privacy, Verification",
author = "Rohit Chadha and {Prasad Sistla}, A. and Mahesh Viswanathan and Bishnu Bhusal",
note = "Publisher Copyright: {\textcopyright} 2023 Copyright held by the owner/author(s).; 30th ACM SIGSAC Conference on Computer and Communications Security, CCS 2023 ; Conference date: 26-11-2023 Through 30-11-2023",
year = "2023",
month = nov,
day = "15",
doi = "10.1145/3576915.3623170",
language = "English (US)",
series = "CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security",
publisher = "Association for Computing Machinery",
pages = "1761--1775",
booktitle = "CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security",
address = "United States",
}