# Lightweight Techniques for Private Heavy Hitters

arXiv: https://arxiv.org/abs/2012.14884 · HTML: https://mlsanity.com/paper/2012.14884/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2020.

## Built on by (most cited first, 13 of 13)

- [RoFL: Robustness of Secure Federated Learning](https://mlsanity.com/paper/2107.03311/) (2021)
- [Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning](https://mlsanity.com/paper/2308.09883/) (2023)
- [SecGNN: Privacy-Preserving Graph Neural Network Training and Inference as a Cloud Service](https://mlsanity.com/paper/2202.07835/) (2022)
- [Federated Analytics: A survey](https://mlsanity.com/paper/2302.01326/) (2023)
- [Samplable Anonymous Aggregation for Private Federated Data Analysis](https://mlsanity.com/paper/2307.15017/) (2023)
- [Masked LARk: Masked Learning, Aggregation and Reporting worKflow](https://mlsanity.com/paper/2110.14794/) (2021)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [PAPAYA Federated Analytics Stack: Engineering Privacy, Scalability and Practicality](https://mlsanity.com/paper/2412.02340/) (2024)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Practical and Light-weight Secure Aggregation for Federated Submodel Learning](https://mlsanity.com/paper/2111.01432/) (2021)
- [Fluent: Round-efficient Secure Aggregation for Private Federated Learning](https://mlsanity.com/paper/2403.06143/) (2024)
- [DP-Hype: Federated Differentially Private Hyperparameter Search](https://mlsanity.com/paper/2510.04902/) (2025)
- [Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy](https://mlsanity.com/paper/2607.27815/) (2026)

## Abstract (arXiv)

This paper presents Poplar, a new system for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client's string. A web-browser vendor, for instance, can use Poplar to figure out which homepages are popular, without learning any user's homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients. Poplar uses two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Poplar protects client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.