Anonymized Histograms in Intermediate Privacy Models
We study the problem of privately computing the anonymized histogram (a.k.a. unattributed histogram), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$- and $\ell_2^2$-errors of $O_\varepsilon(\sqrt{n})$ in the central model of differential privacy (DP). In this work, we provide an algorithm with a nearly matching error guarantee of $\tilde{O}_\varepsilon(\sqrt{n})$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Differentially private anonymized histograms
For a dataset of label-count pairs, an anonymized histogram is the multiset of counts. Anonymized histograms appear in various potentially sensitive contexts such as password-frequency lists, degree distribution in socia…
TIPRDC: Task-Independent Privacy-Respecting Data Crowdsourcing Framework for Deep Learning with Anonymized Intermediate Representations
The success of deep learning partially benefits from the availability of various large-scale datasets. These datasets are often crowdsourced from individual users and contain private information like gender, age, etc. Th…
Speaker Anonymization with Phonetic Intermediate Representations
In this work, we propose a speaker anonymization pipeline that leverages high quality automatic speech recognition and synthesis systems to generate speech conditioned on phonetic transcriptions and anonymized speaker em…
Automatic Speech RecognitionAutomatic Speech Recognition (ASR)Speaker anonymizationspeech-recognition+2Where You Are Is Who You Are: User Identification by Matching Statistics
Most users of online services have unique behavioral or usage patterns. These behavioral patterns can be exploited to identify and track users by using only the observed patterns in the behavior. We study the task of ide…
User IdentificationPre-capture Privacy via Adaptive Single-Pixel Imaging
As cameras become ubiquitous in our living environment, invasion of privacy is becoming a growing concern. A common approach to privacy preservation is to remove personally identifiable information from a captured image,…