Publication

DAMS: Meta-estimation of private sketch data structures for differentially private COVID-19 contact tracing

DAMS: Differentially Private Sketching Data Structures

DAMS: Meta-estimation of private sketch data structures for differentially private COVID-19 contact tracing, Praneeth Vepakomma, Subha Nawer Pushpita and Ramesh Raskar, PPML (Privacy Preserving Machine Learning workshop) at NeurIPS

Abstract

We propose an improved private count-mean-sketch data structure and show its applicability to differentially private contact tracing. Our proposed scheme (Diversified Averaging for Meta estimation of Sketches-DAMS) provides a better trade-off between true positive rates and false positive rates while maintaining differential privacy (a widely accepted formal standard for privacy). We show its relevance to the social good application of private digital contact tracing for COVID-19 and beyond. The scheme involves one way locally differentially private uploads from the infected client devices to a server that upon a post-processing obtains a private aggregated histogram of locations traversed by all the infected clients within a time period of interest. The private aggregated histogram is then downloaded by any querying client in order to compare it with its own data on-device, to determine whether it has come into close proximity of any infected client or not. We present empirical experiments that show a substantial improvement in performance for this particular application. We also prove theoretical variance-reduction guarantees of the estimates obtained through our scheme and verify these findings via experiments as well.

Related Content