Mon 19 Jun 2023 18:37 - 18:45 at Cypress 1 - SRC: Poster Session

Differential privacy is the gold standard for privacy-preserving analysis and also a popular target for the formal verification because of its composition properties. Many tools have been developed that can automatically verify approximate differentially private algorithms, but none of the current state-of-the-art tools give a tight bound on privacy costs for approximate differentially private algorithms. Through this work, we present the theoretical background for a tool that can verify algorithms that use Gaussian noise to be approximate differentially private and provide tight bound on privacy costs. Our approach is to transform a differentially private algorithm into a verifiable version of the algorithm that can be verified using top-of-the-shelf verifiers. Verifiable versions have privacy cost explicit, which can be converted to a curve of possible values of parameters of privacy cost- epsilon, delta. Using the user’s provided budget of values of epsilon, delta we can verify the algorithm to be approximate differentially private. We applied the technique from “optimal accounting of differential privacy via the characteristic function”. We used the characteristic function to characterize privacy loss, which is a lossless representation, which means that, unlike moment-generating functions, characteristic functions always exist. Logarithms of these characteristic functions also compose linearly, which makes privacy tracking easier. The characteristic function is based on dominating pairs - a generalization of worst-case pairs of distributions bounding privacy loss for neighboring datasets. Just like characteristic functions, dominating pairs always exist and compose easily over adaptive mechanisms. In the transformed program, We make privacy cost explicitly by tracking the logarithms of characteristic functions which compose linearly and converting it to epsilon, delta differential privacy. In this work, we extend the simple imperative language introduced in lightDP and shadowDP and also introduce a novel type system. We proved the dominating pair distributions for a simple Gaussian command and the composition of two commands. We used these results to prove the pointwise soundness of the novel type system using proof by structural induction. We also prove the soundness of the type system and explain how our tool can be used to ensure privacy. Our tool is the first one to formally verify approximate differentially private algorithms like the Gaussian mechanism with a tight bound.

Mon 19 Jun

Displayed time zone: Eastern Time (US & Canada) change

18:00 - 19:30
SRC: Poster SessionSRC at Cypress 1
18:00
7m
Poster
An Eager SMT Solver for Algebraic Data Type Queries
SRC
File Attached
18:07
7m
Poster
A Synchronization Mechanism for an Accelerator Design IR
SRC
Pai Li Cornell University, USA
Media Attached
18:15
7m
Poster
ConstraintFlow: A Declarative DSL for Certified Artificial Intelligence
SRC
Media Attached
18:22
7m
Poster
Distributions for Compositionally Differentiating Parametric Discontinuities
SRC
Jesse Michel Massachusetts Institute of Technology
Media Attached
18:30
7m
Poster
Formal Verification of a MIR-to-MIR optimisation
SRC
Media Attached
18:37
7m
Poster
Formal verification of approximate differential privacy via the characteristic function
SRC
Media Attached
18:45
7m
Poster
Leveraging Far Memory for Data-Intensive Processing: A Hotness-Segregated Heap Approach
SRC
Dat Nguyen Texas A & M University
File Attached
18:52
7m
Poster
On lightweight Hoare logic of probabilistic programs: a bound tighter than the union bound
SRC
Xingyu Xie Tsinghua University
Media Attached
19:00
7m
Poster
Prettybird: A DSL for Programmatic Font Compilation
SRC
Charles Averill University of Texas at Dallas
Media Attached
19:07
7m
Poster
Quantum Simulation using Context-Free-Language Ordered Binary Decision Diagrams
SRC
Media Attached
19:15
7m
Poster
Resource Sharing through Control-Flow Based Optimizations
SRC
Media Attached
19:22
7m
Poster
Scaling Decision-Theoretic Probabilistic Programs Through Factorization
SRC
Minsung Cho Northeastern University
Media Attached