Synthesizing Tight Privacy and Accuracy Bounds via Weighted Model Counting

arXiv:2402.16982v1 Announce Type: new
Abstract: Programmatically generating tight differential privacy (DP) bounds is a hard problem. Two core challenges are (1) finding expressive, compact, and efficient encodings of the distributions of DP algorithms, and (2) state space explosion stemming from the multiple quantifiers and relational properties of the DP definition.
We address the first challenge by developing a method for tight privacy and accuracy bound synthesis using weighted model counting on binary decision diagrams, a state of the art technique …

accuracy algorithms arxiv challenges cs.cr cs.pl definition differential privacy distributions explosion hard privacy problem space state