On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy

DOI10.1007/978-3-030-77883-5_16zbMath1477.68101OpenAlexW3165905670MaRDI QIDQ2056803

Rasmus Pagh, Ameya Velingker, Badih Ghazi, Ravi Kumar, Noah Golowich

Publication date: 8 December 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-77883-5_16

zbMATH Keywords

secure multi-party computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Privacy of data (68P27)

Related Items (2)

A theory of composition for differential obliviousness ⋮ Private aggregation from fewer anonymous messages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selection and sorting with limited storage
• Finding repeated elements
• Decomposable searching problems
• Optimal tracking of distributed heavy hitters and quantiles
• Distributed differential privacy via shuffling
• The privacy blanket of the shuffle model
• Binomial Approximation to the Poisson Binomial Distribution: The Krawtchouk Expansion
• Pure Differential Privacy for Rectangle Queries via Private Partitions
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Concentration Inequalities
• Distributed Private Heavy Hitters
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Differential privacy under continual observation
• Optimal Lower Bound for Differentially Private Multi-party Aggregation
• Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
• Local, Private, Efficient Protocols for Succinct Histograms
• The Algorithmic Foundations of Differential Privacy
• Fast, small-space algorithms for approximate histogram maintenance
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• An improved data stream summary: the count-min sketch and its applications
• Minimax Optimal Procedures for Locally Private Estimation
• Heavy Hitters and the Structure of Local Privacy
• The Complexity of Differential Privacy
• The power of factorization mechanisms in local and central differential privacy
• Locally Private k-Means Clustering
• Analysis of Boolean Functions
• Differential privacy and robust statistics
• On the complexity of differentially private data release
• Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
• A Statistical Framework for Differential Privacy
• Optimal private halfspace counting via discrepancy
• Privacy-preserving statistical estimation with optimal convergence rates
• Fast Private Norm Estimation and Heavy Hitters
• Secure Multiparty Computation and Secret Sharing
• Theory of Cryptography
• Differential Privacy
• Separating Local & Shuffled Differential Privacy via Histograms

This page was built for publication: On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy