2020/07/24 by Mark Bun, Jörg Drechsler, Bun, Mark +7
Computer Science · Medicine · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #HIV, Drug Use, Sexual Risk #HIV/AIDS Research and Interventions #Machine Learning (cs.LG) #Methodology (stat.ME) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2007.12674
openalex publication_date 2020/07/24 · openalex created_date 2023/06/24 · openalex updated_date 2026/07/28
Sampling schemes are fundamental tools in statistics, survey design, and algorithm design. A fundamental result in differential privacy is that a differentially private mechanism run on a simple random sample of a population provides stronger privacy guarantees than the same algorithm run on the entire population. However, in practice, sampling designs are often more complex than the simple, data-independent sampling schemes that are addressed in prior work. In this work, we extend the study of privacy amplification results to more complex, data-dependent sampling schemes. We find that not only do these sampling schemes often fail to amplify privacy, they can actually result in privacy degradation. We analyze the privacy implications of the pervasive cluster sampling and stratified sampling paradigms, as well as provide some insight into the study of more general sampling designs.