Lightweight Techniques for Private Heavy Hitters

Dan Boneh; Elette Boyle; Henry Corrigan-Gibbs; Niv Gilboa; Yuval Ishai

Source-linked AI summary

Lightweight Techniques for Private Heavy Hitters

Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai

arXiv:2012.14884v5Dec 29, 2020cs.CR

TL;DR

Poplar tackles private heavy hitters and subset histograms, allowing servers to identify popular strings or count selected strings without exposing individual client inputs. It uses lightweight two-server cryptography, including malicious-secure and incremental or extractable distributed point functions, to provide efficient one-message protocols. The system is evaluated as concretely efficient, while its main limitations are quantified leakage and dependence on two non-colluding servers.

Problem
Poplar addresses private heavy hitters and subset histograms, where servers need popular-string sets or selected-string counts without learning individual client strings.
Method
Poplar combines two-server private aggregation with malicious-secure protocols, extractable distributed point functions, and incremental distributed point functions for succinct one-message client uploads.
Results
Poplar is concretely efficient, outperforms existing secure-aggregation approaches, and supplies malicious-secure protocols and cryptographic tools for private heavy hitters and subset histograms.
Takeaways & Limitations
The techniques support practical private data collection while preserving client privacy against arbitrary deviation by one server and malicious clients within the stated guarantees.
Takeaways & Limitations
Poplar reveals modest quantified leakage about honest-client string distributions and does not guarantee correctness against a malicious server; it also requires two non-colluding servers.

Abstract

from arXiv · show

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.

1 Introduction

Poplar addresses private heavy hitters and subset histograms with lightweight two-server cryptography, aiming to preserve client privacy while efficiently identifying popular strings. Its main techniques provide malicious security, reduce communication from quadratic to linear in string length, and achieve concrete performance, while introducing quantified leakage and requiring two non-colluding servers.

System overview: Poplar solves private heavy hitters with two non-colluding servers, one client message, no public-key operations beyond secure channels, and protection against one malicious server.Correctness is protected against malicious clients, while privacy holds if at least one server is honest.
Our techniques: A malicious-secure checking protocol protects correctness against malicious clients and privacy against a malicious server without extra servers, general-purpose MPC, or additional client-server rounds.The work also develops private subset-histogram protocols and evaluates these techniques in Poplar.
Our techniques: Extractable distributed point functions address double-voting attacks by enabling extraction of an honest strategy from a malicious client’s behavior, under a random-oracle PRG model.Prior protocols could miss a client voting tentatively for multiple strings when fewer than two voted strings intersect the queried set.
Our techniques: Incremental distributed point functions reduce client-to-server communication from quadratic to linear in the string length n by secret-sharing weights along a single non-zero tree path.The straightforward approach requires Ω(n^2) bits per client because it runs n subset-histogram instances, each using an Ω(n)-size key.
Limitations: Poplar leaks modest, precisely quantified information about the distribution of client-held strings beyond the heavy hitters and requires two non-colluding servers.The leakage depends only on the honest clients’ multiset, not client-string associations; scalability to k servers tolerating k−1 malicious servers is inefficient.

2 Problem statement

The paper formalizes private subset histograms and heavy hitters as private aggregate-statistic tasks over client-held strings, with restricted communication and explicit security goals. Poplar protects privacy and malicious-client robustness, but its efficient heavy-hitters protocols permit quantified leakage and do not guarantee correctness against malicious servers.

Tasks: Private heavy hitters requires finding every string appearing more than t times, despite the absence of an a priori candidate set in a potentially enormous universe.The corresponding subset-histogram task counts clients holding each string in a server-held set S.
Communication pattern: Clients upload one message to each server, after which the servers interact to output the aggregate statistic without further client communication.An optional setup phase can distribute public parameters, and one encrypted message may be routed through Server 0.
Security properties: Privacy against one malicious server requires learning no client data beyond the aggregate, even when that server colludes with malicious clients.Completeness and robustness require honest execution to produce the aggregate and malicious clients to influence it only through chosen inputs.
Security properties: The subset-histogram protocol reveals only the subset histogram of participating honest clients, while a malicious server may independently disqualify honest clients.Disqualification can occur by pretending not to receive a client’s message.
Security properties: Efficient heavy-hitters protocols reveal a small, symmetric leakage about the honest-client multiset beyond the heavy hitters, with output length comparable to the aggregate and logarithmic in client count at fixed threshold fraction.The leakage reveals no client-string association and typically exposes less than shuffling, including fewer rare inputs.
Security properties: Poplar does not guarantee that an honest server recovers the correct aggregate when the other server maliciously deviates, leaving malicious-server correctness as future work.The paper prioritizes privacy because the participating organizations may benefit from private data but not from corrupting the output.

3 Background

The background introduces private aggregation through distributed point functions, which compactly secret-share one-hot vectors for subset histograms. These primitives support exact private counts against one malicious server, but motivate extensions for malicious clients and heavy hitters.

Distributed point functions: Distributed point functions compactly secret-share a 2^n-dimensional vector with one non-zero element, using O(n)-size shares instead of a naïve 2^n-size representation.Gen creates shares for a point and value, while Eval recovers a share of the vector at an index.
Distributed point functions: The basic DPF protocol privately computes queried counts because either single key reveals no information about the client’s special point or value.The security property protects the special point and value when an adversary learns only one of the two keys.
Private subset histograms: In the basic subset-histogram protocol, each client sends two DPF keys encoding a one-hot vector at its private string, and servers evaluate keys at queried strings.Summing the two server values for a queried string yields the number of clients holding it.
Extensions: These basic techniques are extended later to defend against malicious-client corruption, compute heavy hitters, and provide user-level differential privacy.The paper evaluates the efficiency of the heavy-hitters protocol after presenting these extensions.
Private subset histograms: The background protocol assumes two servers and lets them output exact counts for each server-held string in the subset-histogram set.The field is chosen with size greater than the number of clients so the aggregate counts are represented correctly.

4 Privacy-preserving subset histograms via malicious-secure sketching

This section strengthens private subset histograms against malicious clients and servers by combining malicious-secure sketching with extractable DPFs. The resulting protocol preserves privacy against a malicious server while preventing clients from corrupting the recovered histogram through invalid or multiple votes.

4.1 Prior work: Sketching for malicious clients: A malicious client can otherwise corrupt the histogram arbitrarily, but Poplar modifies the scheme to protect against client corruption attacks.Malformed DPF keys can produce pseudorandom output or manipulate the recovered statistics.
4.2 New tool: Malicious-secure sketching: The servers check secret-shared vectors for weight one using a lightweight protocol secure against malicious behavior by either server, without extra client interaction or servers.The checked vector is zero everywhere except for a single non-zero entry.
4.2 New tool: Malicious-secure sketching: Authenticated randomized encodings let honest servers reject vectors tampered with by a malicious server while retaining protection against malicious clients.The client encodes v together with a random scalar multiple κv and secret-shares both components.
4.3 New tool: Extractable DPFs: Extractable DPFs prevent a malicious client from controlling non-zero outputs at multiple known locations, enabling the servers to identify the unique relevant vote.In the random-oracle model, malformed keys either behave validly at one location or produce random output elsewhere, while two controlled locations are infeasible.
4.4 Putting it together: Combining malicious-secure sketching with extractable DPFs yields private subset histograms with server-privacy and client-correctness guarantees.The same combination may also apply to other DPF applications evaluated on a strict subset of the input domain.

5 Private heavy hitters

Poplar finds private heavy hitters by repeatedly querying counts for candidate prefixes and pruning prefixes below the threshold. Incremental DPFs make these prefix-count queries lightweight while preserving privacy against one malicious server, though the protocol leaks prefix-count information.

Heavy hitters via prefix-count queries: Poplar recovers t-heavy hitters by breadth-first-searching the prefix tree and pruning every prefix whose count is below t.At each level, surviving prefixes are extended with 0 and 1; surviving length-n strings are the heavy hitters.
Heavy hitters via prefix-count queries: At most n·C/t prefix-count queries are needed, so searching for strings held by a constant fraction of clients uses a number of queries independent of C.The bound follows because each level contains at most C/t heavy prefixes.
Implementing private prefix-count queries via incremental DPFs: Incremental DPFs reduce client computation and communication for n-bit strings from quadratic to linear in n while also improving server-side performance.For applications with n≈256, the resulting factor-of-n improvement is substantial.
Implementing private prefix-count queries via incremental DPFs: The client sends one incremental DPF key, while server-to-server communication is proportional to the prefix-query count, at most n·C/t field elements.The protocol therefore avoids enumerating the entire string universe when computing heavy hitters.
Implementing private prefix-count queries via incremental DPFs: The protocol reveals more than the final heavy hitters: it exposes all heavy prefixes and their client counts, although differential privacy can mitigate this leakage.Against a malicious server, additive attacks can also influence which strings appear heavy, while formal analysis bounds the extra leakage.

6 Constructing Incremental DPFs

The paper constructs incremental DPFs by extending a standard DPF’s evaluation with prefix outputs while preserving pseudorandomness. The optimized construction achieves linear key size and evaluation cost in the input length, with only small per-level overhead.

Construction: Compared with using a state-of-the-art DPF as a black box, the direct incremental construction is designed to make all-prefix key size and evaluation linear rather than quadratic in n.Table 6 compares the two alternatives under fixed PRG and group-size parameters.
Construction: The incremental DPF construction achieves key size and generation/evaluation costs that grow linearly with the input bit length n.This directly avoids the quadratic costs of generating independent DPF keys for every prefix length.
Construction: The construction extends standard DPF evaluation by deriving each level’s output-group share alongside a fresh seed for subsequent evaluation.This preserves the pseudorandomness needed for security while supporting desired prefix outputs.
Construction: The optimized procedure adds one PRG evaluation and one group operation per level, plus correction-word material for converting pseudorandom values into target outputs.The correction mechanism supports arbitrary output groups by replacing XOR with addition of inverses where necessary.

7 Providing differential privacy

Poplar’s heavy-hitter output can reveal sensitive information when repeated runs are compared. The paper proposes adding differential privacy to limit the information inferred from these outputs.

Providing differential privacy: Repeated heavy-hitter runs can reveal whether an individual client contributed a particular string when that client goes offline.The example uses nytimes.com appearing before but not after one client leaves the population.
Providing differential privacy: A simple tweak to Poplar’s heavy-hitters protocol can make its output satisfy ε-differential privacy.The paper describes this modification in Appendix E.

8 Implementation and evaluation

Poplar’s implementation is compact and evaluated across client costs, server communication, and end-to-end execution. The evaluation finds low client overhead, substantially lower communication cost than standard-DPF baselines, and scalable parallel execution.

Client costs: Poplar’s client-side costs grow linearly with string length and remain relatively small compared with standard-DPF and count-min-sketch approaches.Incremental DPFs avoid the quadratic cost of using one standard-DPF key per tree layer, while count-min sketches have a larger linear constant.
Server communication: Poplar’s server communication costs are roughly two orders of magnitude less expensive than the standard-DPF baseline.The comparison uses clients sampling from a Zipf distribution and measures both communication and estimated dollar cost.
End-to-end performance: With 20 physical machines per logical server, Poplar is estimated to process ten million client requests in just over one hour.The workload is described as almost completely parallelizable, and Figure 10 neglects sharding costs.

9 Conclusions

The paper concludes that Poplar enables two non-colluding servers to recover popular client-held strings while preserving client privacy. It also identifies broader cryptographic tools and extensions, while formalizing the protocol setting and its bare-bones privacy assumptions.

9 Conclusions: Poplar lets two non-colluding servers compute the most popular client-held strings while preserving client privacy.The system’s cryptographic toolkit includes unit-vector checking, extractable DPFs, and tree-based secret sharing.
Functionalities: The protocols consider two servers, client inputs, malicious-client influence, and leakage to a malicious server through explicit functionalities.The formal specification uses separate cases for honest parties, malicious clients, and malicious servers.
Scope and assumptions: The bare-bones protocols do not add differential-privacy noise, although a differentially private variant adds server-generated noise.The paper notes that this extra defense may be unnecessary when honest-client inputs have strong statistical entropy guarantees.
Scope and assumptions: Security against malicious clients is proved in the random-oracle model with honest inputs assumed independent of the oracle.The formal security parameter is common to all parties.
Functionalities: The heavy-hitters functionality outputs strings held by at least the server-chosen threshold number of clients.The formal functionality defines the output as the set of strings whose multiplicity reaches threshold t.

B Extension: Hashing for longer strings

The hashing extension shortens long client strings before heavy-hitters search, then stores enough information to recover the original strings. It reduces key size but is incompatible with the paper’s differential-privacy extension.

Hashing approach: The hashing-based optimization improves communication and round complexity when string length n is much larger than the security parameter λ.The approach begins by hashing long strings to 2λ-bit values and addressing the need to recover the original strings.
Hashing approach: Each client hashes its string, appends a random λ-bit nonce, and writes the original string as a payload at the resulting tree leaf.The extended tree has depth 3λ+1, with intermediate path values set to one and the final payload containing the client string.
Complexity: The resulting incremental DPF key is approximately 3λ^2 log_2 C + n bits.The construction uses fields of size approximately C through the hash levels and a larger field at the final payload level.
Server recovery: The servers first identify popular hash values, then search nonce subtrees and recover a string whose hash matches each popular value.Randomized depth-first search is retried when necessary to find a matching original string.
Limitations: The hashing-based technique is incompatible with the paper’s differential-privacy extensions, which instead work with an error-correcting-code variant.This is a stated scope boundary of the optimization.

C.3 Proof of Proposition 1

The incremental DPF proof argues that each party’s key remains pseudorandom as correction words are replaced level by level. The construction uses PRG-generated seeds and group conversion to preserve this indistinguishability across the tree.

Proof strategy: The security proof proceeds through hybrids that replace each level’s correction word with randomness while preserving the other party’s view.The proof advances from level to level, showing that the remaining seed continues to appear random.
Construction: The incremental DPF construction uses a pseudorandom generator and ConvertG′ to produce values in the extended group G′.The construction defines G′ as the product of λ-bit strings under bitwise addition and the output group G.
Proof strategy: Each party begins with a secret random seed, expands it with a PRG at every level, and uses correction words to consume selected pieces of that randomness.The correction-word construction leaves a remaining seed that appears random to the other party.
Protocol costs: The client sends amortized field-element shares and one DPF key to each server, after which the servers evaluate keys, exchange masked shares, and verify a zero sum.The described secure computation uses two server rounds and four field elements of communication per server.

C.4.1 Security analysis

The protocol adds checks to protect correctness against malicious clients while preserving privacy against malicious servers. Its verification rejects malformed client vectors with high probability, and a simulator establishes server privacy.

Malicious client: Client-provided correlated randomness and extra verification checks do not adversely affect the prior protocol’s guarantees against malicious clients.The analysis begins by isolating these additions before proving the malicious-client claim.
Malicious client: The verification check rejects any client vector that is not a valid single-entry binary vector except with probability 2/|F|.The proof uses polynomial identities and the Schwartz-Zippel lemma to enforce at most one nonzero entry, with each nonzero entry in {0,1}.
Malicious server: The protocol provides client privacy against every malicious server through a simulator whose output is indistinguishable from the server’s real view.The simulation handles masked inputs and distinguishes the cases where an adversary’s input offset is zero or nonzero.
Malicious server: Random secret masks force malicious input offsets to be independent of the honest client’s sensitive values.When the offset is nonzero, the resulting expression is uniformly distributed over the client’s secret random choice; when it is zero, the sensitive term disappears.

D Extractable DPF

This section defines extractable DPFs and public-parameter variants, then constructs an extractor that recovers the unique nonzero path from adversarial keys. The construction is polynomial-time and has a stated security bound.

DPF syntax: DPF with public parameters separates private keys from public parameters while retaining the standard two-party evaluation interface.Key generation outputs private keys and public parameters, and each server evaluates using its index, key, public parameters, and input.
Extractable DPF: The extractable DPF definition lets an adversary choose a sparse permissible-output set and requires an extractor to recover the adversary’s encoded input except with negligible probability.The permissible set is represented by an efficient circuit and has size at most 2^(λ/3).
Security bound: The constructed scheme and the prior DPF scheme are extractable, with adversary success bounded by the stated ε_A expression.Lemma D.2 establishes extractability for both schemes and gives the probability bound.
Extractor: The extractor follows oracle-query paths, assigns zero to paths whose required queries are absent, and selects one permissible output at each level.This procedure ensures that zero-valued prefixes rule out their extensions.
Extractor: The extractor examines at most 2nt strings, making its runtime polynomial in the security parameter, path length, and oracle-query count.It limits repeated analysis of identical oracle queries by string length and examines two extensions for each retained candidate.
Privacy connection: The privacy mechanism relies on prefix-count oracle queries, so differential privacy need only be ensured for those query outputs.The supplied analysis then bounds their noise and its effect on heavy-hitter correctness.

E.2 Noise analysis

Differential privacy adds Laplace noise to the protocol’s outputs, but tail bounds control large deviations across all queries. If the noise is small relative to the threshold, heavy-hitter errors are avoided within a margin.

Noise bound: 2λ/ε bounds the magnitude of a single-query noise deviation except with probability exp(−λ), while q queries raise the failure bound to qexp(−λ).The bound follows from a Laplace tail bound and a union bound.
Correctness: If 2λ/ε < 0.05t, noise shifts any candidate string’s weight by at most ±0.05t and does not cause false positives or false negatives.The condition compares the privacy noise scale directly with the heavy-hitter threshold.
Correctness: Under that margin, the servers output strings held by at least 1.05t clients and omit strings held by fewer than 0.95t clients.The result gives the supported separation between guaranteed outputs and guaranteed omissions.

E.3 Example parameter setting

The example setting fixes a 1% heavy-hitter threshold, strong privacy failure probability, and 256-bit strings. It translates the resulting noise bound into concrete inclusion and exclusion guarantees for 50 million clients.

Example parameters: With δ′ = 2−40, n = 256, per-query ε = 0.001, and one-in-a-billion correctness failure, per-query noise is bounded by ±60,000.The bound uses Laplace noise with parameter 2/ε = 2000 and κ = 30.
Example deployment: For 50 million clients, a 1% heavy hitter is a string held by more than 500,000 clients.This sets t = 0.01C for the example deployment.
Example guarantees: The deployment outputs strings held by more than 560,000 clients and omits strings held by fewer than 440,000 clients with overwhelming probability.These thresholds reflect the ±60,000 noise margin around the 500,000 heavy-hitter threshold.