Deciding Accuracy of Differential Privacy Schemes
summary
Introduces accuracy as a parametric notion based on distance to disagreement (dd) and output closeness γ, yielding an explicit alpha–beta–gamma claim: e.g. for sparse vector technique beta = 2n · e^{−αε/8} when γ=0. Shows accuracy verification is undecidable in general but decidable for the diffile+ class assuming Schanuel’s conjecture and unconditionally decidable for finite-domain programs. Implements a verifier DipC+ tool that checks αβγ accuracy at inputs, verifies several mechanisms and in some cases halves the known error bound.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:17PRIVACY IN DATABASES
- 2:37WHAT IS ACCURACY FOR DP MECHANISMS?
- 4:37SPARSEVECTOR TECHNIQUE (SVT)
- 6:05LAPLACE DISTRIBUTION
- 6:44ACCURACY OF SVT
- 8:05TOWARDS A UNIFORM DEFINITION OF
- 10:50ACCURACY FOR SVT USING OUR PROPOSED DEFINITION
- 13:14THE SETUP OF THE VERIFICATION PROBLEMS
- 15:35CHALLENGES
- 19:18PROOF SKETCH
- 20:47A UNCONDITIONAL DECIDABILITY RESULT
- 24:45EXPERIMENTAL EVALUATION
- 26:03EXPERIMENTAL RESULTS
- 26:59CONTRIBUTIONS
related talks
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
01h 00mDifferential Privacy: Fundamentals to Forefront I
26mAlgorithms with More Granular Differential Privacy Guarantees
42mDifferential Privacy
01h 14mTutorial: Privacy, Part II
50mPrivacy Amplification by Sampling and Renyi Differential Privacy
01h 03mStatistical Inference and Privacy, Part II
01h 02mFormal Methods and Proofs of Privacy Properties, Part III